## 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.

Tyler MacLeodFebruary 23rd, 2008 - 21:22

Or one line…

[1...1000] |>

List.filter (fun x -> x % 3 = 0 or x % 5 = 0) |>

List.fold_left (+) 0;;