2011-03-08

Project Euler problem 139 - Solved

Comments

The problem statement is located here.

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.

The code in python is problem139.py:

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)
comments powered by Disqus