Fareyova posloupnost

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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

F5 = {01, 15, 14, 13, 25, 12, 35, 23, 34, 45, 11}

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

Vlastnosti[editovat | editovat zdroj]

Délka[editovat | editovat zdroj]

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[editovat | editovat zdroj]