Project Euler Problem 75 - Solved

The statement for this problem is here.

The solution is quite easy once you know how to generate Pythagorean triplets efficiently. To achieve this you need to know about Euclid's formula to generate primitive Pythagorean triplets.

Using that formula is easy to generate all the triplets, we continue to do so until we find a triplet whose m is 1 and the perimeter exceeds the LIMIT.

For each of the primitive triplets we generate all the derivative ones multiplying them with 1, 2, .., x until it the perimeter exceeds the LIMIT.

With each of the perimeters generated I add them to a set and if found on that set, add them to another.

When all the generation is finished, the result is the elements in the difference between the first and the latter sets.

The solution in python is problem075.py:

from itertools import takewhile, count
from fractions import gcd

LIMIT = 1500000

if __name__ == '__main__':
    found_per = set()
    rep_per = set()
    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 m == 1 and perimeter > LIMIT:
            break

        for per in takewhile(lambda x: x <= LIMIT, (perimeter * i for i in count(1))):
            if per in found_per:
                rep_per.add(per)
            else:
                found_per.add(per)

    print("The result is", len(found_per - rep_per))