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:
This is the longest sum of consecutive primes that adds to a prime below onehundred.
The longest sum of consecutive primes below onethousand that adds to a prime, contains \(21\) terms, and is equal to \(953\).
Which prime, below onemillion, 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 subprimes.
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