Problem 918: Farey Sequence Properties

Mathematical Analysis

Definition and Examples

$F_1 = \{0/1, 1/1\}$, length 2.

$F_3 = \{0/1, 1/3, 1/2, 2/3, 1/1\}$, length 5.

$F_4 = \{0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1\}$, length 7.

Length Formula

Theorem. $|F_n| = 1 + \sum_{k=1}^{n} \varphi(k)$, where $\varphi$ is Euler’s totient function.

Proof. Each fraction $a/b$ in $F_n$ with $0 < a < b$ satisfies $\gcd(a, b) = 1$ and $1 \le b \le n$. For each denominator $b$, there are exactly $\varphi(b)$ valid numerators $a \in \{1, \ldots, b-1\}$ with $\gcd(a,b) = 1$. The fractions $0/1$ and $b/b = 1/1$ are endpoints. We have $\varphi(1) = 1$ which accounts for $1/1$. Adding $0/1$ gives $|F_n| = 1 + \sum_{k=1}^{n}\varphi(k)$. $\square$

Euler’s Totient Function

Definition. $\varphi(n) = |\{k : 1 \le k \le n, \gcd(k, n) = 1\}|$.

Product formula: $\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$.

Proof. By Chinese Remainder Theorem and multiplicativity: $\varphi(p^a) = p^{a-1}(p-1)$ since exactly $p^{a-1}$ of $\{1, \ldots, p^a\}$ are divisible by $p$. For coprime $m, n$: $\varphi(mn) = \varphi(m)\varphi(n)$ by CRT. $\square$

Asymptotic Growth

Theorem. $|F_n| \sim \frac{3n^2}{\pi^2}$ as $n \to \infty$.

Proof. The summatory totient function satisfies $\sum_{k=1}^{n} \varphi(k) = \frac{n^2}{2\zeta(2)} + O(n \log n) = \frac{3n^2}{\pi^2} + O(n \log n)$. This follows from $\sum_{k=1}^{n} \varphi(k) = \frac{1}{2}\sum_{d=1}^{n} \mu(d)\lfloor n/d \rfloor(\lfloor n/d \rfloor + 1)$ and the Euler product $\zeta(2) = \pi^2/6$. $\square$

For $n = 1000$: $3 \times 10^6/\pi^2 \approx 303964$. Exact: 304193.

The Farey Mediant Property

Theorem. If $a/b$ and $c/d$ are consecutive in $F_n$, then $bc - ad = 1$.

Proof. By induction. In $F_1$: $1 \cdot 0 - 1 \cdot 1 = -1$, so $|bc - ad| = 1$. When passing from $F_{n-1}$ to $F_n$, a new fraction $(a+c)/(b+d)$ is inserted between consecutive $a/b$ and $c/d$ exactly when $b + d = n$. The cross-differences with neighbors remain $\pm 1$: $(a+c)b - a(b+d) = cb - ad = 1$ and $c(b+d) - (a+c)d = cb - ad = 1$. $\square$

Corollary. Consecutive Farey fractions $a/b$ and $c/d$ satisfy $c/d - a/b = 1/(bd)$.

Relation to the Stern-Brocot Tree

The Farey sequence of order $n$ is obtained by enumerating all fractions in the Stern-Brocot tree with denominators $\le n$. The mediant insertion process builds the tree level by level.

Totient Sieve Algorithm

1. Initialize $\varphi[k] = k$ for $k = 0, 1, \ldots, n$.
2. For each prime $p$: for each multiple $m$ of $p$: $\varphi[m] \mathrel{-}= \varphi[m] / p$.
3. Sum: $|F_n| = 1 + \sum_{k=1}^{n} \varphi[k]$.

Verification Table

| $n$ | $|F_n|$ | $3n^2/\pi^2$ | Ratio | |-----|--------|-------------|-------| | 10 | 33 | 30.4 | 1.086 | | 100 | 3045 | 3040 | 1.002 | | 500 | 76117 | 75991 | 1.002 | | 1000 | 304193 | 303964 | 1.001 |

Proof of Correctness

Theorem. The sieve correctly computes $\varphi(k)$ for all $k \le n$.

Proof. Each prime $p$ dividing $k$ is encountered exactly once in the sieve. The update $\varphi[k] \leftarrow \varphi[k] - \varphi[k]/p$ applies the factor $(1 - 1/p)$ multiplicatively. Since these factors are applied independently for each prime divisor, the final value is $k \prod_{p \mid k}(1 - 1/p) = \varphi(k)$. $\square$

Complexity Analysis

• Totient sieve: $O(n \log \log n)$ time, $O(n)$ space.
• Summation: $O(n)$ single pass.
• Direct Farey enumeration: $O(n^2 / \log n)$ via the Stern-Brocot structure.

Answer

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

/*
 * Problem 918: Farey Sequence Properties
 *
 * |F_n| = 1 + sum_{k=1}^{n} phi(k)
 *
 * Two methods:
 *   1. Totient sieve: compute phi(k) for k=1..n, then sum
 *   2. Mediant-based enumeration (verification)
 *
 * Asymptotic: |F_n| ~ 3n^2/pi^2
 * Mediant property: consecutive a/b, c/d satisfy bc - ad = 1
 */

const int N = 1000;

/* Euler's totient sieve */
vector<int> totient_sieve(int n) {
    vector<int> phi(n + 1);
    iota(phi.begin(), phi.end(), 0);
    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;
            }
        }
    }
    return phi;
}

/* Mediant-based Farey sequence generation */
long long farey_count_mediant(int n) {
    long long count = 0;
    int a = 0, b = 1, c = 1, d = n;
    count++;  // 0/1
    while (c <= n) {
        int k = (n + b) / d;
        int na = c, nb = d, nc = k * c - a, nd = k * d - b;
        a = na; b = nb; c = nc; d = nd;
        count++;
    }
    return count;
}

int main() {
    auto phi = totient_sieve(N);

    // Method 1: Sieve
    long long ans = 1;
    for (int k = 1; k <= N; k++)
        ans += phi[k];

    // Method 2: Mediant enumeration
    long long ans2 = farey_count_mediant(N);
    assert(ans == ans2);

    // Verify small cases
    assert(1 + phi[1] == 2);  // |F_1| = 2
    long long f3 = 1;
    for (int k = 1; k <= 3; k++) f3 += phi[k];
    assert(f3 == 5);  // |F_3| = 5

    cout << ans << endl;
    return 0;
}

"""
Problem 918: Farey Sequence Properties

|F_n| = 1 + sum_{k=1}^{n} phi(k), where F_n is the Farey sequence of order n.

Key results:
    - |F_n| ~ 3n^2/pi^2 (asymptotic)
    - Mediant property: consecutive a/b, c/d satisfy bc - ad = 1
    - phi(n) = n * prod_{p|n} (1 - 1/p)

Methods:
    1. Totient sieve + summation
    2. Mobius-based summation (cross-check)
    3. Direct Farey enumeration (small n)
"""

from math import gcd

# Totient sieve
def totient_sieve(n: int) -> list:
    """Compute phi(k) for k = 0, 1, ..., n via Euler's product 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
    return phi

def farey_length_sieve(n: int):
    """Compute |F_n| = 1 + sum phi(k) for k=1..n."""
    phi = totient_sieve(n)
    return 1 + sum(phi[1:])

def farey_length_brute(n: int):
    """Count fractions in F_n by enumeration."""
    fracs = set()
    for b in range(1, n + 1):
        for a in range(0, b + 1):
            if gcd(a, b) == 1:
                fracs.add((a, b))
    return len(fracs)

# Farey sequence generation (Stern-Brocot mediant)
def farey_sequence(n: int) -> list:
    """Generate F_n using the mediant-based algorithm."""
    result = []
    a, b, c, d = 0, 1, 1, n
    result.append((a, b))
    while c <= n:
        k = (n + b) // d
        a, b, c, d = c, d, k * c - a, k * d - b
        result.append((a, b))
    return result

# Solve
N = 1000
answer = farey_length_sieve(N)

# Verify small cases
for test_n in [1, 2, 3, 4, 5, 10]:
    sieve_len = farey_length_sieve(test_n)
    brute_len = farey_length_brute(test_n)
    assert sieve_len == brute_len, f"n={test_n}: sieve={sieve_len}, brute={brute_len}"

# Verify mediant algorithm
for test_n in [5, 10, 20]:
    seq = farey_sequence(test_n)
    assert len(seq) == farey_length_sieve(test_n)
    # Verify mediant property: consecutive a/b, c/d have bc - ad = 1
    for i in range(len(seq) - 1):
        a, b = seq[i]
        c, d = seq[i + 1]
        assert b * c - a * d == 1, f"Mediant property failed at {a}/{b}, {c}/{d}"

# Known: |F_1| = 2, |F_2| = 3, |F_3| = 5, |F_4| = 7
assert farey_length_sieve(1) == 2
assert farey_length_sieve(3) == 5
assert farey_length_sieve(4) == 7

print(answer)