Project Euler 72: How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000

I don’t think it is a coincidence that this exact problem comes right now as we shall see in the solution of the problem. Problem 72 of Project Euler reads

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?

The first thing to note is that in here HCF is the same as the greatest common divisor or GCD as I usually use. The second thing to note is that we are probably looking for a very large number, but let us take a look at the problem

Restating the problem

Let us start with a smaller problem. How do we determine the number of reduced proper fractions of one number i. Well a proper reduced fraction is a fraction where the numerator and denominator has a greatest common divisor of 1, meaning they are relatively prime. So all numerators which are relatively prime to and smaller than i  are proper reduced fractions. This is the exact definition of Euler’s totient function, so the answer to that question is φ(i).

This means we can restate the original question to find the answer to

Solving this with a sieve

Euler’s totient function of a given i can be calculated as

It means we have to find all distinct prime factors for all numbers up to 1.000.000. Quite a task unless we do something a bit clever.  Luckily we can use a clever method. We can use a sieving method just like the sieve of Eratosthenes.

In a sieve of Eratosthenes we make a list of all numbers up to the limit we are interested in.  We then start at the first prime and remove any multiple of that since any multiple will be a composite number with the found prime as a factor. We then move on to the next number which is not removed and remove any multiple of that. We need to apply the same technique here. However, instead of removing multiples of the primes we need to multiply them with .   Doing that means we will eventually do that with all prime factors of every number.

The clever thing about this is that primes are easily identifiable since there are no smaller prime factors that divides a prime, once we come to the number it will still be the full quantity.

I have made the sieve implementation in C# as

int limit = 1000000;
int[] phi = Enumerable.Range(0, limit+1).ToArray();
long result = 0;
for(int i = 2; i <= limit; i++){
    if (phi[i] == i) {
        for (int j = i; j <= limit; j += i) {
            phi[j] = phi[j] / i * (i - 1);
        }
    }
    result += phi[i];
}

Wrapping up

My main problem with this solution is that the execution of it gives me

There are 303963552391 proper fractions with denominator up to 1000000
Solution took 34 ms

which is a longer solution time than I would like. However, I think the solution approach is really neat and thus I am satisfied. As usual you can find the source code for the problem here. Comments, questions or other solutions are as always very welcome.