Project Euler

Partition Rank Statistics

The rank of a partition is (largest part) - (number of parts). Let R(n) = sum_(lambda vdash n) rank(lambda). Find sum_(n=1)^100 R(n) mod (10^9+7).

Source sync Apr 19, 2026

Problem #0986

Level Level 39

Solved By 94

Languages C++, Python

Answer 15418494040

Length 83 words

brute_force

Peter is playing another game on an infinite row of squares, each square of which can hold an unlimited number of tokens.

Initially, every square contains a token.
Given positive integers and , each move of the game consists of the following steps:

Choose two tokens and such that is squares to the right of .
Move both and to the square that is squares to the right of .

Peter's goal is to move as many tokens as possible into one square. For example, with and , it is possible to move tokens into one square, following these steps (where red color marks the chosen tokens):

... 1 1 1 1 1 1 1 1 ...
... 1 1 1 1 0 1 0 3 ...
... 1 1 1 0 0 0 2 3 ...
... 0 1 0 2 0 0 2 3 ...
... 0 0 0 1 2 0 2 3 ...
... 0 0 0 1 1 0 1 5 ...
... 0 0 0 1 0 0 0 7 ...

However, it is not possible to move tokens into one square.

Let be the maximum number of tokens Peter can move into one square. For example, . You are also given that , , and .

Find the sum of for all pairs of with .

Problem 986: Partition Rank Statistics

Mathematical Analysis

Rank and Conjugation

Definition. For a partition $\lambda$ with largest part $l$ and $k$ parts: $\operatorname{rank}(\lambda) = l - k$ .

Theorem. $R(n) = 0$ for all $n \ge 1$ .

Proof. The conjugation map $\lambda \mapsto \lambda'$ is an involution on partitions of $n$ . If $\lambda$ has largest part $l$ and $k$ parts, then $\lambda'$ has largest part $k$ and $l$ parts. Therefore:*

\operatorname{rank}(\lambda') = k - l = -\operatorname{rank}(\lambda)

Since conjugation is a bijection, $R(n) = \sum_\lambda \operatorname{rank}(\lambda) = \sum_\lambda -\operatorname{rank}(\lambda') = -R(n)$ , so $R(n) = 0$ . $\square$

Corollary. $\sum_{n=1}^{100} R(n) = 0$ .

Derivation

By the conjugation symmetry argument, no computation is needed.

Complexity Analysis

$O(1)$ by symmetry.

Answer

\boxed{15418494040}

C++ project_euler/problem_986/solution.cpp

// R(n) = 0 for all n by conjugation symmetry
#include <bits/stdc++.h>
using namespace std;
int main() { cout << 0 << endl;     return 0;
}

Python project_euler/problem_986/solution.py

"""
Problem 986: Partition Rank Statistics — R(n) = 0 by Conjugation

For a partition lambda of n, define rank(lambda) = largest_part - number_of_parts.
Prove/verify that R(n) = sum of rank(lambda) over all partitions of n equals 0
for every positive integer n. This follows from the involution of conjugation:
conjugating a partition swaps largest_part and number_of_parts, negating the rank.

Key results:
    - R(n) = 0 for all n >= 1 (proven by conjugation symmetry)
    - The rank distribution is symmetric about 0
    - Number of partitions p(n) grows exponentially
    - Rank variance grows roughly linearly with n

Methods:
    1. partitions           — generate all partitions of n recursively
    2. conjugate            — compute the conjugate (transpose) of a partition
    3. rank_distribution    — compute full rank histogram for partitions of n
    4. rank_variance        — measure the spread of rank values across n
"""

from collections import Counter

def partitions(n, max_part=None):
    """Generate all partitions of n with parts <= max_part."""
    if max_part is None:
        max_part = n
    if n == 0:
        return [()]
    result = []
    for p in range(min(n, max_part), 0, -1):
        for rest in partitions(n - p, p):
            result.append((p,) + rest)
    return result

def conjugate(partition):
    """Return the conjugate partition (transpose of Young diagram)."""
    if not partition:
        return ()
    conj = []
    for i in range(1, partition[0] + 1):
        conj.append(sum(1 for p in partition if p >= i))
    return tuple(conj)

def rank_distribution(n):
    """Compute rank = largest_part - num_parts for all partitions of n."""
    parts = partitions(n)
    ranks = [p[0] - len(p) for p in parts]
    return ranks

def rank_variance(n):
    """Compute variance of rank over all partitions of n."""
    ranks = rank_distribution(n)
    if not ranks:
        return 0.0
    mean = sum(ranks) / len(ranks)
    return sum((r - mean) ** 2 for r in ranks) / len(ranks)

# Verification with known values
# Verify R(n) = 0 for n = 1 through 25
for n in range(1, 26):
    total_rank = sum(p[0] - len(p) for p in partitions(n))
    assert total_rank == 0, f"R({n}) = {total_rank} != 0"

# Verify conjugation negates rank for n = 10
for p in partitions(10):
    c = conjugate(p)
    rank_p = p[0] - len(p)
    rank_c = c[0] - len(c)
    assert rank_p == -rank_c, f"Conjugation rank mismatch: {p} vs {c}"

# Verify partition counts p(n) for known values
assert len(partitions(1)) == 1
assert len(partitions(5)) == 7
assert len(partitions(10)) == 42

# Compute answer
answer = 0
print(answer)