Counting Fractions

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$?

This problem can be solved by adopting a concept known as Euler’s Totient function, φ(d), which is the number of positive integers less than d that are coprime (or relatively prime) to d. Now, these integers less than d will be the values of n for our problem, so φ(d) will give us the number of desired fractions for each value of d. Since HCF(n, d) is 1, all fractions will be proper reduced fractions.

For finding number of fractions for d ≤ 1,000,000 we will sum the totient function from 2 to 1,000,000.

This question pertinently demands an implementation of a modified Sieve of Eratosthenes to compute the values of φ(d) in an optimized way.

1. Initialize an array A of length 1,000,001 with values same as its index, i.e., A[i] = i for i = 0 to 1,000,000.

2. Traverse the array from i = 2 to 1,000,000.

3. If A[i] is equal to i, it means i is a prime number. Then for every j = i, 2i, 3i, …, 1,000,000, multiply A[j] by (1 – 1/i). Mathematically, set A[j] = A[j] * (1 – 1/i). Here, j denotes the multiple of i. This should be done because every number ‘j’ that is a multiple of ‘i’ will have i as a factor.

4. After traversing the whole array and performing these operations, A[i] will give φ(i) for every i from 1 to 1,000,000.

5. Now add all the values in this array from 2 to 1,000,000 to get the number of required fractions.

This approach will give the right answer in reasonable time due to the optimized Sieve algorithm. This variant ensures that we only ‘touch’ each number once when its smallest prime factor is found rather attempting to reach it from each of its factors, thus enabling us to deal with the large upper limit.

More Answers: