Post a Comment On: Scattered Thoughts

I find myself somewhat obsessed with Project Euler these days. It contains a series of math challenges that (mostly) require a computer program of some sort to find the right answer. If you start looking around the web there seems to be a tradition of using these problems as a way to learn a new programming language. And that's what I'm doing too. My language of choice is F#.

The first problem in the project is:

Add all the natural numbers below one thousand that are multiples of 3 or 5.

I have come up with four solutions. Here's number one:

seq {for i in 0..999 do if i%3=0 or i%5=0 then yield i} |> Seq.sum |> printfn "total = %A"

Solution number two is to sum the sequence of integer multiples of 3 and 5 and then subtract the overlap (the sum of the multiples of 15). That would look like this:

({3..3..999} |> Seq.sum) + ({5..5..999} |> Seq.sum) - ({15..15..999} |> Seq.sum) |> printfn "total = %A"

The third solution is another variation on the theme of summing a sequence:

seq {1..999} |> Seq.filter (fun k -> k%3=0 or k%5=0) |> Seq.sum |> printfn "total = %A"

Finally, solution number four comes from noting that the sum from k to n of the multiples of k can be written like this:

[Image]
With some tweaking to get the end of the series correct I translated the math into F# as follows:

let sigma k n = 
    let m = k*((n-1)/k)
    (m*(m+k))/(2*k)

In this case m is the largest integer less than n that needs to be included in the sum (this is not the same as n since the problem states that we are looking at numbers below one thousand). With this helper function the solution to the problem becomes:

(sigma 3 1000) + (sigma 5 1000) - (sigma 15 1000) |> printfn "total = %A"

To time these solutions I used the #time functionality of F# Interactive.

Solution 1 took 00:00:00.010.
Solution 2 took 00:00:00.011.
Solution 3 took 00:00:00.024.
Solution 4 took 00:00:00.003.

It's not at all clear to me why the third solution is two times slower than the first two. As expected the fourth solution is by far the fastest.

And that's way too much analysis for such a simple problem.