This little list comprehension in Haskell will find the Pythagorean triple specified in Problem 9:
[ (a, b, c) | c <- [1..], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a + b + c == 1000 ] !! 0
This is equivalent to taking the first element of
![\{ (a, b, c) \; | \; c \in \mathbb{N}, b \in [1, c] \cap \mathbb{N}, a \in [1, b] \cap \mathbb{N}, a^2 + b^2 = c^2, a + b + c = 1000 \}](http://s0.wp.com/latex.php?latex=%5C%7B+%28a%2C+b%2C+c%29+%5C%3B+%7C+%5C%3B+c+%5Cin+%5Cmathbb%7BN%7D%2C+b+%5Cin+%5B1%2C+c%5D+%5Ccap+%5Cmathbb%7BN%7D%2C+a+%5Cin+%5B1%2C+b%5D+%5Ccap+%5Cmathbb%7BN%7D%2C+a%5E2+%2B+b%5E2+%3D+c%5E2%2C+a+%2B+b+%2B+c+%3D+1000+%5C%7D&bg=ffffff&fg=4c4c4c&s=0 "\{ (a, b, c) \; | \; c \in \mathbb{N}, b \in [1, c] \cap \mathbb{N}, a \in [1, b] \cap \mathbb{N}, a^2 + b^2 = c^2, a + b + c = 1000 \}")
.
Notice how close to mathematical notation the Haskell code is. Now, this code is not very fast; it instructs the computer to build a list of every triple of naturals (a, b, c) such that the triple is a Pythagorean triple and the sum of each element of the triple is 1000, starting at (1, 1, 1), (2, 1, 1), (2, 2, 1), (2, 2, 2)….
Here’s the gist.
Update. To the commenters on Reddit: Perhaps I should have been more clear about my experience here. I had just begun to learn Haskell and, having solved this problem already with the use of Euclid’s formula, I saw in the Haskell tutorial I was reading that one could solve this problem with a simple list comprehension, which struck me as beautiful in the sense of its simplicity and similarity to the normal set comprehension definition of the problem. Indeed, a faster implementation with a list comprehension would be
head [ (a, b, c) | c <- [1..], b <- [1..c], let a = 1000 - b - c, a^2 + b^2 == c^2 ]
One simple optimization is to remove one of the guards and only range over two variables, using the information that was encoded in the guard to determine the third variable. E.g., [ (a, b, c) | c <- [1..], b <- [1..c], let a = 1000 – b – c, a^2 + b^2 == c^2] !! 0
I realize this loses some of the beautiful symmetry with how you'd normally write it as a mathematical set comprehension
By the way, the notation [1,x] normally means the subset of R of numbers y such that 1 <= y <= x. A more mathematically conventional way of writing your set would be to use:
b \in [1,c] \cap \mathbb{N}
instead of simply b \in [1,c]. (And similarly for a.)
@David:
Ah, yes, that’s true.