# 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

# 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:
n_sub_primes = b1 - a + 1
s -= primes[a]
a += 1


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