FSharp, Euler 9

24 May 2008

The problem statement:

A Pythagorean triplet is a set of three natural numbers,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

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

Find the product abc.

This is another one that’s probably really more “math”-y than programming-y, but I’m enjoying using my new F# hammer to solve these, so might as well keep at it.

It seems like another nice make-a-sequence-and-then-filter-it, but just doing 1..1000 for a, b, and c, results in an awfully big sequence (a billion long). So, a couple simple observations to make the numbers a lot smaller. The main one is that you can just make c = 1000 - a - b, since we know that all answers have to have that form anyway.

seq { for a in 1..1000 do
        for b in a..1000 do
            let c = 1000 - a - b
            yield (a,b,c) }
|> Seq.first(fun (a,b,c) -> if a*a + b*b = c*c then Some(a,b,c) else None)