Project Euler Solution #39: Integer right triangles

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

Solution

From the problem statement we know that \(a^2+b^2=c^2\) and \(a+b+c=p\) as well as \(p\leq 1000\). We use these information to calculate the boundaries of \(a\) and \(b\) by choosing the minimal value of the respective opposite value. First we set \(a:= 0\) and after that \(b:= 0\):

\[\begin{array}{rl} & 0+b+c \leq p\\ \Leftrightarrow & 0+b+\sqrt{0^2+b^2} \leq 1000\\ \Leftrightarrow & b+\sqrt{b^2} \leq 1000\\ \Leftrightarrow & b \leq \frac{1000}{2}\\ \end{array}\]

The same applies analogously to \(a\). Searching for the solution can then be implemented as a quadratic search over the bounds with the check of a possible square (without taking 500 itself into account, since sides of length 0 are not possible):

function solution(n) {
  var h = {};
  for (var a = 0; a < n/2; a++)
    for (var b = 0; b < n/2; b++) {
      c = Math.sqrt(a * a + b * b);
      if (c % 1 == 0 && a + b + c <= n)
        h[a + b + c] = (h[a + b + c] || 0) + 1;
   }

  var max = 0, maxp = null;
  for (var p in h) {
    if (max < h[p]) {
      max = h[p];
      maxp = p;
    }
  }
  return +maxp;
}

But we can do a bit better by rewriting the given equations. We know that \(c=p-a-b\) and plugging it into the pythagorean equation yields

\[a^2+b^2=(p-a-b)^2 = p^2+a^2+b^2-2pa-2pb+2ab\]

Solving this equation for \(b\) yields

\[b=\frac{p^2-2pa}{2(p-a)}\]

As long as \(b\) becomes an integer we know that any triangle with the parameters \(a\) and \(p\) will result in an pythagorean triplet. When we analyze the properties of the pythagorean equation, we know if \(a\) and \(b\) are even also \(c\) and as such \(p\) must be even. If either \(a\) or \(b\) is odd, also \(c\) will be odd and \(p\) is even again. The same is true for the last case when \(a\) and \(b\) are odd, \(c\) becomes even and thus \(p\) is even. It follows that \(p\) is always even and we can skip all odd numbers. Furthermore we know that \(a<c\) and \(b<c\). We can also assume that \(a\leq b\), since we could exchange the variables with eachother otherwise. It follows that \(a\leq b<c\), which implies that \(a<\frac{p}{3}\) and all \(a\)'s higher than that limit are not necessary to check. Implementing this improved algorithm leads to

function solution(n) {
  var max = 0, maxp = null;
  for (var p = 2; p <= n; p+= 2) {
    var c = 0;
    for (var a = 2; a < p / 3; a++) {
      if (p * (p - 2 * a) % (2 * (p - a)) == 0)
        c++;
    }
    if (c > max) {
      max = c;
      maxp = p;
    }
  }
  return maxp;
}