Problem 78: Coin Partitions

Mathematical Foundation

Definition 1 (Generalized Pentagonal Numbers). The generalized pentagonal numbers are the values

The sequence $1, 2, 5, 7, 12, 15, 22, 26, \ldots$ lists these in increasing order.

Theorem 1 (Euler’s Pentagonal Number Theorem). As formal power series (and absolutely for $|x| < 1$):

Proof (Franklin’s Involution). The coefficient of $x^n$ in $\prod_{k=1}^{\infty}(1-x^k)$ equals $\sum_{\lambda \in \mathcal{D}_n} (-1)^{\ell(\lambda)}$, where $\mathcal{D}_n$ is the set of partitions of $n$ into distinct parts and $\ell(\lambda)$ is the number of parts.

For $\lambda = (\lambda_1 > \lambda_2 > \cdots > \lambda_r) \in \mathcal{D}_n$, define:

• $s = \lambda_r$: the smallest part.
• $t$: the length of the maximal run of consecutive integers descending from $\lambda_1$, i.e., $t = \max\{m \geq 1 : \lambda_1 - i + 1 \text{ is a part of } \lambda \text{ for all } 1 \leq i \leq m\}$.

Construct the involution $\phi$:

• Move A (when $s < t$, or when $s = t$ and the smallest part $\lambda_r$ is not part of the top run, i.e., $\lambda_r \neq \lambda_1 - t + 1$): Remove $\lambda_r = s$ and add $1$ to each of the $s$ largest parts. The result has $r - 1$ distinct parts.
• Move B (when Move A is inapplicable): Subtract $1$ from each of the $t$ largest parts and insert $t$ as a new smallest part. The result has $r + 1$ distinct parts.

These operations satisfy: (i) $\phi \circ \phi = \mathrm{id}$ (they are mutual inverses), (ii) each changes the parity of $r$, hence reverses the sign $(-1)^r$, and (iii) the map $\phi$ is undefined (fixed point) exactly when:

• $s = t$ and $\lambda_r = \lambda_1 - t + 1$: giving $\lambda = (2r-1, 2r-2, \ldots, r)$ and $n = r(3r-1)/2 = \omega_r^{+}$.
• $s = t + 1$ and $r = s$: giving $n = r(3r+1)/2 = \omega_r^{-}$.

Fixed points contribute $(-1)^r$; all other terms cancel pairwise. $\blacksquare$

Theorem 2 (Partition Recurrence). For $n \geq 1$:

where $p(0) = 1$, $p(m) = 0$ for $m < 0$, and the sum terminates when both $\omega_j^{+}$ and $\omega_j^{-}$ exceed $n$.

Proof. From Theorem 1 and the partition generating function $\sum_n p(n)x^n = \prod_k \frac{1}{1-x^k}$, we obtain

Extracting the coefficient of $x^n$ for $n \geq 1$:

Multiplying through by $-1$ and using $(-1)^{j} \cdot (-1) = (-1)^{j+1}$ yields the recurrence. $\blacksquare$

Lemma 1 (Pentagonal Number Count). The number of generalized pentagonal numbers not exceeding $n$ is $\Theta(\sqrt{n})$.

Proof. From $\omega_j^{+} = j(3j-1)/2 \leq n$, we obtain $j \leq \frac{1 + \sqrt{1 + 24n}}{6} = \Theta(\sqrt{n})$. Similarly for $\omega_j^{-}$. $\blacksquare$

Theorem 3 (Validity of Modular Computation). The recurrence in Theorem 2 is a $\mathbb{Z}$-linear combination of previous partition values with coefficients in $\{-1, +1\}$. Therefore, for any modulus $M$, computing $p(n) \bmod M$ at each step using $p(k) \bmod M$ for $k < n$ correctly yields $p(n) \bmod M$.

Proof. Since addition and subtraction in $\mathbb{Z}/M\mathbb{Z}$ satisfy $(a + b) \bmod M = ((a \bmod M) + (b \bmod M)) \bmod M$ and $(a - b) \bmod M = ((a \bmod M) - (b \bmod M)) \bmod M$, the modular reduction commutes with the recurrence at each step. $\blacksquare$

Editorial

Euler’s pentagonal recurrence is the whole algorithm. It expresses $p(n)$ as an alternating sum of earlier partition values taken at offsets given by the generalized pentagonal numbers. So instead of building partitions explicitly, we generate only the offsets that can actually contribute and combine previously computed values with the required signs.

Because the problem only asks when $p(n)$ becomes divisible by one million, we never need the full integers. Reducing modulo $10^6$ after every step preserves the divisibility test and keeps the numbers small. The candidates in each recurrence step are the pentagonal offsets not exceeding the current $n$; larger offsets are ignored because they would reference negative indices. We advance $n$ in order and stop as soon as the partition value becomes $0 \pmod{10^6}$.

Pseudocode

Precompute the generalized pentagonal numbers up to a safe search limit, together with their alternating signs.
Set p(0) = 1.

For n from 1 upward:
    start the new partition value at 0

    For each precomputed pentagonal offset that does not exceed n:
        add or subtract the previously computed partition value indicated by its sign

    Reduce the result modulo one million

    If the result is 0:
        return n

Complexity Analysis

Time: Each computation of $p(n)$ involves summing over $O(\sqrt{n})$ pentagonal terms (Lemma 1). Summing over all $n$ from $1$ to $n^*$ (the answer):

With $n^* = 55374$, this is approximately $1.3 \times 10^7$ operations.

Space: $O(n^*)$ entries storing $p(k) \bmod 10^6$ for $0 \leq k \leq n^*$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int MOD = 1000000;
    const int MAXN = 100000;

    vector<int> p(MAXN + 1, 0);
    p[0] = 1;

    // Precompute generalized pentagonal numbers with signs
    vector<pair<int, int>> pent; // (pentagonal number, sign)
    for (int k = 1; ; k++) {
        int g1 = k * (3 * k - 1) / 2;
        int g2 = k * (3 * k + 1) / 2;
        if (g1 > MAXN) break;
        int sign = (k % 2 == 1) ? 1 : -1;
        pent.push_back({g1, sign});
        if (g2 <= MAXN)
            pent.push_back({g2, sign});
    }

    for (int n = 1; n <= MAXN; n++) {
        long long val = 0;
        for (auto& [g, s] : pent) {
            if (g > n) break;
            val += (long long)s * p[n - g];
        }
        p[n] = ((int)(val % MOD) + MOD) % MOD;
        if (p[n] == 0) {
            cout << n << endl;
            return 0;
        }
    }

    return 0;
}

"""
Problem 78: Coin Partitions

Find the least value of n for which p(n) is divisible by one million.
Answer: 55374
"""


def main():
    MOD = 1_000_000
    MAXN = 100_000

    # Precompute generalized pentagonal numbers with signs
    pentagonals = []
    for k in range(1, 1000):
        g1 = k * (3 * k - 1) // 2
        g2 = k * (3 * k + 1) // 2
        if g1 > MAXN:
            break
        sign = 1 if k % 2 == 1 else -1
        pentagonals.append((g1, sign))
        if g2 <= MAXN:
            pentagonals.append((g2, sign))

    p = [0] * (MAXN + 1)
    p[0] = 1

    for n in range(1, MAXN + 1):
        val = 0
        for g, s in pentagonals:
            if g > n:
                break
            val += s * p[n - g]
        p[n] = val % MOD
        if p[n] == 0:
            print(n)
            return

    print(-1)


if __name__ == "__main__":
    main()