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?



In [8]:

    
let enumerate_array (a:'a []) =
    seq { for i in 0 .. (a.Length-1) -> (i, a.[i]) }

let compositesInRange fromNum toNum =
    [|2 .. toNum/fromNum|]
    |> Array.map (fun x -> fromNum * x)
    
let primesTo n =
    // start off assuming every number from 0 .. n is prime
    let isPrime = Array.init (1+n) (fun _ -> true)
    
    isPrime.[0] <- false
    isPrime.[1] <- false
    
    // simple sieve of eratosthenes - update "primeness" of
    // each number in the isPrime array
    for x in 2 .. int(sqrt(double(n))) do 
        if isPrime.[x] then             
            compositesInRange x n
            |> Array.map (fun i -> isPrime.[i] <- false)
            |> ignore

    enumerate_array isPrime
    |> Seq.filter (fun (i,t) -> t)
    |> Seq.map fst

let limit = 1000000
let primesToMillion = primesTo limit |> Seq.toArray
let primesToMillionSet = primesToMillion |> Set.ofArray

let rec consecutivePrimes' i currentCount currentSum maxCount maxSum =   
    let newSum = currentSum + primesToMillion.[i]
    if newSum >= limit then (maxSum, maxCount)
    elif primesToMillionSet.Contains(newSum) && currentCount > maxCount then
        consecutivePrimes' (i+1) (currentCount+1) newSum currentCount newSum
    else
        consecutivePrimes' (i+1) (currentCount+1) newSum maxCount maxSum

let consecutivePrimesStartingAt i =
    consecutivePrimes' i 0 0 -1 -1
    
// hacky :-(
[0..10000]
|> List.map consecutivePrimesStartingAt
|> List.sortBy (fun (s,c) -> -c)
|> List.head









    Out[8]:





(997651, 542)