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?
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.003sPython
#!/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.024sRuby
#!/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