# Project Euler 72 Solution: Counting fractions

Problem 72

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, 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:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 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 ≤ 1,000,000?

## Solution

In Problem 71 we have seen that we can create a set of reduced proper fractions using Farey sequences. The Farey sequence $$F_n$$ contains every reduced fraction with denominators smaller or equal to $$n$$. If we want to create $$F_{n+1}$$ we have to add all reduced fractions with a denominator coprime to $$n+1$$. The number of numbers that are coprime to a number is exactly the definition of the Euler totient function $$\varphi(n)$$. Therefore

$|F_{n+1}| = |F_n| + \varphi(n+1)$

for every $$n\geq 2$$. For $$n=1$$ we get $$|F_1| = 1+\varphi(1)$$ from which the non-recursive solution follows

$|F_n| = 1 + \sum\limits_{i=1}^n\varphi(i)$

Since we are not interested in the artificially established bounds $$\frac{0}{1}$$ and $$\frac{1}{1}$$ of the Farey sequences, we remote $$F_1$$ and get the solution function $$S$$:

$S(n) = |F_n| - |F_1| = \sum\limits_{i=2}^n\varphi(i)$

We now could solve this problem by summing over $$\varphi(i)$$, but we can do better by deriving an algorithm based on the idea of the Sieve of Eratosthenes and the fact that $$\varphi(n) = n\prod\limits_{p | n}\left(1-\frac{1}{p}\right)$$ for all primes $$p$$ of $$n$$. The algorithm goes like this:

1. Create an array phi[1..n], initialized with its index to finally store $$\varphi(i)$$ values of all numbers from $$1$$ to $$n$$. This array serves two purposes
1. To check if phi[i] was already evaluated. This works since the maximum possible value of $$\varphi(i)$$ is $$i-1$$
2. To initialize phi[i] with $$i$$ as a multiple in the above product formula and remain in the integer world
2. Run a loop from $$i=2$$ to $$n$$
1. If phi[i]=i, the current number was not evaluated yet and $$i$$ is a prime number. Now traverse all multiples of $$i$$ similar to the Sieve of Eratosthenes and multiply the $$1-\frac{1}{i}=\frac{i-1}{i}$$ to it, according to the product formula.
2. Otherwise the number $$i$$ is coprime and no action is needed
3. Sum over the current value of phi[i], since we will never change that value again
function solution(limit) {
let phi = [];
let sum = 0;
for (let i = 0; i <= limit; i++) {
phi.push(i);
}

for(let i = 2; i <= limit; i++){
if (phi[i] === i) {
for (let j = i; j <= limit; j+= i) {
phi[j] = phi[j] / i * (i - 1);
}
}
sum+= phi[i];
}
return sum;
}

« Back to problem overview