Claudio Cherubino's blogLife of a Googler

23Jan/082

Project Euler in F# – Problem 6

The exercises proposed by Project Euler are ordered by difficulty, and the one I'll discuss today is ranked sixth.

However, I think it is one of the easiest to solve, since it doesn't require any trick and the solution is already written in its text:

The sum of the squares of the first ten natural numbers is,
1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 ? 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

We just have to evaluate two formulas and then perform a subtraction, so let's go directly to the F# code:

```#light
let numbers = [1 .. 100]

let diff =
(numbers |> Seq.fold (+) 0 |> (fun x -> x*x)) -
(numbers |> Seq.sumByInt (fun x -> x*x))
```

You should already know the pipeline operator, which is massively used in F#.

Seq.fold is used to apply a function (in our case the sum operator) to all the elements of a collection (i.e. the list of numbers) starting from a base value that we set equal to zero.

Then we pass the result to a function that takes a number and returns its square, actually giving us the square of the sum of the first 100 numbers.

In the next line of the diff function we evaluate the sum of the squares of the first 100 numbers.

It is done thanks to the Seq.sumByInt function that returns the sum of the results generated by applying the given function (i.e. the square function) to each element of the collection.

That's it, no tricks and no special mathematical knowledge required, I told you!

1. With some cleverness the expression (x_1^2 .. x_100^2) – (x_1 .. x_2)^2 can be simplified to the sum of x_i*x_j, where i ranges from [1 .. 100] and j > i.

Example: (a + b)^2 – (a^2 + b^2) = 2ab.
Exameple: (a + b + c)^2 – (a^2 + b^2 + c^2) = 2(ab+ac+bc)

The following uses this simplification:

#light
let rec diff2 l =
match l with
| [] -> 0
| _ -> 2 * List.sumByInt (fun x -> List.hd l * x) (List.tl l) + diff2 (List.tl l)
diff2 [1 .. 100]

2. Of course I meant the expression (x_1 + .. + x_2)^2 – (x_1^2 + .. + x_100^2) , not (x_1^2 .. x_100^2) – (x_1 + .. + x_2)^2