Solution

Answer: 55374

Let $p(n)$ denote the partition function: the number of ways to write $n$ as a sum of positive integers, disregarding order.

We are asked to find the smallest $n$ such that

$$p(n)\equiv 0 \pmod{1{,}000{,}000}.$$

For example,

$$p(5)=7,$$

because the partitions of $5$ are:

$$\begin{aligned} 5\ 4+1\ 3+2\ 3+1+1\ 2+2+1\ 2+1+1+1\ 1+1+1+1+1 \end{aligned}$$

Mathematical analysis

The key to solving this efficiently is Euler’s recurrence for the partition function.

1. Generating function for partitions

Euler showed that

$$\sum_{n=0}^{\infty} p(n)x^n = \prod_{k=1}^{\infty}\frac{1}{1-x^k}.$$

This product encodes partitions: each factor

$$1+x^k+x^{2k}+\cdots$$

represents using part $k$ any number of times.

Direct expansion is too slow for large $n$, so we need a recurrence.

2. Euler’s Pentagonal Number Theorem

Euler proved the remarkable identity

$$\prod_{k=1}^{\infty}(1-x^k) = \sum_{m=-\infty}^{\infty} (-1)^m x^{g(m)},$$

where

$$g(m)=\frac{m(3m-1)}2$$

are the generalized pentagonal numbers.

The first few are:

$$1,2,5,7,12,15,22,26,\dots$$

coming from

$$m=1,-1,2,-2,3,-3,\dots$$

Using the generating function relation, Euler derived the recurrence

$$p(n)= \sum_{k=1}^{\infty} (-1)^{k+1} \left( p!\left(n-\frac{k(3k-1)}2\right) + p!\left(n-\frac{k(3k+1)}2\right) \right),$$

with base conditions

$$p(0)=1,\qquad p(n)=0\text{ for }n<0.$$

The signs alternate in pairs:

$$+,+,-,-,+,+,-,-,\dots$$

This recurrence computes $p(n)$ in approximately $O(n\sqrt n)$, fast enough for this problem.

3. Working modulo one million

We only care whether $p(n)$ is divisible by $10^6$, so we compute

$$p(n)\bmod 1{,}000{,}000$$

at every step.

That keeps numbers small and computation efficient.

We iterate upward from $n=1$ until we find

$$p(n)\equiv 0 \pmod{1{,}000{,}000. }$$

Python implementation

MOD = 1_000_000

# p[n] will store partition numbers modulo MOD
p = [1]   # p(0) = 1

n = 1

while True:
    total = 0
    k = 1

    while True:
        # Generalized pentagonal numbers
        g1 = k * (3 * k - 1) // 2
        g2 = k * (3 * k + 1) // 2

        # Stop if both exceed n
        if g1 > n and g2 > n:
            break

        # Signs follow pattern:
        # +,+,-,-,+,+,...
        sign = 1 if k % 2 == 1 else -1

        if g1 <= n:
            total += sign * p[n - g1]

        if g2 <= n:
            total += sign * p[n - g2]

        k += 1

    total %= MOD
    p.append(total)

    if total == 0:
        print(n)
        break

    n += 1

Code walkthrough

Initialization

MOD = 1_000_000

We only need partition values modulo one million.

p = [1]

Stores partition values:

$$p(0)=1.$$

n = 1

We begin searching from $1$.

Main loop

while True:

Compute partition numbers one by one until divisibility is found.

total = 0
k = 1

total accumulates the recurrence sum.

k indexes generalized pentagonal numbers.

Pentagonal numbers

g1 = k * (3 * k - 1) // 2
g2 = k * (3 * k + 1) // 2

These generate

$$1,2,5,7,12,15,\dots$$

in the correct order.

Alternating signs

sign = 1 if k % 2 == 1 else -1

Implements

$$+,+,-,-,+,+,\dots$$

from Euler’s recurrence.

Add recurrence terms

if g1 <= n:
    total += sign * p[n - g1]

Adds contribution from one generalized pentagonal number.

Same for g2.

Reduce modulo one million

total %= MOD

Keeps integers manageable.

Store result

p.append(total)

Now p[n] is available for future computations.

Check divisibility

if total == 0:

If true, then

$$p(n)\equiv 0 \pmod{1{,}000{,}000}.$$

We print and stop.

Small-example verification

The recurrence correctly produces:

$$\begin{aligned} p(0)&=1\ p(1)&=1\ p(2)&=2\ p(3)&=3\ p(4)&=5\ p(5)&=7 \end{aligned}$$

matching the example in the problem statement.

Final verification

Known partition values grow extremely rapidly, so reaching a multiple of one million at a moderately sized $n$ is plausible.

Running the algorithm yields:

$$n=55374.$$

This is the established Project Euler result for Problem 78.

Answer: 55374

Project Euler Problem 78