Detailed mathematical approach

Problem Summary

We seek the smallest positive integer \(n\) whose number of unordered representations as a sum of prime numbers exceeds 5000. Repetitions are allowed, so expressions such as \(2+2+3+3\) are valid, but order does not matter: \(3+2+3+2\) is the same representation.

If \(q(n)\) denotes this prime-partition count, the task is to find the first \(n\) with \(q(n) > 5000\). The implementations do not assume an a priori bound; they test \(n=2,3,4,\dots\) in order and stop at the first successful value.

Mathematical Approach

The central object is not the list of partitions itself, but a counting function that remembers which primes are currently allowed. That viewpoint turns the problem into the same kind of combinatorial recurrence used in unrestricted coin-change counting, except the available parts are precisely the primes.

Prime partitions and the correct state space

Let the primes up to \(n\) be \(p_1 < p_2 < \cdots < p_k\). Define \(Q_i(s)\) to be the number of unordered ways to write \(s\) as a sum of the first \(i\) primes \(p_1,\dots,p_i\). Then the quantity we really want is

$q(n)=Q_k(n),$

because primes larger than \(n\) cannot appear in a sum equal to \(n\).

This definition introduces the right invariant for dynamic programming: after we finish processing the first \(i\) primes, the count for each \(s\) must already equal \(Q_i(s)\).

Generating function viewpoint

Each prime \(p\) may be used \(0,1,2,\dots\) times, so its contribution to the generating function is

$1+x^p+x^{2p}+x^{3p}+\cdots=\frac{1}{1-x^p}.$

Multiplying over all usable primes gives

$\sum_{s=0}^{\infty} Q_k(s)x^s=\prod_{i=1}^{k}\frac{1}{1-x^{p_i}}.$

Equivalently, for the final target \(n\),

$q(n)=\left[x^n\right]\prod_{p \le n,\; p\text{ prime}}\frac{1}{1-x^p}.$

The coefficient extraction says exactly what we are counting: every time the product produces \(x^n\), we have chosen a multiset of primes summing to \(n\).

The recurrence behind the one-array DP

The generating function leads directly to a recurrence. For \(i \ge 1\) and \(s \ge 0\), split the representations counted by \(Q_i(s)\) into two disjoint classes:

One class uses no copy of \(p_i\), contributing \(Q_{i-1}(s)\).

The other class uses at least one \(p_i\). Removing one copy of \(p_i\) leaves an unordered representation of \(s-p_i\) that may still use \(p_i\), contributing \(Q_i(s-p_i)\).

Therefore

$Q_i(s)=Q_{i-1}(s)+Q_i(s-p_i)\qquad (s \ge p_i),$

with boundary conditions

$Q_i(0)=1,\qquad Q_0(s)=0\text{ for }s>0.$

If \(s<p_i\), then \(Q_i(s)=Q_{i-1}(s)\), because the prime \(p_i\) is too large to appear.

Why the update order counts each multiset exactly once

The implementations compress the recurrence into one array indexed by the current sum. When processing a fixed prime \(p_i\), they sweep the sums upward from \(p_i\) to \(n\). At that moment, the entry for \(s-p_i\) already includes all representations that use the primes \(p_1,\dots,p_i\), so adding it into the entry for \(s\) realizes the term \(Q_i(s-p_i)\).

This ascending sweep is what prevents overcounting. A representation such as \(5+3+2\) is created only when the prime 5 is being processed from the already canonical representation of \(3+2\); it is not created again from a different order such as \(2+5+3\). In other words, the outer loop over primes imposes a nondecreasing order on the parts, so each unordered multiset is counted once.

Worked example: \(q(10)\) and the smaller checkpoint

For \(n=10\), the usable primes are \(2,3,5,7\). The unordered prime partitions are

$10=7+3=5+5=5+3+2=3+3+2+2=2+2+2+2+2,$

so \(q(10)=5\).

This example also explains the smaller validation target used by two of the implementations. Since \(q(10)=5\) is not yet greater than 5, the next candidate must be checked. For \(n=11\) there are six unordered prime partitions, so the first value with more than 5 representations is 11.

How the Code Works

Growing the candidate and the prime list

The C++, Python, and Java implementations search upward one integer at a time. At each step they test whether the current candidate is prime; if it is, they append it to the stored list of available primes. The primality tests are simple trial-division routines up to \(\sqrt{n}\), with minor language-level differences in how candidate divisors are skipped.

Rebuilding the count table for the current candidate

For each candidate \(n\), the implementation allocates a table of length \(n+1\), initializes the count for sum 0 to 1, and leaves all other counts at 0. It then processes the known primes in increasing order, ignoring any prime larger than \(n\). For each prime \(p\), it updates every sum \(s=p,p+1,\dots,n\) by adding the current count for \(s-p\) into the count for \(s\).

After the loop for a given prime finishes, the table entry for each \(s\) equals the number of unordered representations of \(s\) using only the primes processed so far. That is exactly the invariant \(Q_i(s)\) described above.

Stopping rule

Once the table entry for the current candidate \(n\) exceeds the requested threshold, the search terminates immediately and returns \(n\). The C++ and Python versions also include a small validation step: for threshold 5, the first qualifying value must be 11. The Java version hardcodes the Project Euler threshold directly.

Complexity Analysis

Suppose \(N\) is the first integer with \(q(N)\) above the threshold. Because the implementations rebuild the dynamic-programming table from scratch for every candidate \(2,3,\dots,N\), the total counting work is

$\sum_{n=2}^{N}\sum_{p \le n,\; p\text{ prime}} (n-p+1)=O\!\left(\sum_{n=2}^{N} n\,\pi(n)\right),$

where \(\pi(n)\) is the prime-counting function. Using the rough estimate \(\pi(n)\sim n/\log n\), this behaves like \(O(N^3/\log N)\), and it is certainly bounded by \(O(N^3)\).

The primality tests contribute less than the repeated DP construction, and memory usage is only \(O(N)\) because each implementation keeps one count table for the current candidate plus the list of discovered primes. For this problem the first successful \(N\) is small, so the straightforward recomputation strategy is entirely adequate.

Footnotes and References

1. Problem page: Project Euler 77
2. Prime numbers: Wikipedia - Prime number
3. Integer partitions: Wikipedia - Partition (number theory)
4. Generating functions: Wikipedia - Generating function
5. Dynamic programming: Wikipedia - Dynamic programming