(2 votes, average: 4.50 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 our analysis:

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

No matter which integral values we choose for a, b and c such that a2 + b2 = c2 the perimeter will be even.

By iterating perimeters we need a method to check for integral (integer) right triangles.
We can interpret the Pythagorean theorem as a2 + b2 = (p-a-b)2 since c = p-a-b. After expanding and simplifying we have:
b = p(p – 2a) / 2(p-a) and when this equation evaluates to an integer (MOD(p(p – 2a), 2(p-a)) = 0) we have our triangle.

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

#### Solution

Runs < 0.02 seconds in Python.

 L = 10000 t_max = 0   for p in range(L/2, L+1, 2): t = 0 for a in range(2, p/4 + 1): if p*(p - 2*a) % (2*(p-a)) == 0: t += 1 if t > t_max: t_max, p_max = t, p   print "Answer to PE39 = ", p_max

• 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
1,000,000,000 = 2417775360

## Discussion

### 5 Responses to “Project Euler 39”

1. 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
2. Well, I do see it finding 210, but you’re right about 240. Not sure what went into that optimization but your change did work. I’m just not sure why. I need to think about this and figure out what happened.

Thanks, as always, for your astute and thoughtful contributions.

Posted by Mike | March 3, 2011, 1:20 PM
3. 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 get.

Posted by Francky | May 5, 2011, 10:52 AM