TheAlgorithms-Python

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

4
For any integer n, consider the three functions
5

6
f1,n(x,y,z) = x^(n+1) + y^(n+1) - z^(n+1)
7
f2,n(x,y,z) = (xy + yz + zx)*(x^(n-1) + y^(n-1) - z^(n-1))
8
f3,n(x,y,z) = xyz*(xn-2 + yn-2 - zn-2)
9

10
and their combination
11

12
fn(x,y,z) = f1,n(x,y,z) + f2,n(x,y,z) - f3,n(x,y,z)
13

14
We call (x,y,z) a golden triple of order k if x, y, and z are all rational numbers
15
of the form a / b with 0 < a < b ≤ k and there is (at least) one integer n,
16
so that fn(x,y,z) = 0.
17

18
Let s(x,y,z) = x + y + z.
19
Let t = u / v be the sum of all distinct s(x,y,z) for all golden triples
20
(x,y,z) of order 35.
21
All the s(x,y,z) and t must be in reduced form.
22

23
Find u + v.
24

25

26
Solution:
27

28
By expanding the brackets it is easy to show that
29
fn(x, y, z) = (x + y + z) * (x^n + y^n - z^n).
30

31
Since x,y,z are positive, the requirement fn(x, y, z) = 0 is fulfilled if and
32
only if x^n + y^n = z^n.
33

34
By Fermat's Last Theorem, this means that the absolute value of n can not
35
exceed 2, i.e. n is in {-2, -1, 0, 1, 2}. We can eliminate n = 0 since then the
36
equation would reduce to 1 + 1 = 1, for which there are no solutions.
37

38
So all we have to do is iterate through the possible numerators and denominators
39
of x and y, calculate the corresponding z, and check if the corresponding numerator and
40
denominator are integer and satisfy 0 < z_num < z_den <= 0. We use a set "uniquq_s"
41
to make sure there are no duplicates, and the fractions.Fraction class to make sure
42
we get the right numerator and denominator.
43

44
Reference:
45
https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem
46
"""
47

48
from __future__ import annotations
49

50
from fractions import Fraction
51
from math import gcd, sqrt
52

53

54
def is_sq(number: int) -> bool:
55
    """
56
    Check if number is a perfect square.
57

58
    >>> is_sq(1)
59
    True
60
    >>> is_sq(1000001)
61
    False
62
    >>> is_sq(1000000)
63
    True
64
    """
65
    sq: int = int(number**0.5)
66
    return number == sq * sq
67

68

69
def add_three(
70
    x_num: int, x_den: int, y_num: int, y_den: int, z_num: int, z_den: int
71
) -> tuple[int, int]:
72
    """
73
    Given the numerators and denominators of three fractions, return the
74
    numerator and denominator of their sum in lowest form.
75
    >>> add_three(1, 3, 1, 3, 1, 3)
76
    (1, 1)
77
    >>> add_three(2, 5, 4, 11, 12, 3)
78
    (262, 55)
79
    """
80
    top: int = x_num * y_den * z_den + y_num * x_den * z_den + z_num * x_den * y_den
81
    bottom: int = x_den * y_den * z_den
82
    hcf: int = gcd(top, bottom)
83
    top //= hcf
84
    bottom //= hcf
85
    return top, bottom
86

87

88
def solution(order: int = 35) -> int:
89
    """
90
    Find the sum of the numerator and denominator of the sum of all s(x,y,z) for
91
    golden triples (x,y,z) of the given order.
92

93
    >>> solution(5)
94
    296
95
    >>> solution(10)
96
    12519
97
    >>> solution(20)
98
    19408891927
99
    """
100
    unique_s: set = set()
101
    hcf: int
102
    total: Fraction = Fraction(0)
103
    fraction_sum: tuple[int, int]
104

105
    for x_num in range(1, order + 1):
106
        for x_den in range(x_num + 1, order + 1):
107
            for y_num in range(1, order + 1):
108
                for y_den in range(y_num + 1, order + 1):
109
                    # n=1
110
                    z_num = x_num * y_den + x_den * y_num
111
                    z_den = x_den * y_den
112
                    hcf = gcd(z_num, z_den)
113
                    z_num //= hcf
114
                    z_den //= hcf
115
                    if 0 < z_num < z_den <= order:
116
                        fraction_sum = add_three(
117
                            x_num, x_den, y_num, y_den, z_num, z_den
118
                        )
119
                        unique_s.add(fraction_sum)
120

121
                    # n=2
122
                    z_num = (
123
                        x_num * x_num * y_den * y_den + x_den * x_den * y_num * y_num
124
                    )
125
                    z_den = x_den * x_den * y_den * y_den
126
                    if is_sq(z_num) and is_sq(z_den):
127
                        z_num = int(sqrt(z_num))
128
                        z_den = int(sqrt(z_den))
129
                        hcf = gcd(z_num, z_den)
130
                        z_num //= hcf
131
                        z_den //= hcf
132
                        if 0 < z_num < z_den <= order:
133
                            fraction_sum = add_three(
134
                                x_num, x_den, y_num, y_den, z_num, z_den
135
                            )
136
                            unique_s.add(fraction_sum)
137

138
                    # n=-1
139
                    z_num = x_num * y_num
140
                    z_den = x_den * y_num + x_num * y_den
141
                    hcf = gcd(z_num, z_den)
142
                    z_num //= hcf
143
                    z_den //= hcf
144
                    if 0 < z_num < z_den <= order:
145
                        fraction_sum = add_three(
146
                            x_num, x_den, y_num, y_den, z_num, z_den
147
                        )
148
                        unique_s.add(fraction_sum)
149

150
                    # n=2
151
                    z_num = x_num * x_num * y_num * y_num
152
                    z_den = (
153
                        x_den * x_den * y_num * y_num + x_num * x_num * y_den * y_den
154
                    )
155
                    if is_sq(z_num) and is_sq(z_den):
156
                        z_num = int(sqrt(z_num))
157
                        z_den = int(sqrt(z_den))
158
                        hcf = gcd(z_num, z_den)
159
                        z_num //= hcf
160
                        z_den //= hcf
161
                        if 0 < z_num < z_den <= order:
162
                            fraction_sum = add_three(
163
                                x_num, x_den, y_num, y_den, z_num, z_den
164
                            )
165
                            unique_s.add(fraction_sum)
166

167
    for num, den in unique_s:
168
        total += Fraction(num, den)
169

170
    return total.denominator + total.numerator
171

172

173
if __name__ == "__main__":
174
    print(f"{solution() = }")
175