Skip to content

Project Euler Problem 87

July 31, 2012

Solving Project Euler Problem 87 was very straightforward.
Reusing primes sequence from solution to Project Euler Problem 10 limit it from up by TOPPRIME. Then build arrays of squares, cubes and powers of 4, similarly limited by TOPSUM. Finally, produce all possible sums of elements of these arrays, one of each, that again are limited by TOPSUM, accounting for unique values with the help of HashSet unique. Power of unique gives the problem solution.

#nowarn "40"

let rec primes =
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
and nextPrime n =
     if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
and isPrime n =
    if n >= 2 then
        primes
        |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
        |> fun x -> x.Value * x.Value > n
    else false

let TOPSUM = 50000000L
let TOPPRIME = int(sqrt (float TOPSUM))

let problem087() =
    let candidates = primes |> Seq.takeWhile (fun x -> x <= TOPPRIME) |> Seq.map int64
    let squares = candidates |> Seq.map (fun x -> x * x) |> Seq.toArray
    let cubes =
        candidates
        |> Seq.map (fun x -> x * x * x)
        |> Seq.takeWhile (fun x -> x < TOPSUM) |> Seq.toArray
    let fours =
        squares
        |> Seq.map (fun x -> x * x)
        |> Seq.takeWhile (fun x -> x < TOPSUM) |> Seq.toArray

    let unique = System.Collections.Generic.HashSet()
    for i in [0..squares.Length-1] do
        for j in [0..cubes.Length-1] do
            for k in [0..fours.Length-1] do
                let sum = squares.[i] + cubes.[j] + fours.[k] in
                    if sum <= TOPSUM then unique.Add(sum) |> ignore
    unique.Count
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: