(15 votes, average: 4.93 out of 5)

Project Euler 39: Maximize the number of solutions for which the value of the perimeter, p, of a right angle triangle ≤ 1000

Problem Description

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?

Analysis

The Pythagorean Theorem gives us: a2 + b2 = c2 and by intuition a + b + c = p (perimeter).
The decision to iterate perimeters has many advantages over generating right triangles. Only even numbered perimeters need to be checked; below is my analysis:

Independent Dependent a b E E E E O O E E E O O E O E E E

No matter which integer values we choose for a, b and c such that a2 + b2 = c2 the perimeter will be even. That is, you can’t possibly have an odd perimeter.

By iterating perimeters we need a method to check for integral (integer) right triangles.
Since c = pab, we can interpret the Pythagorean theorem as a2 + b2 = (p-a-b)2 . After expanding and simplifying we have:

$b = \frac{p(p-2a)}{2(p-a)},$

and when this equation evaluates to an integer we found a target triangle.

One last optimization. By using a+b>c and symmetry we only need to investigate values of a to:

$\frac{p}{2 + \sqrt2}$

Reading the comments below, this solution was reformulated to produce all the triangles that contribute to the maximum in addition to finding the max.

Project Euler 39 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 39 Solution Python 2.7 source.

Afterthoughts

• Some other results:
10,000 = 9,240
100,000 = 55,440
1,000,000 = 720,720
10,000,000 = 6,126,120
100,000,000 = 77,597,520
• See also, Project Euler 75 Solution:
Project Euler 39 Solution last updated

Discussion

7 Responses to “Project Euler 39 Solution”

1. Can you please explain why we need to investigate values only till p/(2 + sqrt(2))?

Posted by Manav Aggarwal | May 26, 2015, 9:29 AM
2. if p got n solutions, then 2p will either get n ones or more.

So :
for p in range(limit//4*2, limit+1, 2):
increase speed by x2.

Thanks for all that you give.

Posted by Francky | May 5, 2011, 10:52 AM
3. The initial solution was built to find the max and not the specific triangles. But I’ve changed it to find all the contributing triangles. Thanks.

Posted by Mike | March 3, 2011, 1:20 PM
4. I think p/4 must be p/(2+sqrt(2))
otherwise you miss the last two.

p=840, {40,399,401}
p=840, {56,390,394}
p=840, {105,360,375}
p=840, {120,350,370}
p=840, {140,336,364}
p=840, {168,315,357}
p=840, {210,280,350} <–
p=840, {240,252,348} <–
Problem39 = 840 elapsed time: 1 ms. Test Passed.
Press any key to continue . . .

Posted by Rudy | March 1, 2011, 2:15 PM