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\displaystyle 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?

Haskell

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.000s

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   0m12.873s
user   0m12.732s
sys    0m0.040s

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.217s
user   0m0.164s
sys    0m0.000s

Questions? Comments? Send me an email: [email protected]