project euler problem 73 https projecteuler netproblem73 consider the fraction nd where n and d are positive integers if nd and hcfn d1 it is called a reduced proper fraction if we list the set of reduced proper fractions for d 8 in ascending order of size we get 18 17 16 15 14 27 13 38 25 37 12 47 35 58 23 57 34 45 56 67 78 it can be seen that there are 3 fractions between 13 and 12 how many fractions lie between 13 and 12 in the sorted set of reduced proper fractions for d 12 000 returns number of fractions lie between 13 and 12 in the sorted set of reduced proper fractions for d maxd solution4 0 solution5 1 solution8 3 returns number of fractions lie between 1 3 and 1 2 in the sorted set of reduced proper fractions for d max_d solution 4 0 solution 5 1 solution 8 3
from math import gcd


def solution(max_d: int = 12_000) -> int:
    

    fractions_number = 0
    for d in range(max_d + 1):
        for n in range(d // 3 + 1, (d + 1) // 2):
            if gcd(n, d) == 1:
                fractions_number += 1
    return fractions_number


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