Detailed mathematical approach

Problem Summary

For a positive integer \(n\), let \(p(n)\) denote the number of ways to write \(n\) as a sum of positive integers when order does not matter. For example, \(p(4)=5\) because the partitions are \(4\), \(3+1\), \(2+2\), \(2+1+1\), and \(1+1+1+1\).

Problem 78 asks for the least \(n\) such that \(p(n)\) is divisible by one million:

$p(n)\equiv 0 \pmod{10^6}.$

The partition function grows very quickly, so the useful task is not to compute exact giant integers, but to generate the residues \(p(0),p(1),p(2),\dots\) modulo \(10^6\) until the first zero residue appears.

Mathematical Approach

The implementations are built around Euler's pentagonal recurrence for the partition function. That recurrence is not a generic dynamic-programming trick; it comes from the generating function of integer partitions and the pentagonal number theorem.

From partitions to a generating function

If we choose how many \(1\)'s, how many \(2\)'s, how many \(3\)'s, and so on appear in a partition, then the generating function for \(p(n)\) is

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

Each factor \(1/(1-x^m)=1+x^m+x^{2m}+\cdots\) records how many copies of the part \(m\) are used. The coefficient of \(x^n\) in the full product is therefore exactly the number of partitions of \(n\).

Euler's pentagonal theorem produces the recurrence

Euler proved the identity

$\prod_{m=1}^{\infty}(1-x^m)=1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right).$

Since this product is the reciprocal of \(P(x)\), we have

$P(x)\cdot\left(1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right)\right)=1.$

Now compare coefficients of \(x^n\). With the conventions \(p(0)=1\) and \(p(m)=0\) for \(m<0\), the coefficient identity becomes

$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).$

For any fixed \(n\), only finitely many terms contribute, because once the offset exceeds \(n\), every later term is automatically zero.

Generalized pentagonal numbers and the sign pattern

The two offsets that appear for each \(k\ge 1\) are

$g_k^-=\frac{k(3k-1)}{2},\qquad g_k^+=\frac{k(3k+1)}{2}.$

These generate the sequence

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

called the generalized pentagonal numbers. The sign attached to the pair \((g_k^-,g_k^+)\) depends only on the parity of \(k\): when \(k\) is odd, both terms are added; when \(k\) is even, both terms are subtracted. So the recurrence follows the pattern

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

across successive generalized pentagonal offsets.

Worked example: computing \(p(7)\)

For \(n=7\), the generalized pentagonal numbers not exceeding 7 are \(1,2,5,7\). Therefore

$p(7)=p(6)+p(5)-p(2)-p(0).$

Using the earlier values \(p(6)=11\), \(p(5)=7\), \(p(2)=2\), and \(p(0)=1\), we get

$p(7)=11+7-2-1=15.$

This matches the direct count of the 15 partitions of 7. The example shows why the recurrence is practical: instead of recomputing partitions from scratch, each new value is assembled from already known smaller ones.

Why working modulo one million is enough

The recurrence is linear, so reducing every stored value modulo \(10^6\) preserves correctness:

$p(n)\bmod 10^6=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p(n-g_k^-)+p(n-g_k^+)\right)\bmod 10^6.$

This is the crucial invariant used by the implementation. At step \(n\), the table already contains correct residues for all smaller indices, and those residues are sufficient to compute the next residue. No exact huge partition number ever needs to be stored.

How the Code Works

Growing the partition table one value at a time

The C++, Python, and Java implementations begin with the base case \(p(0)=1\). They then build the sequence incrementally: compute the residue for \(p(1)\), append it, compute the residue for \(p(2)\), append it, and continue until a zero residue is found.

Applying Euler's recurrence in the inner loop

For a fixed \(n\), the implementation loops over \(k=1,2,3,\dots\), forms the two offsets \(k(3k-1)/2\) and \(k(3k+1)/2\), and stops as soon as the smaller offset already exceeds \(n\). The contribution of each pair is added or subtracted according to whether \(k\) is odd or even. If the second offset is still within range, it contributes too; otherwise only the first one is used.

The partial sum can become negative, so the implementation reduces the result modulo the target modulus and then normalizes it into the standard range \(0\) through \(10^6-1\). The C++ and Java versions use a wider accumulator type for this temporary sum before taking the modulus.

Termination and a small sanity check

After each new residue is computed, the implementation checks whether it is zero. The first \(n\) for which that happens is the required answer. One implementation also includes a small checkpoint with modulus \(5\): since \(p(4)=5\), the least \(n\) satisfying \(p(n)\equiv 0\pmod 5\) is \(4\). That verifies that the recurrence and stopping rule are wired correctly before running the full search with modulus \(10^6\).

Complexity Analysis

Let \(N\) be the least index with \(p(N)\equiv 0\pmod{10^6}\). For a given \(n\), the number of usable generalized pentagonal numbers is \(O(\sqrt{n})\), because the offsets grow quadratically in \(k\). Summing that cost over \(n=1\) through \(N\) gives total time

$\sum_{n=1}^{N} O(\sqrt{n})=O(N^{3/2}).$

The table stores one residue for each value from \(0\) through \(N\), so the space usage is \(O(N)\). This is why Euler's recurrence is so effective here: it turns an apparently difficult partition-counting search into a single sequential computation with modest memory.

Footnotes and References

1. Problem page: Project Euler 78
2. Integer partitions: Wikipedia - Partition (number theory)
3. Partition function: Wikipedia - Partition function
4. Pentagonal number theorem: Wikipedia - Pentagonal number theorem
5. Partition numbers sequence: OEIS A000041