Farey rivi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. joulukuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Farey-sarja (myös Farey-murtoluku , Farey- sekvenssi tai Farey- taulukko ) on rationaalisten lukujen äärellisten osajoukkojen perhe .

Määritelmä

Kolmannen kertaluvun Farey-sekvenssi on nouseva sarja kaikista positiivisista pelkistymättömistä varsinaisista murtoluvuista , joiden nimittäjä on pienempi tai yhtä suuri kuin : $n$ $n$

F_{n}{\stackrel {\text{def}}{=}}\left\{{\frac {a_{i}}{b_{i}}}:0\leqslant a_{i}\ leqslant b_{i}\leqslant n,\ \gcd(a_{i},b_{i})=1,\ {\frac {a_{i}}{b_{i}}}<{\frac {a_{ i+1}}{b_{i+1}}}}\right\}.

Tilauksen Farey-sekvenssi voidaan muodostaa tilaussekvenssistä seuraavalla säännöllä: $n+1$ $n$

Kopioimme kaikki järjestyssekvenssin elementit . $n$
Jos järjestysjonon kahdessa vierekkäisessä murto-osassa olevien nimittäjien summa antaa luvun, joka ei ole suurempi kuin , niin lisäämme niiden mediaanin näiden murtolukujen väliin , joka on yhtä suuri kuin niiden osoittajien summan suhde nimittäjien summaan. $n$ $n+1$

Esimerkki

Farey-jaksot 1-8: $n$

F_1=\left\{\frac{0}{1},\;\frac{1}{1}\right\};

F_2=\left\{\frac{0}{1},\;\frac{1}{2},\;\frac{1}{1}\right\};

F_3=\left\{\frac{0}{1},\;\frac{1}{3},\;\frac{1}{2},\;\frac{2}{3},\; \frac{1}{1}\right\};

F_4=\left\{\frac{0}{1},\;\frac{1}{4},\;\frac{1}{3},\;\frac{1}{2},\; \frac{2}{3},\;\frac{3}{4},\;\frac{1}{1}\right\};

F_5=\left\{\frac{0}{1},\;\frac{1}{5},\;\frac{1}{4},\;\frac{1}{3},\; \frac{2}{5},\;\frac{1}{2},\;\frac{3}{5},\;\frac{2}{3},\;\frac{3}{ 4},\;\frac{4}{5},\;\frac{1}{1}\right\};

F_6=\left\{\frac{0}{1},\;\frac{1}{6},\;\frac{1}{5},\;\frac{1}{4},\; \frac{1}{3},\;\frac{2}{5},\;\frac{1}{2},\;\frac{3}{5},\;\frac{2}{ 3},\;\frac{3}{4},\;\frac{4}{5},\;\frac{5}{6},\;\frac{1}{1}\right\} ;

F_7=\left\{\frac{0}{1},\;\frac{1}{7},\;\frac{1}{6},\;\frac{1}{5},\; \frac{1}{4},\;\frac{2}{7},\;\frac{1}{3},\;\frac{2}{5},\;\frac{3}{ 7},\;\frac{1}{2},\;\frac{4}{7},\;\frac{3}{5},\;\frac{2}{3},\;\ frac{5}{7},\;\frac{3}{4},\;\frac{4}{5},\;\frac{5}{6},\;\frac{6}{7 },\;\frac{1}{1}\right\};

F_8=\left\{\frac{0}{1},\;\frac{1}{8},\;\frac{1}{7},\;\frac{1}{6},\; \frac{1}{5},\;\frac{1}{4},\;\frac{2}{7},\;\frac{1}{3},\;\frac{3}{ 8},\;\frac{2}{5},\;\frac{3}{7},\;\frac{1}{2},\;\frac{4}{7},\;\ frac{3}{5},\;\frac{5}{8},\;\frac{2}{3},\;\frac{5}{7},\;\frac{3}{4 },\;\frac{4}{5},\;\frac{5}{6},\;\frac{6}{7},\;\frac{7}{8},\;\frac {1}{1}\oikea\}.

Ominaisuudet

Jos Farey-sarjassa on kaksi vierekkäistä murtolukua, niin . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Todiste.

Huomaa, että kolmio on tasossa, jossa on kärkipisteet , eikä se voi sisältää muita kokonaislukupisteitä kuin kärkipisteitä. Muuten, jos koko piste sisältyy , murto-osa on välillä ja , ja nimittäjä ei ylitä . Joten huippukaavan mukaan sen pinta-ala on yhtä suuri kuin . Toisaalta alue on . H.t.d. $A=(0,\;0)$ $B=(p_1,\;q_1)$ $C=(p_2,\;q_2)$ $(r,\;s)$ $\kolmio ABC$ $r/s$ $p_1/q_1$ $p_2/q_2$ $s$ $\max\{q_1,\;q_2\}$ $1/2$ $\kolmio ABC$ $(q_1p_2-q_2p_1)/2$

Päinvastoin on myös totta: jos murtoluvut ovat sellaisia, että , niin ne ovat Farey-sarjan naapurijäseniä . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$ $F_{\max\{q_1,q_2\}}$

Generointialgoritmi

Algoritmi kaikkien murtolukujen F n generoimiseksi on hyvin yksinkertainen sekä nousevassa että laskevassa järjestyksessä. Jokainen algoritmin iteraatio rakentaa seuraavan murto-osan kahden edellisen perusteella. Siten, jos ja ovat kaksi jo rakennettua murtolukua, ja on seuraava tuntematon, niin . Tämä tarkoittaa, että joillekin kokonaisluvuille ja on totta , joten ja . Koska sen pitäisi olla mahdollisimman lähellä arvoa , niin asetamme nimittäjäksi suurimman mahdollisen, eli tästä eteenpäin ottaen huomioon sen, että on kokonaisluku, meillä on ja ${\frac {a}{b}}$ ${\frac {c}{d))$ ${\frac {p}{q))$ $\frac{c}{d} = \frac{a + p}{b + q}$ $k$ $kc = a + p$ $kd = b + q$ $p = kc - a$ $q = kd - b$ ${\frac {p}{q))$ ${\frac {c}{d))$ $kd - b = n$ $k$ $k = \lfloor\frac{n + b}{d}\rfloor$

p = \left\lfloor\frac{n+b}{d}\right\rfloor c - a

q = \left\lfloor\frac{n+b}{d}\right\rfloor d - b

Toteutusesimerkki Pythonissa :

def farey ( n , asc = True ): jos asc : a , b , c , d = 0 , 1 , 1 , n muuten : a , b , c , d = 1 , 1 , n - 1 , n tulosta " % d / %d " % ( a , b ) kun taas ( nouseva ja c <= n ) tai ( ei nouseva ja a > 0 ): k = int ( ( n + b ) / d ) a , b , c , d = c , d , k * c - a , k * d - b tulosta " %d / %d " % ( a , b )

Esimerkki JavaScriptin toteutuksesta :

class Murtoluku { konstruktori ( numero , denom ) { this . numero = numero ; tämä . denom = denom ; } kopioi () { return new Murtoluku ( this . numer , this . denom ); } } function * farey ( n , asc = tosi ) { olkoon [ a , b ] = asc ? [ uusi murtoluku ( 0 , 1 ), uusi murtoluku ( 1 , n ) ] : [ uusi murtoluku ( 1 , 1 ), uusi murtoluku ( n - 1 , n ) ]; tuotto a . kopioi (); while ( nouseva && b . numero <= n || ! nouseva && a . numero > 0 ) { tuotto b . kopioi (); const k = Math . kerros (( n + a . denom ) / b . denom ), seuraava = uusi Murtoluku ( k * b . numer - a . numer , k * b . denom - a . denom ); a = b _ b = seuraava ; } }

Siten on mahdollista rakentaa mielivaltaisen suuri joukko kaikista murtoluvuista lyhennetyssä muodossa, jota voidaan käyttää esimerkiksi Diofantiiniyhtälön ratkaisemiseen rationaalilukujen tyhjentävällä haulla .

Historia

John Farey on kuuluisa geologi, yksi geofysiikan pioneereista . Hänen ainoa panoksensa matematiikkaan olivat hänen mukaansa nimetyt murtoluvut. Vuonna 1816 julkaistiin Fareyn artikkeli "Mauttomat fraktioiden kummallisesta ominaisuudesta", jossa hän määritteli sekvenssin . Tämä artikkeli saavutti Cauchyn , joka samana vuonna julkaisi todisteen Fareyn olettamuksesta, jonka mukaan jokainen uusi termi Farey-järjestyksessä on naapuriensa mediaani . Fareyn vuonna 1816 kuvaamaa sekvenssiä käytti Charles Haros vuoden 1802 artikkelissaan desimaalien lähentämisestä yhteisten murtolukujen avulla. $F_{n}$ $n+1$

Katso myös

Linkit

Knop K. Ei-binäärinen järjestelmä // Kotitietokone. - 2001. - Nro 8 . Arkistoitu alkuperäisestä 12. maaliskuuta 2007.
Weisstein, Eric W. Farey Sequence (englanniksi) Wolfram MathWorld -verkkosivustolla .
Farey-sarjan osoittajat ja nimittäjät: OEIS - sekvenssi A006842 ja OEIS - sekvenssi A006843 .