Fareyova posloupnost

O(n²)

Fareyova posloupnost Fₙ obsahuje každý zlomek a/b v základním tvaru (gcd(a,b)=1) s 0 ≤ a ≤ b ≤ n, seřazený od nejmenšího po největší. Sousední zlomky a/b a c/d ve Fₙ splňují bc − ad = 1 — pozoruhodnou vlastnost mediántu, která se využívá v klasickém generovacím rekurenci. Délka Fₙ se rovná 1 + Σ φ(m) pro m = 1 až n, kde φ je Eulerova funkce. Fareyovy posloupnosti se vyskytují v teorii aproximací, ve studiu Stern–Brocotova stromu i v souvislosti s Riemannovou hypotézou.

Posloupnost
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Nasaď rekurenci prvními dvěma členy 0/1 a 1/n
  2. Vypočítej každý další člen Fareyovým vzorcem: k = ⌊(n+b₀)/b₁⌋, pak a₂ = k·a₁−a₀, b₂ = k·b₁−b₀
  3. Přidej řetězec nového zlomku a zvýrazni jej jako aktivní člen
  4. Zastav se, jakmile dosáhneš 1/1; počet členů se rovná 1 + Σ φ(m)

Pseudokód

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)