Project Euler Solution #72: 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;
}