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