Statement

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

Solution

It's a brute-force approach with limits and performance improvements.

The limits are:

• We just evaluate sequences until 500000, all sequences starting with a prime higher than that will be at most of length 1.
• As soon as the subsequence gets higher than 1000000 we stop incrementing that subsequence

The performance improvements are:

• Using a set of primes to check whether the subsequence is a prime or not, checking a set is O(1) and checking a list is O(n).

from CommonFunctions import find_primes_less_than
from itertools import takewhile
 
if __name__ == '__main__':
    primes = find_primes_less_than(1000000)
    prime_set = set(primes)
    max_len = 0
    result = 0
    for i in takewhile(lambda i: primes[i] <= 5000000,
                       range(len(primes))):
        tmp = primes[i]
        for j in takewhile(lambda j: tmp + primes[j] <= 1000000,
                           range(i + 1, len(primes))):
            tmp += primes[j]
            if j - i + 1 > max_len and tmp in prime_set:
                result = tmp
                max_len = j - i + 1
    print("The result is:", result)

The Python file is available for download here.