problem 72 counting fractions https projecteuler netproblem72 description 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 21 elements in this set how many elements would be contained in the set of reduced proper fractions for d 1 000 000 solution number of numbers between 1 and n that are coprime to n is given by the euler s totient function phin so the answer is simply the sum of phin for 2 n 1 000 000 sum of phid for all dn n this result can be used to find phin using a sieve time 1 sec returns an integer the solution to the problem solution10 31 solution100 3043 solution1000 304191 generating an array from 1 to limit returns an integer the solution to the problem solution 10 31 solution 100 3043 solution 1_000 304191 generating an array from 1 to limit indexes for selection
import numpy as np


def solution(limit: int = 1_000_000) -> int:
    

    
    phi = np.arange(-1, limit)

    for i in range(2, limit + 1):
        if phi[i] == i - 1:
            ind = np.arange(2 * i, limit + 1, i)  
            phi[ind] -= phi[ind] // i

    return np.sum(phi[2 : limit + 1])


if __name__ == "__main__":
    print(solution())