### The Problem

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?

### The Solution

Problem 50! I think after solving this one, I earn some sort of prize. I'm hoping for a luxury vacation, but I'm not holding my breath.

The first thing we need is the list of primes below 1000000. We'll start by stealing some code from problem 35 to generate those.

``````let intsqrt i = int(sqrt(float i))

let isPrime i =
if i <= 1 then false
elif i = 2 then true
elif (i &&& 1) = 0 then false
else
let sr = intsqrt i
seq { 3..2..sr } |> Seq.forall (fun f -> i%f<>0)

let rec nextPrime x =
match x with
| x when isPrime x -> x
| x -> nextPrime (x + 1)

let getPrimesBelow max =
let primeGenerator candidate =
if candidate > max then
None
elif candidate = 2 then
Some(2,3)
else
let next = nextPrime candidate
if next >= max then
None
else
Some(next,next+2)

Seq.unfold primeGenerator 2

[<Literal>]
let target = 1000000

let primes = getPrimesBelow target |> List.ofSeq
``````

Now we have a list of primes. The plan of attack is to go through each and find the starting prime of the sequence that, when summed, adds up to a prime number `n`.

``````let isSumOfConsecutivePrimes n =
let rec isSum candidates sum len =
match candidates with
| [] -> None
| x::xs ->
let newSum = sum + x
let newLen = len + 1
if newSum = n then Some(newLen)
elif newSum > n then None
else
isSum xs newSum newLen

let rec findStartingPrime candidates =
match candidates with
| [] -> None
| x::_ when x > n -> None
| x::_ when x = n -> Some(n,1)
| x::xs ->
match isSum xs x 1 with
| Some l -> Some(n,l)
| _ -> findStartingPrime xs

findStartingPrime primes
``````

`isSumOfConsecutivePrimes` starts by looping through each prime and determining if that prime is the start of the sequence we're looking for. The internal function `isSum` takes the list of subsequent primes, the current sum, and the length of the current sequence. If it gets to the end of the list of primes, it returns `None`. Otherwise, if it hits the sum we're looking for, it returns the length of the sequence that generated the sum.

This is a brute force way of solving the problem. I am certain there are other, better ways to do it. But this one works.

Full disclosure: in order to get this to run under the 1-minute time limit, I had to compile it with full code optimizations turned on. To get it to run in under a minute in FSI, I had to run it in parallel.

Here is the single-threaded code that returns the answer:

``````#time
primes
|> Seq.map isSumOfConsecutivePrimes
|> Seq.choose (fun x -> x)
|> Seq.maxBy (fun (_,len) -> len)
|> fst
#time
``````

And here's the parallel version:

``````let isSumOfConsecutivePrimesAsync n = async {
return isSumOfConsecutivePrimes n
}

#time
primes
|> Seq.map isSumOfConsecutivePrimesAsync
|> Async.Parallel
|> Async.RunSynchronously
|> Seq.choose(fun x -> x)
|> Seq.maxBy (fun (_,len) -> len)
|> fst
#time
``````
Other Posts in This Series