Project Euler in F#: Problem 21

Evaluate the sum of all the amicable numbers under 10000.

    let sumOfDivisors n = seq {for m in 2..int(sqrt(float n)) do if n % m = 0 then yield! [m;n/m]} |> Seq.sum |> (+) 1
    let ans = {1..10000} |> Seq.filter (fun n -> sumOfDivisors (sumOfDivisors n) = n && sumOfDivisors n <> n) |> Seq.sum

The naive solution I came up for this returns a sequence of pairs. I’m not sure what the idiomatic and/or efficient solution is in F#, so I just yield!ed the pair as a list. Any F# experts have a better way?

I should add a disclaimer that while this sum of divisors function works for this problem, it’s actually wrong for perfect squares, just in case anyone stumbles on this code and tries to use it.

After seeing how explicitly calling DivRem sped up problem 16, I wondered if explicitly saving the sum would speed this up.

    let sumOfDivisors n = seq {for m in 2..int(sqrt(float n)) do if n % m = 0 then yield! [m;n/m]} |> Seq.sum |> (+) 1
    let amicable n =
        let m = sumOfDivisors n
        n = sumOfDivisors m && m <> n
    let ans = {1..10000} |> Seq.filter amicable |> Seq.sum

But this gives the exact same performance; I guess the compiler does the optimization automatically.

Advertisements
Project Euler in F#: Problem 21

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