## Project Euler in F# – Problem 9

Today's exercise is **Project Euler Problem 9**, that says:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Therefore this time we have to find **a triplet** (a, b, c), but a brute-force approach would require **a billion combinations**, since the three numbers can range from 1 to 1000.

However, we can reduce the number of tests exploiting a little algebra.

First of all, *c = 1000 - a - b*, so only two variables are in play, leading us to **a million choices**.

Then we go down to **half a million**, thanks to the constraint that *a < b*.

According to these premises, here is the **F#** code:

#light let sq x = x * x let ab = { for a in 1 .. 1000 for b in a .. 1000 -> a,b } |> Seq.filter (fun (a,b) -> sq a + sq b = sq (1000 - a - b) ) |> Seq.hd let answer = let a = fst ab let b = snd ab let c = 1000 - a - b a * b * c

At line 5 we enumerate all items of a collection created with **list comprehension**, i.e. the numbers between 1 and 1000.

Inside this loop we have another loop, but in this case we are interested in all numbers bigger than the current item of the outer collection, i.e. all numbers between *a* and 1000.

Then, we filter all couples (*a, b*) keeping only those for which we have: *a² + b² = (1000 - a - b)²*.

According to the text of the exercise, there exists exactly one **Pythagorean triplet** that satisfies the equation *a + b + c = 1000*, so we can apply the *Seq.hd* (*head*) function to take the first (and only) element of the generated sequence.

At lines 9, 10 and 11 we evaluate *a*, *b* and *c* and finally we multiply them to get the answer.

### Twitter Updates

- @avalaxy Unfortunately I don't have an ETA. Feel free to submit patches or add suggestions to reach the goal sooner 2012-09-28
- @avalaxy it is planned for the new APIs and the library work is tracked at http://t.co/tAOfAYTA 2012-09-28
- @Sabrina_Miso Prova con uno zaino, non sara' trendy come una borsa, ma almeno le spalle non moriranno :) 2012-09-24
- @duplikey come hai fatto a resistere due giorni? 2012-09-24
- @avalaxy sorry, never tried that on a Metro app. Have you tried building the source instead? 2012-09-09
- More updates...