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 | c | p | |
| 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 = p–a–b, we can interpret the Pythagorean theorem as a2 + b2 = (p-a-b)2 . After expanding and simplifying we have:
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:
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, :
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 AMHi,
Since I wrote this solution there have been many improvements and better explanations that I could possibly conjure.
Here is a link that answers your question and takes solving this problem many steps further.
http://mathematica.stackexchange.com/questions/10001/how-to-improve-the-performance-of-solutions-to-project-euler-39
Thanks
Posted by Mike Molony | June 3, 2015, 10:29 PMif 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 AMGood suggestion. It did improve performance some.
Posted by Mike | May 12, 2011, 3:36 PMWould you mind explaining the floor division on limit and then times two?
Posted by john | January 24, 2017, 8:07 PMThe 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 PMI 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