// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (10 votes, average: 4.60 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.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|997651|

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