Project Euler — Problem 87 Solution

Problem

The small­est num­ber express­ible as the sum of a prime square, prime cube, and prime fourth pow­er is 28. In fact, there are exact­ly four num­bers below fifty that can be expressed in such a way:

28 = 22 + 23 + 24

33 = 32 + 23 + 24

49 = 52 + 23 + 24

47 = 22 + 33 + 24

How many num­bers below fifty mil­lion can be expressed as the sum of a prime square, prime cube, and prime fourth pow­er?

Solution

// generate all prime numbers under <= this max
let max = int64(sqrt(double(50000000L)))

// initialise the list with 2 which is the only even number in the sequence
let mutable primeNumbers = &#91;2L&#93;

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

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

// populate the prime numbers list
for n in potentialPrimes do if not(hasDivisor n) then primeNumbers <- primeNumbers @ &#91;n&#93;

// use the same hasDivisor function instead of the prime numbers list as it offers
// far greater coverage as the number n is square rooted so this function can
// provide a valid test up to max*max
let isPrime n = if n = 1L then false else not(hasDivisor(n))

let answer =
    primeNumbers
    |> Seq.collect (fun n ->
        primeNumbers 
        |> Seq.map (fun n' -> pown n 2 + pown n' 3) 
        |> Seq.takeWhile (fun sum -> sum < 50000000L))
    |> Seq.collect (fun sum ->
        primeNumbers 
        |> Seq.map (fun n -> sum + pown n 4) 
        |> Seq.takeWhile (fun sum' -> sum' < 50000000L))
    |> Seq.distinct
    |> Seq.length

The biggest prime that can appear in the equa­tion is equals to the square root of 50000000 – 8 – 16, which, inci­den­tal­ly is just over 7000, so the num­bers of primes involved is rea­son­ably small which bodes well for a fast solu­tion!

The log­ic in this solu­tion is oth­er­wise sim­ple, using the cached prime num­bers list to first gen­er­ate num­bers (< 50 mil­lion) that can be writ­ten as the sum of a prime square and prime cube; then for each num­ber see if we can add a prime fourth pow­er and get a sum less than 50 mil­lion.

One thing that caught me out ini­tial­ly was the need to search for dis­tinct num­bers as some of these num­bers do over­lap, but oth­er­wise this is a solu­tion which runs hap­pi­ly under 3 sec­onds.