Desperately seeking Pythagoras

Also known as Project Euler 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 maximised?

My first thought here was to generate an iterable collection of right angled triangles and accumulate a count of triangles by perimeter size. Don’t try this – it is far too slow an approach.

So my second thought was to try and iterate over the perimeter sizes and calculate the number of right angle triangles for each. It’s a long time since I had to think about Pythagoras but, for a triangle with sides a, b and c and a perimeter of p, I can make the following two statements:

a + b + c = p
a^2 + b^2 = c^2

Based on the second statement, above, I can also assert:
c = sqrt(a^2 + b^2)

Also:
c = p - a - b

Which means:
a^2 + b^2 = (p - a - b)^2

This can be expanded and simplified to state:
0 = pp - 2pb - 2ap + 2ab

or:

b = p(p - 2a) / 2(p - a)

Using this formula, we can say that for any values of p and a where p > a, if b is an integer then we have a right angle triangle.

One further optimisation: Intuitively, a can’t be greater than p/3.

Implementing this can then be done with two very simple for loops. The outer one iterates over all values of p and the inner one iterates over the range (2, int(p / 3)) and counts the number of integer values of b.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s