Project Euler 77: Find the first integer which can be written as the sum of primes in over five thousand different ways

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 31 and 76 using primes instead of coins or counting numbers and having a variable target instead of a fixed one. We find the number of ways to sum primes for each number from 11 until the number of ways to sum exceed 5000.

Finding the ideal set of primes to use in the sum required some investigation. I happened upon a sequence A000607: Number of partitions of n into prime parts that listed each number and its prime partitions. Surprisingly, the number was very small and by the time you get to 80 the number of partitions exceeds 10,000. So, clearly, only primes less than 80 would be required.

If you wanted to extend this problem to some other reasonable limit, such as “What is the first value which can be written as the sum of primes in over 10¹⁷ different ways?”, prime numbers less than 1,000 would suffice.

Project Euler 77 Solution

Afterthoughts

• From the example, we can start at 11 for our search.
  
• The fewer primes that you start with, increases the number of combinations.
  
• Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000607: Number of partitions of n into prime parts.
  
• See also, Project Euler 31 Solution:
  
• See also, Project Euler 76 Solution: