Robert Eisele
Engineer, Systems Architect and DBA

# Project Euler 9: Special Pythagorean triplet

Problem 9

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

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.

## Solution

A problem like this is perfect for Haskell, since we can transform the mathematical description par for par into a programm:

solution n = head [a * b * c |
c <- [1..n],
b <- [1..c],
a <- [1..b],
a^2 + b^2 == c^2,
a + b + c == n]

However, it takes quite some time to find the solution with this brute force attempt. One improvement is to use the fact that $$a+b+c=n$$ which lets us construct the variable c as $$c=n - a - b$$ (we could construct c as $$c=\sqrt{a^2+b^2}$$, but this is computational much more expensive and of course we could construct a and b but this would require another check if the result becomes negative). This minimal change reduces the execution time tremendously:

solution n = head [a * b * c |
b <- [1..n],
a <- [1..b],
let c = n - a - b,
a^2 + b^2 == c^2]

In order to keep the relation $$a<b<c$$, we would need to add a check of $$b<c$$, but as $$a^2+b^2=c^2 \Rightarrow b<c$$ for $$a>0$$, we can skip this test. But based on the fact that $$a<b<c$$, we can conclude even more, namely that $$a<n/3$$ and $$a<b<n/2$$. With this, we can further improve the search space:

solution n = head [a * b * c |
a <- [1..quot n 3],
b <- [a..quot n 2],
let c = n - a - b,
a^2 + b^2 == c^2]

We learned quite a lot already, but the search space is still too large, so back to the drawing board.We know $$a+b=n-c$$ and $$a^2+b^2=c^2$$, which implies that $$2ab = (n-c)^2 - c^2$$. When subtracting the two equations, we get $$a^2 - 2ab + b^2 = c^2 - (n-c)^2 + c^2 = c^2 - n^2 + 2nc$$. Since $$(a-b)^2 = c^2 - n^2 + 2nc$$, we know the right part must be square. We achieved, that we completely removed a and b! As we constructed the triplet this way, we find a solution if the integer square root exists and the result will be maximized as $$abc = n(n/4)^2 - n(c - n/4)^2$$.

solution n = head [ a * b * c |
c <- [1 + quot n 3 .. quot n 2],
let sqa_b = c * c - n * n + 2 * n * c,
let a_b = floor(sqrt(fromIntegral sqa_b)),
let b = quot (n - c + a_b) 2,
let a = n - b - c,
a_b * a_b == sqa_b]

Or the same implemented in JavaScript:

function solution(n) {

for (var c = (n / 3 + 1) | 0; c < n / 2; c++) {

var sqa_b = c * c - n * n + 2 * n * c
var a_b = Math.floor(Math.sqrt(sqa_b));

if (a_b * a_b == sqa_b) {
var b = (n - c + a_b) / 2;
var a = n - b - c;
return a * b * c;
}
}
return -1
}
solution(1000);


Go to overview