Claudio Cherubino's blog Life of a Googler

20Jan/081

Project Euler in F# – Problem 1 (alternative solution)

In the last article I presented a naive solution for the first Project Euler problem, that asks us to "find the sum of all the multiples of 3 and 5 below 1000".

There are many different solutions for the same problem and today I want to show an alternative approach, which is based on a mathematical formula for an arithmetic series.

In our first solution we examined all numbers between 1 and 999 and only kept the multiples of 3 and 5, skipping all the others.

Instead of doing this, we just need to generate the multiples of 3 and 5 and sum them, subtracting the multiples of 15 because they will be included twice.

Remembering that the sum of the first n integer numbers is equal to n * (n+1) / 2, we need to adapt this formula to sum the multiples of a given number, i.e. 3, 5 and 15.

Let's call n the the result of the integer division between the maximum value (in our case 999) and step, where step is 3, 5 or 15.

According to this naming, the sum of multiples will be step * n * (n + 1) / 2, and this formula is very easy to translate in F#:

#light
let sum_mult max step =
  let n = max / step
  step*n*(n + 1)/2

let max = 999
let sum = sum_mult max 3 + sum_mult max 5 - sum_mult max 15
print_any sum

At line 2 we define the sum_mult function, which takes two integer arguments this time: max and step.

The next line shows how to define a local identifier called n, whose scope is limited to the sum_mult function.

The rest of the code is straightforward, we apply the formula to sum the multiples of 3 and 5 and subtract those of 15.

Comparing the complexity of this solution with the previous one we can easily see that we moved from O(n), i.e. going through all the elements of the array, to O(1).

In fact, with this approach the number of evaluations is always fixed to 3, regardless of the maximum number to take into account.

Next time we'll face a new problem, I look forward to receiving your comments.

Comments (1) Trackbacks (1)
  1. Or one line…

    [1...1000] |>
    List.filter (fun x -> x % 3 = 0 or x % 5 = 0) |>
    List.fold_left (+) 0;;


Leave a comment

(required)