# Project Euler 39 Solution: Integer right triangles

Problem 39

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;
}

« Back to problem overview