Problem 039

Project Euler

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 maximized?

 Again, the larger the number, the number of solutions should also increase in general. Therefore, we’ll start will the maximum number ( p ≤ 1000) and count backward.

We can cut the search space smaller by recognize the following triangle with a, b, c.

a + b < c
a + b + c = p
Therefore, search a between 1 to \frac{p}{2} and search b between a+1 to \frac{p}{2} in a nested loop to ensure no repeat combination of a and b. Then, increment the number of solution for a specific c by solving c base on a and b using the equations from above. Since p ≤ 1000, then c ≤ 998. At the end, find the c with the most solution.