Problem 72 — Counting Fractions

Problem Analysis

The problem asks me to count reduced proper fractions n/d with 1 <= n < d whose numerator and denominator share no common factor other than 1, for every denominator up to one million. Two integers whose greatest common divisor is 1 are called coprime. The decisive observation is that for a fixed denominator d, the number of valid numerators is exactly the count of integers in 1..d-1 that are coprime to d - and that quantity is precisely Euler's totient function, written phi(d). So the answer to a question about coprime fractions collapses into a single sum: the running total of phi(d) from d = 2 up to the limit. I start at 2 rather than 1 because phi(1) = 1 would count 1/1, which is not a proper fraction with n < d.

The remaining work is computing phi(d) for every d efficiently. The totient is a multiplicative function given by phi(d) = d * product over distinct primes p dividing d of (1 - 1/p). Because this is a product over prime factors, I can compute all totients up to N simultaneously with a sieve modelled on the Sieve of Eratosthenes: seed each phi[d] = d, then for every prime p apply the factor (p-1)/p to each multiple of p. The cost is dominated by the inner loops, which run N/2 + N/3 + N/5 + ... times over the primes - a sum that grows like N log log N, the same near-linear bound as the Sieve of Eratosthenes itself. Memory is O(N). Both are entirely practical even at N = 10^7.

Solution Approach

Euler Totient Sieve (Python and C)

Both files implement the same totient sieve; the C version exists purely for speed. The algorithm proceeds as follows:

• Allocate an array euler_totients of length max_d + 1 and set euler_totients[d] = d. This is the "no prime factors applied yet" identity value, matching the leading d in the product formula. In Python I write this compactly as list(range(max_d + 1)); in C it is a single initialisation loop.
• Iterate n from 2 upward. If euler_totients[n] == n, no smaller prime has yet touched this cell, so n must itself be prime. This doubles as the primality test - I need no separate boolean sieve.
• When n is prime, I walk every multiple j = n, 2n, 3n, ... and apply euler_totients[j] = euler_totients[j] / n * (n - 1). Each distinct prime factor of j is applied exactly once this way, so once all primes <= j have been processed, the cell at j holds its true totient.
• I accumulate result += euler_totients[n] in the same outer loop. This is correct because every prime factor of n is at most n, so the totient of n is fully finalised by the time the outer loop reaches index n.

The two implementations differ only in their host language. The C version uses malloc for the heap array and long long to hold the running total (about 3.0e11 at max_d = 1000000, and roughly 3.0e13 at 10^7 - both comfortably inside a 64-bit integer). The Python version relies on arbitrary-precision integers and a built-in list, so there is no overflow concern at all. Both run one linear outer pass with nested per-prime inner passes.