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: a^{2} + b^{2} = c^{2} 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 a^{2} + b^{2} = c^{2} 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 a^{2} + b^{2} = (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, Project Euler 75 Solution:
Can you please explain why we need to investigate values only till p/(2 + sqrt(2))?
Hi,
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
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.
Good suggestion. It did improve performance some.
Would you mind explaining the floor division on limit and then times two?
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.
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 . . .