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:

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 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

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

Externí odkazy