Problem Description

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

Analysis

A straightforward extension to problem 76 using primes instead of counting numbers and having a variable target instead of a fixed one.

Solution

Runs < 1 second in Python.

primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79]
 
target = 11
while True:
  ways = [1] + [0]*target
  for i in primes:
    for j in range(i, target+1):
      ways[j] += ways[j-i]
  if ways[target] > 5000: break
  target += 1;
print "Answer to PE77 = ", target;

Comments

We selected this method because it uses fewer primes than having to guess at both the target and the number of primes needed. Also, from the example, we can start at 11 for our search.