Farey rad

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 december 2019; kontroller kräver 3 redigeringar .

Farey-serier (även Farey-bråk , Farey -sekvens eller Farey- tablå ) är en familj av ändliga delmängder av rationella tal .

Definition

Farey-sekvensen i th-ordningen är en stigande serie av alla positiva irreducerbara egenbråk vars nämnare är mindre än eller lika med : $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\}.

Farey-sekvensen för en order kan konstrueras från ordersekvensen genom följande regel: $n+1$ $n$

Vi kopierar alla element i ordersekvensen . $n$
Om summan av nämnarna i två intilliggande bråk av ordningsföljden ger ett tal som inte är större än , då infogar vi deras median mellan dessa bråk , lika med förhållandet mellan summan av deras täljare och summan av nämnare. $n$ $n+1$

Exempel

Farey-sekvenser för 1 till 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=\vänster\{\frac{0}{1},\;\frac{1}{3},\;\frac{1}{2},\;\frac{2}{3},\; \frac{1}{1}\right\};

F_4=\vänster\{\frac{0}{1},\;\frac{1}{4},\;\frac{1}{3},\;\frac{1}{2},\; \frac{2}{3},\;\frac{3}{4},\;\frac{1}{1}\right\};

F_5=\vänster\{\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=\vänster\{\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=\vänster\{\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=\vänster\{\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}\right\}.

Egenskaper

Om det finns två intilliggande bråk i Farey-serien, då . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Bevis.

Observera att triangeln är i planet med hörn , och kan inte innehålla heltalspunkter annat än hörn. Annars, om hela punkten finns i , ligger bråkdelen mellan och , och nämnaren överstiger inte . Så enligt Peak-formeln är dess yta lika med . Å andra sidan är området . H. t. d. $A=(0,\;0)$ $B=(p_1,\;q_1)$ $C=(p_2,\;q_2)$ $(r,\;s)$ $\triangel ABC$ $r/s$ $p_1/q_1$ $p_2/q_2$ $s$ $\max\{q_1,\;q_2\}$ $1/2$ $\triangel ABC$ $(q_1p_2-q_2p_1)/2$

Det omvända är också sant: om bråken är sådana att , då är de angränsande medlemmar av Farey-serien . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$ $F_{\max\{q_1,q_2\}}$

Generationsalgoritm

Algoritmen för att generera alla bråk F n är mycket enkel, både i stigande och fallande ordning. Varje iteration av algoritmen bygger nästa fraktion baserat på de två föregående. Således, om och är två redan konstruerade bråk, och är nästa okända, då . Detta betyder att för något heltal , och är sant , alltså och . Eftersom det ska vara så nära som möjligt ställer vi in nämnaren på maximalt möjligt, det vill säga härifrån, med hänsyn till det faktum att det är ett heltal, har vi och ${\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 = \lgolv\frac{n + b}{d}\rgolv$

p = \vänster\lgolv\frac{n+b}{d}\höger\rgolv c - a

q = \vänster\lgolv\frac{n+b}{d}\höger\rgolv d - b

Implementeringsexempel i Python :

def farey ( n , asc = Sant ): om asc : a , b , c , d = 0 , 1 , 1 , n annat : a , b , c , d = 1 , 1 , n - 1 , n skriv ut " % d / %d " % ( a , b ) medan ( asc och c <= n ) eller ( inte asc och a > 0 ): k = int (( n + b ) / d ) a , b , c , d = c , d , k * c - a , k * d - b skriv ut " %d / %d " % ( a , b )

JavaScript- implementeringsexempel :

klass Bråk { konstruktor ( tal , valör ) { detta . numer = numer ; detta . denom = denom ; } copy () { returnera ny bråkdel ( detta . tal , detta . valör ); } } funktion * farey ( n , asc = sant ) { låt [ a , b ] = asc ? [ ny bråkdel ( 0 , 1 ), ny bråkdel ( 1 , n ) ] : [ ny bråkdel ( 1 , 1 ), ny bråkdel ( n - 1 , n ) ]; ge en . kopia (); while ( asc && b . numer <= n || ! asc && a . numer > 0 ) { yield b . kopia (); const k = Math . våning (( n + a . denom ) / b . denom ), nästa = ny Bråk ( k * b . numer - a . numer , k * b . denom - a . denom ); a = b _ b = nästa ; } }

Det är alltså möjligt att konstruera en godtyckligt stor mängd av alla bråk i förkortad form, som till exempel kan användas för att lösa den diofantiska ekvationen genom uttömmande sökning i rationella tal.

Historik

John Farey är en berömd geolog, en av pionjärerna inom geofysiken . Hans enda bidrag till matematiken var bråken uppkallad efter honom. År 1816 publicerades Fareys artikel "Om en nyfiken egenskap hos vulgära fraktioner", där han definierade sekvensen . Detta papper nådde Cauchy , som samma år publicerade ett bevis på Fareys gissning att varje ny term i ordningen Farey-sekvensen är medianen för dess grannar. Sekvensen som beskrevs av Farey 1816 användes av Charles Haros i hans papper från 1802 om approximation av decimaler med vanliga bråk. $F_{n}$ $n+1$

Se även

Länkar

Knop K. Icke-binärt system // Hemdator. - 2001. - Nr 8 . Arkiverad från originalet den 12 mars 2007.
Weisstein, Eric W. Farey Sequence (engelska) på Wolfram MathWorld- webbplatsen .
Täljare och nämnare för Farey-serien: OEIS -sekvens A006842 och OEIS - sekvens A006843 .