(4 votes, average: 4.00 out of 5)

## Project Euler Problem 50 Solution

#### Problem Description

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

#### Analysis

We need to answer two simple questions: With which prime do we start and how many consecutive primes do we need to add.

We built an array of sums, each time adding a new prime to the total until the total exceeded the maximum (1,000,000 in this case.) It is then a simple task to look at different sums and record the one with the most terms.

#### Solution

Runs < 1 second in Python.

```from Euler import prime_sieve, is_prime   max = 1000000 primes = prime_sieve(max) prime_sum = [0]   sum = 0 count = 0 while (sum<max): sum+=primes[count] prime_sum.append(sum) count+=1   terms = 1 for i in range(count): for j in range(i+terms, count): n = prime_sum[j] - prime_sum[i] if (j-i>terms and is_prime(n)): (terms,max_prime) = (j-i,n)   print "Answer to Problem 50 = ",max_prime," with ",terms," terms\n";```

• Was surprised by how many terms were required.

## Discussion

### 3 Responses to “Project Euler Problem 50 Solution”

1. how could you make sure that the answer you get must be correct?

for this case:
while (sum<max):
sum+=primes[count]
prime_sum.append(sum)
count+=1

I don't think (sum<max) is a legal condition. note that even sum exceeds max,
prime_sum[j]-prime_sum[i]
might be smaller than max, thus it could be the final answer.

Posted by jcchen | January 30, 2011, 6:44 AM
• I had to look at the code after so many years but confirmed that the logic is sound. Even for 100,000,000 the program produces a result of 99,819,619 with 4685 terms.

Our table of consecutive prime sums can never exceed our maximum, so sum

Does this help at all?

Posted by Mike | February 1, 2011, 3:30 PM
2. (summax that is necessary for us

Posted by Francky | April 28, 2011, 8:57 AM