Fareyn jono

Oletetaan, että m on positiivinen kokonaisluku. Fareyn jonolla F_m tarkoitetaan tällöin niiden välillä [0,1] olevien murtolukujen kasvavaa jonoa, jotka:

- ovat supistetussa muodossa (ts. osoittajan ja nimittäjän) suurin yhteinen tekijä on 1 ja

- nimittäjä on pienempi tai yhtä suuri kuin m.

Esimerkiksi:

F₁ = {⁰⁄₁, ¹⁄₁}

F₂ = {⁰⁄₁, ¹⁄₂, ¹⁄₁}

F₃ = {⁰⁄₁, ¹⁄₃, ¹⁄₂, ²⁄₃, ¹⁄₁}

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

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

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

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

F₈ = {⁰⁄₁, ¹⁄₈, ¹⁄₇, ¹⁄₆, ¹⁄₅, ¹⁄₄, ²⁄₇, ¹⁄₃, ³⁄₈, ²⁄₅, ³⁄₇, ¹⁄₂, ⁴⁄₇, ³⁄₅, ⁵⁄₈, ²⁄₃, ⁵⁄₇, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ⁶⁄₇, ⁷⁄₈, ¹⁄₁}

Fareyn jonojen historiaa

Fareyn jonot on nimetty brittiläisen mineralogin (kidetutkijan) John Fareyn mukaan. Hänen näitä jonoja koskeva kirjoitelmansa julkaistiin lehdessä nimeltä Philosophical Magazine vuonna 1816. Farey esitti väittämän, että jonon kukin jäsen voidaan laskea sen lähimpien naapurien ns. medianttina ts. jakamalla näiden lukujen osoittajien summa niiden nimittäjien summalla. Farey ei kuitenkaan tiettävästi itse todistanut väittämäänsä. Todistuksen esitti ensimmäisenä Cauchy kirjassaan Exercises de mathématique. Saman tuloksen oli kuitenkin esittänyt toinen matemaatikko C. Haros jo vuonna 1802. Harosin artikkeli ei kuitenkaan liene ollut Fareyn tai Cauchyn tiedossa. On siis lähinnä historiallinen sattuma, että jonot kantavat edelleen Fareyn nimeä.

Välittömän edeltäjän ja seuraajan laskeminen

Tarkastellaan Fareyn jonoa, jossa nimittäjien maksimiarvo on $m$.

Lukua ${\frac {p}{q}}$, missä ${\mbox{gcd}}(p,q)=1$, välittömästi seuraava luku ${\frac {p'}{q'}}$ voidaan laskea kaavoista

${\begin{cases}q'=\lfloor {\frac {m+r}{q}}\rfloor q-r\\p'={\frac {pq'+1}{q}}\end{cases}}$

missä $r$ on luvun $p$ modulaariaritmetiikan käänteisluku modulo $q$, ts. $pr\equiv 1({\mbox{ mod }}q)$, ja $\lfloor \cdot \rfloor$ tarkoittaa pyöristystä alaspäin lähimpään kokonaislukuun (ns. porrasfunktio).

Vastaavasti lukua ${\frac {p}{q}}$ välittömästi edeltävä luku ${\frac {p''}{q''}}$ voidaan laskea kaavoista

${\begin{cases}q''=\lfloor {\frac {m-r}{q}}\rfloor q+r\\p''={\frac {pq''-1}{q}}\end{cases}}$

missä $r$ on kuten edellä.

Tarvittavat modulaariaritmetiikan käänteisluvut voidaan laskea tehokkaasti ns. laajennetun eukleideen algoritmin avulla.

Kaavat ovat erityisen käyttökelpoisia tarkasteltujen lukujen ollessa suuria, esimerkiksi kymmenien tai satojen numeroiden mittaisia.