Problem 9

Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, $a < b < c$ , for which,
$a^2 + b^2 = c^2$
For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$ .
There exists exactly one Pythagorean triplet for which $a + b + c = 1000$ .
Find the product $abc$ .

https://projecteuler.net/problem=9

Brute Force

function euler9() {
  var a, a2, b, b2, c, c2;
  c = 3;
  while (true) {
    c2 = c*c;
    for (b = 2; b < c; b++) {
      b2 = b*b;
      for (a = 1; a < b; a++) {
        a2 = a*a;
        if (a2 + b2 === c2 && a + b + c === 1000) {
          return a*b*c;
        }
      }
    }
    c++;
  }
}
timer(euler9);
// euler9 x 1: 24.132ms
// 31875000

Starting Point

Because we are looking for $a+b+c=1000$ , and $a<b<c$ we can determine a starting point for $c>335$ . If $c = 334$ then the max value for $b = 333$ and $a = 332$ , which is less than $1000$ .

function euler9() {
  var a, a2, b, b2, c, c2;
  c = 335;
  while (true) {
    c2 = c*c;
    for (b = 2; b < c; b++) {
      b2 = b*b;
      for (a = 1; a < b; a++) {
        a2 = a*a;
        if (a2 + b2 === c2 && a + b + c === 1000) {
          return a*b*c;
        }
      }
    }
    c++;
  }
}
timer(euler9);
// euler9 x 1: 13.301ms
// 31875000

# Time O(n^3)

Using the Requirements

We are still checking a bunch of numbers that can’t be an answer.

$1000 = a + b + c$ , so $1000 - c = a + b$ , and $1000 - c - b = a$ . That means we only need to check one value of $a$ per value of $b$ . We still need to check every value of $b$ less than $c-1$ , that is until $a > b$ , further reducing the values we have to check.

function euler9() {
  var a, a2, b, b2, c, c2;
  c = 335;
  while (true) {
    c2 = c*c;
    b = c - 1;
    a = 1000 - c - b;
    while (a < b) {
      a2 = a*a,
      b2 = b*b;
      if (a2 + b2 === c2) {
        return a*b*c;
      }
      a++;
      b--;
    }
    c++;
  }
}
timer(euler9);
// euler9 x 1: 0.029ms
// 31875000

# Time O(n^2)

Euclid’s formula

For a pythagorean triplet,
$$a = m^2 - n^2 ,\ \, b = 2mn ,\ \, c = m^2 + n^2\; \text{where}\; m > n$$ and because our problem requires $a+b+c=1000$, $$\begin{align*} m^2 -n^2 + 2mn + m^2 + n^2 & = 1000 \\ 2m^2 + 2mn & = 1000 \\ 2m(m+n) & = 1000 \\ m(m+n) & = 500 \\ n & = (500 \div m) - m \end{align*}$$

function euler9() {
  var m, n;
  m = 2;
  while (true) {
    if (500 % m === 0 && 500 / m - m < m) break;
    m++;
  }
  n = 500 / m - m;
  return (m * m - n * n) * (2 * m * n) * (m * m + n * n);
}
timer(euler9);
// euler9 x 1: 0.006ms
// 31875000