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)Voila!