// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (13 votes, average: 4.69 out of 5)
Loading...

Project Euler Solutions

Project Euler 50 Solution

Project Euler 50 Solution

Project Euler 50: Find the prime number, below one-million, that can be written as the sum of the most consecutive primes.


Project Euler 50 Problem Description

Project Euler 50: 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.

Project Euler 50 Solution

Runs < 0.003 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 50 Solution Python 2.7 source.

Afterthoughts

Limit

Starting prime

Prime sum

# terms

Run time
102

2

41

6 Terms

<0.001 sec.
103

7

953

21 Terms

<0.001 sec.
104

3

9521

65 Terms

<0.001 sec.
105

3

92951

183 Terms

<0.001 sec.
106

7

997651

543 Terms

0.002 sec.
107

5

9951191

1587 Terms

0.005 sec.
108

7

99819619

4685 Terms

0.011 sec.
109

11

999715711

13935 Terms

0.03 sec.
1010

2

9999419621

41708 Terms

0.1 sec.
1011

19

99987684473

125479 Terms

0.36 sec.
1012

5

999973156643

379317 Terms

1 sec.
Project Euler 50 Solution last updated

Discussion

3 Responses to “Project Euler 50 Solution”

  1. (summax that is necessary for us

    Posted by Francky | April 28, 2011, 8:57 AM
  2. 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 < max is valid. Does this help at all?

      Posted by Mike | February 1, 2011, 3:30 PM

Post a comment