Project Euler Problem 50: Consecutive Prime Sum

The source code for this problem can be found here.

Problem 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 Discussion

This problem can be solved by considering a sliding window over a list of primes. For each window, remove primes until the sum of the remaining primes is also a prime number. Find the prime with the maximal number of sub-primes.

Solution Implementation

from lib.numbertheory import is_probably_prime
from lib.sequence import Primes


def maximise_b(upper_bound, primes, s, b):
    """ Accumulate increasing primes into s, starting at primes[b], until the new sum is also prime but no larger than
        upper_bound
    """
    while b < len(primes) and s < upper_bound:
        s += primes[b]
        b += 1
    return s, b


def maximal_prime(primes, s, b):
    """ Remove high primes from s until it is prime """
    prime_s = s
    while not is_probably_prime(prime_s):
        b -= 1  #
        prime_s -= primes[b]
    return prime_s, b


def solve():
    """ Compute the answer to Project Euler's problem #50 """

    upper_bound = 1000000
    n_primes = 5000
    primes = list(Primes(upper_bound=n_primes))
    s, a, b = 0, 0, 0
    n_sub_primes = 0
    answer = None

    # Find primes s s.t. s = sum(primes[a:b]) for increasing values of a
    # Maintain s as a sliding window to avoid enumerating the same primes over and over
    while a < upper_bound and b < len(primes):
        # consider a window primes[a:b]
        s, b = maximise_b(upper_bound, primes, s, b)  # find the maximal b s.t. sum(primes[a:b]) < upper_bound
        prime_s, b1 = maximal_prime(primes, s, b)  # remove high primes until sum(primes[a:b]) is a prime number
        if b1 - a + 1 > n_sub_primes:
            # New best answer
            n_sub_primes = b1 - a + 1
            answer = prime_s
        s -= primes[a]
        a += 1

    return answer


expected_answer = 997651

solutions.problem50.maximal_prime(primes, s, b)

Remove high primes from s until it is prime

solutions.problem50.maximise_b(upper_bound, primes, s, b)

Accumulate increasing primes into s, starting at primes[b], until the new sum is also prime but no larger than upper_bound

solutions.problem50.solve()

Compute the answer to Project Euler’s problem #50