project euler problem 234 https projecteuler netproblem234 for any integer n consider the three functions f1 nx y z xn1 yn1 zn1 f2 nx y z xy yz zxxn1 yn1 zn1 f3 nx y z xyzxn2 yn2 zn2 and their combination fnx y z f1 nx y z f2 nx y z f3 nx y z we call x y z a golden triple of order k if x y and z are all rational numbers of the form a b with 0 a b k and there is at least one integer n so that fnx y z 0 let sx y z x y z let t u v be the sum of all distinct sx y z for all golden triples x y z of order 35 all the sx y z and t must be in reduced form find u v solution by expanding the brackets it is easy to show that fnx y z x y z xn yn zn since x y z are positive the requirement fnx y z 0 is fulfilled if and only if xn yn zn by fermat s last theorem this means that the absolute value of n can not exceed 2 i e n is in 2 1 0 1 2 we can eliminate n 0 since then the equation would reduce to 1 1 1 for which there are no solutions so all we have to do is iterate through the possible numerators and denominators of x and y calculate the corresponding z and check if the corresponding numerator and denominator are integer and satisfy 0 znum zden 0 we use a set uniquqs to make sure there are no duplicates and the fractions fraction class to make sure we get the right numerator and denominator reference https en wikipedia orgwikifermat27slasttheorem check if number is a perfect square issq1 true issq1000001 false issq1000000 true given the numerators and denominators of three fractions return the numerator and denominator of their sum in lowest form addthree1 3 1 3 1 3 1 1 addthree2 5 4 11 12 3 262 55 find the sum of the numerator and denominator of the sum of all sx y z for golden triples x y z of the given order solution5 296 solution10 12519 solution20 19408891927 n1 n2 n1 n2 check if number is a perfect square is_sq 1 true is_sq 1000001 false is_sq 1000000 true given the numerators and denominators of three fractions return the numerator and denominator of their sum in lowest form add_three 1 3 1 3 1 3 1 1 add_three 2 5 4 11 12 3 262 55 find the sum of the numerator and denominator of the sum of all s x y z for golden triples x y z of the given order solution 5 296 solution 10 12519 solution 20 19408891927 n 1 n 2 n 1 n 2
from __future__ import annotations

from fractions import Fraction
from math import gcd, sqrt


def is_sq(number: int) -> bool:
    
    sq: int = int(number**0.5)
    return number == sq * sq


def add_three(
    x_num: int, x_den: int, y_num: int, y_den: int, z_num: int, z_den: int
) -> tuple[int, int]:
    
    top: int = x_num * y_den * z_den + y_num * x_den * z_den + z_num * x_den * y_den
    bottom: int = x_den * y_den * z_den
    hcf: int = gcd(top, bottom)
    top //= hcf
    bottom //= hcf
    return top, bottom


def solution(order: int = 35) -> int:
    
    unique_s: set = set()
    hcf: int
    total: Fraction = Fraction(0)
    fraction_sum: tuple[int, int]

    for x_num in range(1, order + 1):
        for x_den in range(x_num + 1, order + 1):
            for y_num in range(1, order + 1):
                for y_den in range(y_num + 1, order + 1):
                    
                    z_num = x_num * y_den + x_den * y_num
                    z_den = x_den * y_den
                    hcf = gcd(z_num, z_den)
                    z_num //= hcf
                    z_den //= hcf
                    if 0 < z_num < z_den <= order:
                        fraction_sum = add_three(
                            x_num, x_den, y_num, y_den, z_num, z_den
                        )
                        unique_s.add(fraction_sum)

                    
                    z_num = (
                        x_num * x_num * y_den * y_den + x_den * x_den * y_num * y_num
                    )
                    z_den = x_den * x_den * y_den * y_den
                    if is_sq(z_num) and is_sq(z_den):
                        z_num = int(sqrt(z_num))
                        z_den = int(sqrt(z_den))
                        hcf = gcd(z_num, z_den)
                        z_num //= hcf
                        z_den //= hcf
                        if 0 < z_num < z_den <= order:
                            fraction_sum = add_three(
                                x_num, x_den, y_num, y_den, z_num, z_den
                            )
                            unique_s.add(fraction_sum)

                    
                    z_num = x_num * y_num
                    z_den = x_den * y_num + x_num * y_den
                    hcf = gcd(z_num, z_den)
                    z_num //= hcf
                    z_den //= hcf
                    if 0 < z_num < z_den <= order:
                        fraction_sum = add_three(
                            x_num, x_den, y_num, y_den, z_num, z_den
                        )
                        unique_s.add(fraction_sum)

                    
                    z_num = x_num * x_num * y_num * y_num
                    z_den = (
                        x_den * x_den * y_num * y_num + x_num * x_num * y_den * y_den
                    )
                    if is_sq(z_num) and is_sq(z_den):
                        z_num = int(sqrt(z_num))
                        z_den = int(sqrt(z_den))
                        hcf = gcd(z_num, z_den)
                        z_num //= hcf
                        z_den //= hcf
                        if 0 < z_num < z_den <= order:
                            fraction_sum = add_three(
                                x_num, x_den, y_num, y_den, z_num, z_den
                            )
                            unique_s.add(fraction_sum)

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

    return total.denominator + total.numerator


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