Project Euler Problem 72 Solution: Counting Fractions

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 a 1,000,000 by using Euler's Totient function $\varphi$.

Totient Function Sieve (Function `ET(L)`)

We create a list phi[] of size L+1 such that phi[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 use itertools.accumulate* to compute the partial sums of the values in the phi[] list. As a result, p[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 is specific to the requirements of problem which 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

Solves all test cases for Hackerrank Project Euler Problem 72

HackerRank Project Euler 72: How many elements would be contained in the set of reduced proper fractions for $d\le N$, $2\le N\le 10^6$ (up to $10^5$ test cases)?

Python Source Code

import itertools

def ET(L):
    phi = list(range(L+1))
    for n in range(2, L+1):
        if phi[n] == n:
            for k in range(n, L+1, n):
                phi[k] -= phi[k] // n
    return phi

L = 1_000_000
p = list(itertools.accumulate(ET(L)))

for _ in range(int(input())):
    print(p[int(input())]-1)

Last Word

*The itertools.accumulate() function in Python takes an iterable as input and returns an iterator of the cumulative sums (or other binary operations) of the elements in that iterable. By default, accumulate() computes the running sum.

Here is a simple example using the default behavior (cumulative sum):