Consecutive Prime Sum: Project Euler

As proposed in my previous post, I decided to tackle another problem from Project Euler. This is Problem 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?

So far I've completed eight out of the 723 problems currently available. This latest problem proved a difficult one to attack mainly because any recourse to subsets or partitions generated numbers so large that SageMathCell timed out. Even the method I developed of slicing the list of primes into progressively shorter lists caused a time out but for the upper limits of 100 and 1000 it worked fine:

upper_limit=100

P=[n for n in [2..upper_limit] if is_prime(n)]

record=0

for i in [i..len(P)-1]:

    for j in [i+1..len(P)-1]:

        Q=[p for p in P if p>=P[i] and p<=P[j]]

        if sum(Q)<upper_limit and is_prime(sum(Q)):

            if len(Q)>record:

                record=len(Q)

                print((P[i],P[j],sum(Q),len(Q)))

 (2, 3, 5, 2)

(2, 7, 17, 4)

(2, 13, 41, 6)

In the preceding code, we see that the six primes from 2 to 13 add to the prime 41.

upper_limit=1000

P=[n for n in [2..upper_limit] if is_prime(n)]

record=0

for i in [0..len(P)-1]:

    for j in [i+1..len(P)-1]:

        Q=[p for p in P if p>=P[i] and p<=P[j]]

        if sum(Q)<upper_limit and is_prime(sum(Q)):

            if len(Q)>record:

                record=len(Q)

                print((P[i],P[j],sum(Q),len(Q))) 

(2, 3, 5, 2)

(2, 7, 17, 4)

(2, 13, 41, 6)

(2, 37, 197, 12)

(2, 43, 281, 14)

(3, 53, 379, 15)

(3, 61, 499, 17)

(7, 89, 953, 21)

In the preceding code, we see that the 21 primes from 7 to 89 add to the prime 953.

Once the upper limit is set to 1000000, the time out problems began. I needed to set the \(i\) values manually starting with 0 and working up:

• starting with \(i=0\), I got a result of (2, 3863, 958577, 536)
• starting with \(i=1\), I got a result of (3, 3779, 920291, 525)
• starting with \(i=2\), I got a result of (5, 3911, 978037, 539)
• starting with \(i=3\), I got a result of (7, 3931, 997651, 543)

I submitted this last result to Project Euler and it proved the correct result so there was no need to keep going. Thus the answer to the question of which prime, below one-million, can be written as the sum of the most consecutive primes is 997651. It is the sum of 543 consecutive primes, beginning with 7 and ending with 3931. Line 4 of the code (as shown in Figure 1) reads: 

for i in [3 .. len(P)-1]: 

Here is the permalink to the code shown in the screenshot (Figure 1):

Figure 1