Problem 72: Counting Fractions

Mathematical Analysis

Theorem 1 (Fractions Per Denominator)

The number of reduced proper fractions with denominator exactly $d$ is $\varphi(d)$.

Proof. A fraction $n/d$ with $1 \leq n < d$ is in lowest terms if and only if $\gcd(n, d) = 1$. By definition, $\varphi(d) = |\{n : 1 \leq n \leq d,\ \gcd(n,d) = 1\}|$. For $d \geq 2$, since $\gcd(d, d) = d > 1$, the element $n = d$ does not contribute, so the count of $n$ with $1 \leq n < d$ and $\gcd(n,d) = 1$ equals $\varphi(d)$. $\square$

Theorem 2 (Euler’s Product Formula)

For $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$:

Proof. We prove two properties and combine them.

(i) Multiplicativity. If $\gcd(m, n) = 1$, then $\varphi(mn) = \varphi(m)\varphi(n)$. By the Chinese Remainder Theorem, the canonical ring isomorphism $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ restricts to a group isomorphism $(\mathbb{Z}/mn\mathbb{Z})^\times \cong (\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times$. Comparing cardinalities gives $\varphi(mn) = \varphi(m)\varphi(n)$.

(ii) Prime powers. For a prime power $p^a$, an integer $k \in \{1, \ldots, p^a\}$ satisfies $\gcd(k, p^a) > 1$ if and only if $p \mid k$. There are $p^{a-1}$ such multiples, so $\varphi(p^a) = p^a - p^{a-1} = p^a(1 - 1/p)$.

Applying (i) inductively to the prime factorization $n = \prod p_i^{a_i}$ and substituting (ii) yields the product formula. $\square$

Theorem 3 (Answer Formula)

The total number of reduced proper fractions with denominator $\leq N$ is:

Proof. By Theorem 1, the count is $\sum_{d=2}^{N} \varphi(d)$. (We begin at $d = 2$ since $d = 1$ admits no proper fractions: the condition $1 \leq n < 1$ has no solutions.) Since $\varphi(1) = 1$, this equals $\sum_{d=1}^{N} \varphi(d) - 1$. $\square$

Lemma (Totient Sieve Correctness)

The sieve algorithm that initializes $\varphi[d] = d$ for all $d$ and, for each prime $p \leq N$, updates $\varphi[m] \leftarrow \varphi[m] \cdot (p-1)/p$ for all multiples $m$ of $p$, correctly computes $\varphi(d)$ for all $d \leq N$.

Proof. After the sieve completes, each entry satisfies:

Every prime $p$ dividing $d$ satisfies $p \leq d \leq N$, so the product ranges over all prime divisors of $d$. By Theorem 2, this equals $\varphi(d)$.

Primes are correctly identified during the sieve: $d$ is prime if and only if $\varphi[d] = d$ when $d$ is first visited (since all primes $p < d$ dividing $d$ would have already modified $\varphi[d]$, and $d$ is composite if and only if it has such a prime divisor). $\square$

Remark (Asymptotic)

By a classical result in analytic number theory, $\sum_{d=1}^{N} \varphi(d) = \frac{3N^2}{\pi^2} + O(N \log N)$. For $N = 10^6$, this gives approximately $3.04 \times 10^{11}$.

Editorial

The denominator-by-denominator interpretation is the key simplification. For a fixed $d$, exactly $\varphi(d)$ numerators produce reduced proper fractions, so the whole problem becomes the summatory totient

Computing each $\varphi(d)$ independently would waste work because nearby values share prime factors. The sieve avoids that. We begin with $\varphi(d) = d$ for every $d$, and whenever we discover a prime $p$, we apply the factor $(1 - 1/p)$ to every multiple of $p$. By the time the sieve finishes, every denominator has been filtered by exactly its distinct prime divisors, so the array contains the correct totients and summing it gives the answer.

Pseudocode

Create an array phi with phi[d] = d for every d from 0 to N.

For each integer p from 2 to N:
    If phi[p] is still equal to p, then p is prime
        For each multiple m of p:
            replace phi[m] by phi[m] x (p - 1) / p

Add phi[2] through phi[N].
Return that total.

Complexity Analysis

Time: The sieve visits, for each prime $p \leq N$, all $\lfloor N/p \rfloor$ multiples. By Mertens’ second theorem:

where $M$ is the Meissel—Mertens constant.

• Time: $O(N \log \log N)$.
• Space: $O(N)$ for the array $\varphi[1..N]$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Count reduced proper fractions n/d with d <= 1,000,000.
    // Answer = sum of phi(d) for d = 2 to N (Theorem 3).
    // Euler totient sieve in O(N log log N).

    const int N = 1000000;
    vector<int> phi(N + 1);
    iota(phi.begin(), phi.end(), 0);  // phi[i] = i

    for (int p = 2; p <= N; p++) {
        if (phi[p] == p) {  // p is prime
            for (int m = p; m <= N; m += p) {
                phi[m] = phi[m] / p * (p - 1);
            }
        }
    }

    long long total = 0;
    for (int d = 2; d <= N; d++) {
        total += phi[d];
    }

    cout << total << endl;
    return 0;
}

"""
Project Euler Problem 72: Counting Fractions

Count the number of reduced proper fractions n/d with d <= 1,000,000.
By Theorem 3, the answer is sum of phi(d) for d = 2 to 1,000,000.

Computed via Euler totient sieve in O(N log log N).
"""


def solve_sieve(N: int) -> int:
    """Compute sum of phi(d) for d=2..N using Euler totient sieve."""
    phi = list(range(N + 1))
    for p in range(2, N + 1):
        if phi[p] == p:  # p is prime
            for m in range(p, N + 1, p):
                phi[m] = phi[m] // p * (p - 1)
    return sum(phi[d] for d in range(2, N + 1))


answer = solve_sieve(1_000_000)
print(answer)