     (11 votes, average: 5.00 out of 5) Loading...

## Project Euler 77 Solution ## 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 1017 different ways?”, prime numbers less than 1,000 would suffice.

#### Project Euler 77 Solution

Runs < 0.005 seconds in Python 2.7. Use this link to get the Project Euler 77 Solution Python 2.7 source.

#### Afterthoughts

Project Euler 77 Solution last updated