Project Euler Problem 139

# Statement

Let (a, b, c) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length c.

For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares.

However, if (5, 12, 13) triangles were used then the hole would measure 7 by 7 and these could not be used to tile the 13 by 13 square.

Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?

# Solution

I used the same technique as in problem 75 to generate all the primitive triplets below the given limit.

If the remainder of the hypotenuse divided by the difference of the catheti equals 0 then in all the deriving triangles based on that triple the property will hold true.
To determine how many triangles derived from that triplet exists below the limit, we just divide the limit by the perimeter of the base triangle.

```from itertools import takewhile, count
from fractions import gcd

LIMIT = 100000000

if __name__ == '__main__':
result = 0
generator = ((n, m) for n in count(3, 2) for m in range(1, n, 2) if gcd(m,n) == 1)
for n, m in generator:
a = m * n
b = (n ** 2 - m ** 2) // 2
c = (n ** 2 + m ** 2) // 2
perimeter = a + b + c
if perimeter > LIMIT and m == 1:
break

if c % (b - a) == 0:
result += LIMIT // (a + b + c)
print("The result is", result)
```