Statement
It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.
- 12 cm: (3,4,5)
- 24 cm: (6,8,10)
- 30 cm: (5,12,13)
- 36 cm: (9,12,15)
- 40 cm: (8,15,17)
- 48 cm: (12,16,20)
In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.
- 120 cm: (30,40,50), (20,48,52), (24,45,51)
Given that L is the length of the wire, for how many values of L <= 1,500,000 can exactly one integer sided right angle triangle be formed?
Solution
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.
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))
The Python file is available for download here.