Problem 73: Counting Fractions in a Range

Mathematical Analysis

Theorem 1 (Range Bounds for Fixed Denominator)

For a fixed denominator $d \geq 2$, the integers $n$ satisfying $1/3 < n/d < 1/2$ and $\gcd(n, d) = 1$ are precisely those in the set:

Proof. The condition $n/d > 1/3$ gives $n > d/3$, so $n \geq \lfloor d/3 \rfloor + 1$ (since $n$ is a positive integer and $d/3$ may not be an integer). The condition $n/d < 1/2$ gives $n < d/2$, so $n \leq \lceil d/2 \rceil - 1 = \lfloor (d-1)/2 \rfloor$. The fraction is reduced if and only if $\gcd(n, d) = 1$. $\square$

Theorem 2 (Mobius Identity for Coprimality)

For any positive integers $n$ and $d$:

where $\mu$ is the Mobius function and $[\cdot]$ denotes the Iverson bracket.

Proof. Let $g = \gcd(n, d)$ and define $F(g) = \sum_{k \mid g} \mu(k)$. By the Mobius inversion identity (or equivalently, since $\mu$ is the Dirichlet inverse of the constant function $\mathbf{1}$), we have $F = \mu * \mathbf{1} = \varepsilon$, where $\varepsilon$ is the identity for Dirichlet convolution: $\varepsilon(m) = [m = 1]$.

Explicitly, for $g = p_1^{a_1} \cdots p_r^{a_r}$ with $g > 1$:

and $F(1) = \mu(1) = 1$. Hence $F(g) = [g = 1] = [\gcd(n,d) = 1]$. $\square$

Theorem 3 (Mobius Summation Formula)

The total count of reduced fractions between $1/3$ and $1/2$ with denominator $\leq N$ is:

where $G(M) = \sum_{d=2}^{M} \left(\lfloor (d-1)/2 \rfloor - \lfloor d/3 \rfloor\right)$ counts the total integers in the range $(d/3, d/2)$ summed over denominators $d = 2, \ldots, M$ (without the coprimality constraint).

Proof. Starting from:

Applying Theorem 2:

Exchanging summation order with the substitutions $d = kd'$, $n = kn'$:

The inner count equals $\lfloor (d'-1)/2 \rfloor - \lfloor d'/3 \rfloor$ when this is non-negative, and 0 otherwise. This gives the stated formula. $\square$

Remark (Mobius Sieve)

The Mobius function $\mu(n)$ can be computed for all $n \leq N$ via a sieve analogous to the Sieve of Eratosthenes:

1. Initialize $\mu[n] = 1$ for all $n$.
2. For each prime $p \leq N$: negate $\mu[m]$ for all multiples $m$ of $p$; set $\mu[m] = 0$ for all multiples $m$ of $p^2$.

This correctly computes $\mu$ because: $\mu(n) = 0$ if $n$ has a squared prime factor; otherwise $\mu(n) = (-1)^k$ where $k$ is the number of distinct prime factors, and each prime negation toggles the sign.

Editorial

The direct approach would inspect every denominator $d$, generate the numerators in the interval $(d/3, d/2)$, and then filter by $\gcd(n,d)=1$. The Mobius identity lets us perform that filtering in bulk instead of checking gcds one fraction at a time.

After expanding the coprimality condition with $\mu$, the problem reorganizes into divisor classes indexed by $k$. For a fixed $k$, we only need to count how many raw numerators fall into the interval for denominators up to $\lfloor N/k \rfloor$; the Mobius value $\mu(k)$ then decides whether that whole class contributes positively, negatively, or not at all. So the candidates are generated by the interval bounds for each denominator, while the Mobius weights perform the filtering that enforces reduced fractions.

Pseudocode

Sieve the Mobius function up to N.
Set the final count to 0.

For each divisor scale k from 1 to N:
    If mu[k] is 0, continue to the next scale

    Let limit be floor(N / k)
    Set a subtotal for this scale to 0

    For each denominator d from 2 to limit:
        Let lo be the smallest integer strictly greater than d / 3
        Let hi be the largest integer strictly smaller than d / 2

        If the interval from lo to hi is nonempty:
            add its size to the subtotal

    Add mu[k] times this subtotal to the final count

Return the final count.

Complexity Analysis

Mobius sieve: $O(N \log \log N)$.

Double sum: The total number of iterations is $\sum_{k=1}^{N} \lfloor N/k \rfloor = O(N \log N)$ (harmonic sum).

• Time: $O(N \log N)$.
• Space: $O(N)$ for the Mobius sieve.

For $N = 12{,}000$, this runs in well under a second.

Answer

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

int main() {
    // Count reduced fractions n/d with 1/3 < n/d < 1/2, d <= 12000.
    // Mobius summation: C(N) = sum_k mu(k) * G(floor(N/k)).

    const int N = 12000;

    // Sieve the Mobius function
    vector<int> mu(N + 1, 1);
    vector<bool> is_prime(N + 1, true);

    for (int p = 2; p <= N; p++) {
        if (is_prime[p]) {
            for (int m = 2 * p; m <= N; m += p)
                is_prime[m] = false;
            for (long long m = (long long)p * p; m <= N; m += (long long)p * p)
                mu[m] = 0;
            for (int m = p; m <= N; m += p)
                mu[m] *= -1;
        }
    }

    long long count = 0;
    for (int k = 1; k <= N; k++) {
        if (mu[k] == 0) continue;
        int limit = N / k;
        long long c = 0;
        for (int d = 2; d <= limit; d++) {
            int lo = d / 3 + 1;
            int hi = (d - 1) / 2;
            if (hi >= lo) c += hi - lo + 1;
        }
        count += mu[k] * c;
    }

    cout << count << endl;
    return 0;
}

"""
Project Euler Problem 73: Counting Fractions in a Range

Count reduced fractions n/d strictly between 1/3 and 1/2 with d <= 12000.

By Theorem 3 (Mobius Summation), we sieve mu and sum over divisor classes.
"""


def solve():
    N = 12000

    # Sieve the Mobius function
    mu = [1] * (N + 1)
    is_prime = [True] * (N + 1)

    for p in range(2, N + 1):
        if is_prime[p]:
            for m in range(2 * p, N + 1, p):
                is_prime[m] = False
            for m in range(p * p, N + 1, p * p):
                mu[m] = 0
            for m in range(p, N + 1, p):
                mu[m] *= -1

    count = 0
    for k in range(1, N + 1):
        if mu[k] == 0:
            continue
        limit = N // k
        c = 0
        for d in range(2, limit + 1):
            lo = d // 3 + 1       # smallest n > d/3
            hi = (d - 1) // 2     # largest n < d/2
            if hi >= lo:
                c += hi - lo + 1
        count += mu[k] * c

    return count


if __name__ == "__main__":
    answer = solve()
    assert answer == 7295372
    print(answer)