Project Euler Problem 77

Solution

Answer: 71

We are asked for the first integer that can be written as a sum of primes in more than 5000 different ways.

This is a classic integer partition problem, except the allowed parts are only primes.

---

Mathematical analysis

Let $f(n)$ denote the number of ways to write $n$ as a sum of primes, where order does not matter.

For example, for $10$:

$$\begin{aligned} 10 &= 7+3\ &=5+5\ &=5+3+2\ &=3+3+2+2\ &=2+2+2+2+2 \end{aligned}$$

so $f(10)=5$.

---

Key insight: coin-change dynamic programming

This problem is structurally identical to the classic “coin change” problem.

Suppose the available primes are

$$2,3,5,7,11,\dots$$

We want the number of unordered sums producing $n$.

Define:

$$dp[k]$$

as the number of ways to form total $k$.

Initially:

$$dp[0]=1$$

because there is exactly one way to make zero: choose nothing.

Then for each prime $p$, update:

$$dp[k] \mathrel{+}= dp[k-p]$$

for all $k\ge p$.

Why does this work?

• When processing prime $p$,
• every way to make $k-p$
• becomes a way to make $k$ by adding one $p$.

Because primes are processed in increasing order, each combination is counted exactly once, regardless of arrangement.

---

Generating primes

We only need relatively small numbers, so a simple primality test suffices.

A number $n$ is prime if no integer $d \le \sqrt n$ divides it.

---

Strategy

We increment $n$ from small values upward:

1. Generate all primes $\le n$
2. Compute the number of prime partitions of $n$
3. Stop once the count exceeds $5000$

---

Python implementation

from math import isqrt

# Check whether a number is prime
def is_prime(n):
    if n < 2:
        return False
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return False
    return True

# Generate all primes up to limit
def primes_up_to(limit):
    return [x for x in range(2, limit + 1) if is_prime(x)]

target = 5000
n = 2

while True:
    primes = primes_up_to(n)

    # dp[k] = number of ways to write k as a sum of primes
    dp = [0] * (n + 1)
    dp[0] = 1

    # Coin-change style dynamic programming
    for p in primes:
        for k in range(p, n + 1):
            dp[k] += dp[k - p]

    # Check whether we've exceeded the target
    if dp[n] > target:
        print(n)
        break

    n += 1

---

Code walkthrough

Prime testing

def is_prime(n):

Checks primality by trial division up to $\sqrt n$.

for d in range(2, isqrt(n) + 1):

If any divisor exists, the number is composite.

---

Prime generation

def primes_up_to(limit):
    return [x for x in range(2, limit + 1) if is_prime(x)]

Builds the list of usable prime “coins”.

---

Main search loop

while True:

We test integers one by one until the condition is satisfied.

---

Dynamic programming table

dp = [0] * (n + 1)
dp[0] = 1

Base case:

$$dp[0]=1$$

meaning there is one empty sum.

---

Transition

for p in primes:
    for k in range(p, n + 1):
        dp[k] += dp[k - p]

For every prime $p$:

• all ways to form $k-p$
• extend to ways to form $k$.

This counts unordered decompositions correctly.

---

Verifying the small example

For $n=10$, the algorithm gives:

$$dp[10]=5$$

matching the five decompositions listed in the problem statement.

---

Final verification

The number of prime partitions grows fairly rapidly, so the first value exceeding $5000$ should not be extremely large.

Running the algorithm yields:

$$71$$

Indeed:

• $f(70) \le 5000$
• $f(71) > 5000$

so this is the first such integer.

Answer: 71