Farey row

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 6 decembrie 2019; verificările necesită 3 modificări .

Seria Farey (de asemenea fracții Farey , secvență Farey sau tablou Farey) este o familie de submulțimi finite de numere raționale .

Definiție

Secvența Farey de ordinul al treilea este o serie ascendentă a tuturor fracțiilor proprii ireductibile pozitive al căror numitor este mai mic sau egal cu : $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}}}}\dreapta\}.

Secvența Farey a unui ordin poate fi construită din secvența de ordine prin următoarea regulă: $n+1$ $n$

Copiem toate elementele secvenței de ordine . $n$
Dacă suma numitorilor din două fracții adiacente ale șirului de ordine dă un număr nu mai mare de , atunci introducem mediana acestora între aceste fracții , egală cu raportul dintre suma numărătorilor lor și suma numitorilor. $n$ $n+1$

Exemplu

Secvențe Farey de la 1 la 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}\dreapta\}.

Proprietăți

Dacă sunt două fracții adiacente în seria Farey, atunci . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Dovada.

Rețineți că triunghiul este în planul cu vârfuri și nu poate conține alte puncte întregi decât vârfuri. În caz contrar, dacă întregul punct este conținut în , atunci fracția se află între și , iar numitorul nu depășește . Deci, conform formulei Peak , aria sa este egală cu . Pe de altă parte, zona este . H. t. d. $A=(0,\;0)$ $B=(p_1,\;q_1)$ $C=(p_2,\;q_2)$ $(r,\;s)$ $\triunghi ABC$ $r/s$ $p_1/q_1$ $p_2/q_2$ $s$ $\max\{q_1,\;q_2\}$ $1/2$ $\triunghi ABC$ $(q_1p_2-q_2p_1)/2$

Reversul este de asemenea adevărat: dacă fracțiile sunt astfel încât , atunci sunt membri vecini ai seriei Farey . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$ $F_{\max\{q_1,q_2\}}$

Algoritm de generare

Algoritmul de generare a tuturor fracțiilor F n este foarte simplu, atât în ordine crescătoare cât și descrescătoare. Fiecare iterație a algoritmului construiește următoarea fracție pe baza celor două anterioare. Astfel, dacă și sunt două fracții deja construite și este următoarea necunoscută, atunci . Aceasta înseamnă că pentru un număr întreg , și este adevărat , prin urmare și . Deoarece ar trebui să fie cât mai aproape de , atunci setăm numitorul să fie maxim posibil, adică , de aici, ținând cont de faptul că este un întreg, avem și ${\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

Exemplu de implementare în Python :

def farey ( n , asc = True ): if asc : a , b , c , d = 0 , 1 , 1 , n else : a , b , c , d = 1 , 1 , n - 1 , n print " % d / %d " % ( a , b ) în timp ce ( asc și c <= n ) sau ( nu asc și a > 0 ): k = int (( n + b ) / d ) a , b , c , d = c , d , k * c - a , k * d - b print " %d / %d " % ( a , b )

Exemplu de implementare JavaScript :

class Fracție { constructor ( număr , denumire ) { this . număr = număr ; aceasta . denom = denom ; } copy () { return new Fraction ( acest . număr , acest . denumire ); } } function * farey ( n , asc = true ) { lat [ a , b ] = asc ? [ Fracție nouă ( 0 , 1 ), Fracție nouă ( 1 , n ) ] : [ Fracție nouă ( 1 , 1 ), Fracție nouă ( n - 1 , n ) ]; randament un . copie (); în timp ce ( asc && b . număr <= n || ! asc && a . număr > 0 ) { randament b . copie (); const k = Math . etaj (( n + a . denom ) / b . denom ), următorul = nou Fracție ( k * b . numer - a . numer , k * b . denom - a . denom ); a = b _ b = următorul ; } }

Astfel, este posibil să se construiască un set arbitrar mare de toate fracțiile într-o formă prescurtată, care poate fi folosit, de exemplu, pentru a rezolva ecuația diofantină prin căutare exhaustivă în numere raționale.

Istorie

John Farey este un geolog faimos, unul dintre pionierii geofizicii . Singura lui contribuție la matematică au fost fracțiile numite după el. În 1816, a fost publicat articolul lui Farey „On a curious property of vulgar fractions”, în care a definit secvența . Această lucrare a ajuns la Cauchy , care în același an a publicat o dovadă a conjecturei Farey că fiecare termen nou al secvenței Farey este mediana vecinilor săi. Secvența descrisă de Farey în 1816 a fost folosită de Charles Haros în lucrarea sa din 1802 despre aproximarea zecimalelor prin fracții comune. $F_{n}$ $n+1$

Vezi și

Link -uri

Knop K. Sistem non-binar // Computer de acasă. - 2001. - Nr. 8 . Arhivat din original pe 12 martie 2007.
Weisstein, Eric W. Farey Sequence (engleză) pe site-ul web Wolfram MathWorld .
Numeratorii și Numitorii din seria Farey: secvența OEIS A006842 și secvența OEIS A006843 .