TheAlgorithms-Python

1
"""
2
Project Euler Problem 75: https://projecteuler.net/problem=75
3

4
It turns out that 12 cm is the smallest length of wire that can be bent to form an
5
integer sided right angle triangle in exactly one way, but there are many more examples.
6

7
12 cm: (3,4,5)
8
24 cm: (6,8,10)
9
30 cm: (5,12,13)
10
36 cm: (9,12,15)
11
40 cm: (8,15,17)
12
48 cm: (12,16,20)
13

14
In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided
15
right angle triangle, and other lengths allow more than one solution to be found; for
16
example, using 120 cm it is possible to form exactly three different integer sided
17
right angle triangles.
18

19
120 cm: (30,40,50), (20,48,52), (24,45,51)
20

21
Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can
22
exactly one integer sided right angle triangle be formed?
23

24
Solution: we generate all pythagorean triples using Euclid's formula and
25
keep track of the frequencies of the perimeters.
26

27
Reference: https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple
28
"""
29

30
from collections import defaultdict
31
from math import gcd
32

33

34
def solution(limit: int = 1500000) -> int:
35
    """
36
    Return the number of values of L <= limit such that a wire of length L can be
37
    formmed into an integer sided right angle triangle in exactly one way.
38
    >>> solution(50)
39
    6
40
    >>> solution(1000)
41
    112
42
    >>> solution(50000)
43
    5502
44
    """
45
    frequencies: defaultdict = defaultdict(int)
46
    euclid_m = 2
47
    while 2 * euclid_m * (euclid_m + 1) <= limit:
48
        for euclid_n in range((euclid_m % 2) + 1, euclid_m, 2):
49
            if gcd(euclid_m, euclid_n) > 1:
50
                continue
51
            primitive_perimeter = 2 * euclid_m * (euclid_m + euclid_n)
52
            for perimeter in range(primitive_perimeter, limit + 1, primitive_perimeter):
53
                frequencies[perimeter] += 1
54
        euclid_m += 1
55
    return sum(1 for frequency in frequencies.values() if frequency == 1)
56

57

58
if __name__ == "__main__":
59
    print(f"{solution() = }")
60