Project Euler Problem 72 Statement
Consider the fraction, $\dfrac n d$, where $n$ and $d$ are positive integers. If $n \lt d$ and $\operatorname{HCF}(n,d)=1$, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for $d \le 8$ in ascending order of size, we get: $$\frac 1 8, \frac 1 7, \frac 1 6, \frac 1 5, \frac 1 4, \frac 2 7, \frac 1 3, \frac 3 8, \frac 2 5, \frac 3 7, \frac 1 2, \frac 4 7, \frac 3 5, \frac 5 8, \frac 2 3, \frac 5 7, \frac 3 4, \frac 4 5, \frac 5 6, \frac 6 7, \frac 7 8$$
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 \le 1,000,000$?
Solution
HackerRank's Project Euler #72 challenge involves counting the number of distinct irreducible fractions for denominators up to $1,000,000$ by using Euler's Totient function $\varphi$.
Totient Function Sieve (Function ET(L))
- We create a list phi[] of size
L+1such thatphi[i] = i. - We iterate over n from 2 to L. If
phi[n] == n, then n is prime. - For each prime n, we update its multiples: $$\varphi[k] = \varphi[k] - \frac{\varphi[k]}{n}\text{ for each multiple $k$ of $n$}$$
- This is a standard sieve method for computing totient values in $O(L \log \log L)$ time.
Next, we compute the partial sums of the values in the phi[] list. As a result, phi[x] stores the sum of $\varphi(i)$ for $i$ ranging from $0$ to $x$.
Finally, we handle user queries by reading an integer input and outputting cumulative sum minus 1. The subtraction of 1 excludes the fraction $1/1$.
By precomputing the totient function values and their cumulative sums, we can answer each query in constant time.
HackerRank version
HackerRank Project Euler Problem 72: Determine the number of elements that would be contained in the set of reduced proper fractions for $d\le N$ where $(2\le N\le 10^6)$ for $10^5$ test cases.
Python Source Code
L = 1_000_000
phi = list(range(L + 1))
for n in range(2, L + 1):
if phi[n] == n: # n is prime
for k in range(n, L + 1, n):
phi[k] -= phi[k] // n
for i in range(1, L + 1):
phi[i] += phi[i - 1]
for _ in range(int(input())):
print(phi[int(input())] - 1)