Farey sequence

O(n²)

The Farey sequence Fₙ contains every fraction a/b in reduced form (gcd(a,b)=1) with 0 ≤ a ≤ b ≤ n, arranged from smallest to largest. Adjacent fractions a/b and c/d in Fₙ satisfy bc − ad = 1 — a remarkable mediant property used in the classic generation recurrence. The length of Fₙ equals 1 + Σ φ(m) for m = 1 to n, where φ is Euler's totient function. Farey sequences appear in approximation theory, the study of the Stern–Brocot tree, and the Riemann hypothesis.

Sequence
Press ▶ to run
Edit the input and press Play

How it works

  1. Seed the recurrence with the first two terms 0/1 and 1/n
  2. Compute each successive term using the Farey neighbour formula: k = ⌊(n+b₀)/b₁⌋, then a₂ = k·a₁−a₀, b₂ = k·b₁−b₀
  3. Append the new fraction string and highlight it as the active term
  4. Stop when 1/1 is reached; the count equals 1 + Σ φ(m)

Pseudocode

1fareySequence(n):                    # O(|F_n|) ≈ O(n²/π²)2  a0,b0 ← 0,1  ;  a1,b1 ← 1,n      # seed: 0/1 and 1/n3  seq ← ["0/1", "1/n"]4  while a1/b1 < 1:5    k  ← ⌊(n + b0) / b1⌋            # Farey neighbour recurrence6    a2 ← k*a1 - a0  ;  b2 ← k*b1 - b07    seq.push(a2 + "/" + b2)8    a0,b0 ← a1,b1  ;  a1,b1 ← a2,b29  return seq                         # |seq| = 1 + Σφ(m)