Project Euler — Problem 50 Solution

Problem

The prime 41, can be writ­ten as the sum of six con­sec­u­tive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of con­sec­u­tive primes that adds to a prime below one-hun­dred.

The longest sum of con­sec­u­tive primes below one-thou­sand that adds to a prime, con­tains 21 terms, and is equal to 953.

Which prime, below one-mil­lion, can be writ­ten as the sum of the most con­sec­u­tive primes?

Solution

// generate all prime numbers under <= this max
let max = 10000

// initialise the list with 2 which is the only even number in the sequence
let mutable primeNumbers = [2]

// only check the prime numbers which are <= the square root of the number n
let hasDivisor n =
    primeNumbers
    |> Seq.takeWhile (fun n' -> n' <= int(sqrt(double(n))))
    |> Seq.exists (fun n' -> n % n' = 0)

// only check odd numbers <= max
let potentialPrimes = Seq.unfold (fun n -> if n > max then None else Some(n, n+2)) 3

// populate the prime numbers list
for n in potentialPrimes do
    if not(hasDivisor n) then primeNumbers  Seq.filter (fun n' -> n' > n)
    |> Seq.scan (fun (sum, count) n' -> (sum+n', count+1)) (n, 1)
    |> Seq.takeWhile (fun (sum, count) -> sum < 1000000)
    |> Seq.filter (fun (sum, count) -> isPrime sum)
    |> Seq.maxBy (fun (sum, count) -> count)

// for all numbers, find the longest sequence
let answer = primeNumbers |> Seq.map getPrimeSequence |> Seq.maxBy (fun (sum, count) -> count)

Again, uti­liz­ing the PGsim­ple 3 algo­rithm from here, this solu­tion runs in just over a sec­ond as I’ve restrict­ed it to check sequences start­ing with a prime < 10000 which per­haps unsur­pris­ing­ly, has pro­vid­ed me with the answer.

The only tricky part in this prob­lem is how to build up a list of sequences for each start­ing prime and find the longest sequence start­ing from that num­ber which results in a prime < 1000000. For­tu­nate­ly you can do this rather eas­i­ly with Seq.scan in F# which works sim­i­lar­ly to Seq.fold but gives you all the inter­me­di­ate results as well as the final result. Used in con­junc­tion with Seq.takeWhile it allows me to get all the sequences which sums up to a num­ber less than 1000000. The rest is pret­ty straight for­ward, fil­ter out the sums that aren’t prime num­bers and find the longest sequence, and do this for all the primes we have gen­er­at­ed to find the answer to the prob­lem.