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