Project Euler Problem 139


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?


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:
        if c % (b - a) == 0:
            result += LIMIT // (a + b + c)
    print("The result is", result)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License