# Project Euler Problem 50 Solution

## Question

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?

import Data.Function (on)
import Data.List (maximumBy)

primes :: [Int]
primes = 2 : sieve primes [3,5..] where
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
where (h, t) = span (< p*p) xs

isPrime :: Int -> Bool
isPrime n | n < 1 = False
| otherwise = not $or [n rem x == 0 | x <- [2..floor$ sqrt $fromIntegral n]] consecutive :: Int -> [Int] consecutive p = dropWhile (not . isPrime)$ reverse sums where
sums = takeWhile (< 1000000) $scanl1 (+)$ dropWhile (< p) primes

main :: IO ()
main = print $head$ maximumBy (compare on length) $map consecutive$ take 10 primes
$ghc -O2 -o consecutive-prime-sum consecutive-prime-sum.hs$ time ./consecutive-prime-sum
real   0m0.003s
user   0m0.000s
sys    0m0.003s

## Python

#!/usr/bin/env python

def euler(n):
# Create a candidate list within which non-primes will
# marked as None, noting that only candidates below
# sqrt(n) need be checked.
candidates = list(range(n+1))
fin = int(n**0.5)

# Loop over the candidates, marking out each multiple.
# If the current candidate is already checked off then
# continue to the next iteration.
for i in range(2, fin+1):
if not candidates[i]:
continue

candidates[2*i::i] = [None] * (n//i - 1)

# Filter out non-primes and return the list.
return [i for i in candidates[2:] if i]

def main():
primes = euler(1000000)
largest = 0
chain = []
for start in range(10):
seq = primes[start:]
i = 0
total = 0
for prime in seq:
total += prime
if total > 1000000:
break
i += 1
if total in primes:
c = seq[:i]
if len(c) > len(chain):
chain = c
print(sum(chain))

if __name__ == "__main__":
main()
$time python3 consecutive-prime-sum.py real 0m10.962s user 0m10.938s sys 0m0.024s ## Ruby #!/usr/bin/env ruby require 'mathn' primes = Prime.each(10000).to_a longest = [] primes[0..10].each_with_index { |p, i| j = i begin j += 1 cons = primes[i..j] sum = cons.reduce(:+) if sum.prime? && cons.length > longest.length longest = cons end end while sum < 1000000 } puts longest.reduce(:+) $ time ruby consecutive-prime-sum.rb
real   0m0.059s
user   0m0.059s
sys    0m0.000s