Project Euler Problem 72

Solution

Answer: 303963552391

1. Mathematical analysis

We want the number of reduced proper fractions

$$\frac{n}{d}$$

such that:

$n < d$,
$\gcd(n,d)=1$,
$d \le 1{,}000{,}000$.

Step 1: Count reduced fractions for a fixed denominator

Fix a denominator $d$.

The valid numerators $n$ are integers:

$$1 \le n < d$$

that are coprime to $d$.

The number of such integers is exactly Euler’s totient function:

$$\varphi(d)$$

because $\varphi(d)$ counts positive integers less than $d$ that are coprime to $d$.

For example:

$d=8$: coprime numerators are $1,3,5,7$, so $\varphi(8)=4$.
$d=7$: all $1,2,3,4,5,6$ work, so $\varphi(7)=6$.

Thus the total number of reduced proper fractions for $d \le N$ is:

$$\sum_{d=2}^{N} \varphi(d)$$

For this problem:

$$\sum_{d=2}^{1{,}000{,}000} \varphi(d)$$

Step 2: Efficiently computing totients

A direct gcd check for every pair $(n,d)$ would be impossibly slow:

$$O(N^2)$$

Instead, compute all totients up to $N$ using a sieve (similar to the Sieve of Eratosthenes).

Key fact:

If $p$ is prime, then for multiples of $p$,

$$\varphi(n) = n\left(1-\frac1p\right)$$

We initialize:

$$\varphi(n)=n$$

Then for each prime $p$, update all multiples:

$$\varphi(k) \leftarrow \varphi(k)-\frac{\varphi(k)}{p}$$

This computes all totients up to $10^6$ in roughly:

$$O(N\log\log N)$$

which is easily fast enough.

2. Python implementation

def count_reduced_proper_fractions(limit):
    # Initialize phi[n] = n
    phi = list(range(limit + 1))

    # Sieve to compute Euler's totient for every number
    for p in range(2, limit + 1):
        # If phi[p] == p, then p is prime
        if phi[p] == p:
            # Update all multiples of p
            for multiple in range(p, limit + 1, p):
                phi[multiple] -= phi[multiple] // p

    # Sum φ(d) for d >= 2
    return sum(phi[2:])

# Problem limit
N = 1_000_000

answer = count_reduced_proper_fractions(N)
print(answer)

3. Code walkthrough

Initialize totients

phi = list(range(limit + 1))

We begin with:

$$\phi(n)=n$$

for every $n$.

Example:

phi = [0,1,2,3,4,5,6,7,8]

for $N=8$.

Detect primes

if phi[p] == p:

Only primes still satisfy:

$$\phi(p)=p$$

at this stage.

So this acts as a primality test during the sieve.

Apply totient update

phi[multiple] -= phi[multiple] // p

Implements:

$$\phi(n) = \phi(n)\left(1-\frac1p\right)$$

for every multiple of prime $p$.

Example for $N=8$:

After processing primes:

$$\phi = [0,1,1,2,2,4,2,6,4]$$

meaning:

$$\phi(2)=1,; \phi(3)=2,; \phi(4)=2,; \phi(5)=4,; \phi(6)=2,; \phi(7)=6,; \phi(8)=4$$

Sum all counts

sum(phi[2:])

For the sample $d \le 8$:

$$1+2+2+4+2+6+4 = 21$$

which exactly matches the problem statement.

4. Final verification

The asymptotic estimate is:

$$\sum_{n\le N}\varphi(n) \approx \frac{3}{\pi^2}N^2$$

For $N=10^6$:

$$\frac{3}{\pi^2}(10^{12}) \approx 3.04\times10^{11}$$

So we expect an answer around a few hundred billion, which is the right magnitude.

Running the sieve gives:

$$303963552391$$

This is a well-known verified value for Project Euler Problem 72.

Answer: 303963552391