Fareyova posloupnost

Fareyova posloupnost řádu n je posloupnost zlomků mezi 0 a 1, které jsou jednak v základním tvaru, jednak mají ve jmenovateli číslo menší nebo rovné n. Například pro n = 5 tedy vypadá takto:

F₅ = {⁰⁄₁, ¹⁄₅, ¹⁄₄, ¹⁄₃, ²⁄₅, ¹⁄₂, ³⁄₅, ²⁄₃, ³⁄₄, ⁴⁄₅, ¹⁄₁}

Je pojmenována po britském geologovi Johnu Fareyovi st., který si všiml, že nové členy v posloupnosti F_n lze získat z řady F_n-1 jako medián dvou sousedních členů. Důkaz tohoto pozorování však podal až Cauchy.

Vlastnosti

Délka

Máme-li k dispozici Eulerovu funkci φ, můžeme délku n-té Fareyovy posloupnosti snadno vyjádřit jako

$|F_n|=|F_{n-1}|+\phi (n).$

Asymptoticky lze velikost n-tého prvku posloupnosti odhadnout jako

$|F_n|\sim \frac{3n^2}{{\pi }^2}.$

Externí odkazy

• Šablona:Commonscat
• Druhá kapitola skript Martina Klazara, Kaleidoskop teorie čísel