Farey række

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. december 2019; checks kræver 3 redigeringer .

Farey-rækker (også Farey-brøker , Farey -sekvens eller Farey- tableau ) er en familie af endelige delmængder af rationelle tal .

Definition

th-ordens Farey-sekvensen er en stigende række af alle positive irreducerbare egenbrøker , hvis nævner er mindre end eller lig 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 af en ordre kan konstrueres ud fra ordresekvensen ved følgende regel: $n+1$ $n$

Vi kopierer alle elementerne i rækkefølgen . $n$
Hvis summen af nævnerne i to tilstødende brøker af rækkefølgen giver et tal, der ikke er større end , så indsætter vi deres median mellem disse brøker , svarende til forholdet mellem summen af deres tællere og summen af nævnerne. $n$ $n+1$

Eksempel

Farey-sekvenser for 1 til 8: $n$

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

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

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

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

F_5=\venstre\{\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=\venstre\{\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=\venstre\{\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=\venstre\{\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\}.

Egenskaber

Hvis der er to tilstødende fraktioner i Farey-serien, så . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Bevis.

Bemærk, at trekanten er i planen med toppunkter , og ikke kan indeholde heltalspunkter ud over toppunkter. Ellers, hvis hele punktet er indeholdt i , så ligger brøken mellem og , og nævneren overstiger ikke . Så ifølge Peak-formlen er dens areal lig med . Til gengæld er området . H. t. d. $A=(0,\;0)$ $B=(p_1,\;q_1)$ $C=(p_2,\;q_2)$ $(r,\;s)$ $\trekant ABC$ $r/s$ $p_1/q_1$ $p_2/q_2$ $s$ $\max\{q_1,\;q_2\}$ $1/2$ $\trekant ABC$ $(q_1p_2-q_2p_1)/2$

Det modsatte er også sandt: Hvis brøkerne er sådan, at , så er de nabomedlemmer af Farey-serien . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$ $F_{\max\{q_1,q_2\}}$

Generationsalgoritme

Algoritmen til at generere alle brøker F n er meget enkel, både i stigende og faldende rækkefølge. Hver iteration af algoritmen bygger den næste fraktion baseret på de to foregående. Således, hvis og er to allerede konstruerede brøker, og er den næste ukendte, så . Dette betyder, at for nogle heltal , og er sandt , dermed og . Da det skal være så tæt som muligt på , så sætter vi nævneren til at være den maksimalt mulige, det vil sige herfra, under hensyntagen til det faktum, at det er et heltal, har vi og ${\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 = \lgulv\frac{n + b}{d}\rgulv$

p = \venstre\lgulv\frac{n+b}{d}\højre\rgulv c - a

q = \venstre\lgulv\frac{n+b}{d}\højre\rgulv d - b

Implementeringseksempel i Python :

def farey ( n , asc = Sand ): hvis asc : a , b , c , d = 0 , 1 , 1 , n andet : a , b , c , d = 1 , 1 , n - 1 , n print " % d / %d " % ( a , b ) mens ( asc og c <= n ) eller ( ikke asc og a > 0 ): k = int (( n + b ) / d ) a , b , c , d = c , d , k * c - a , k * d - b udskriv " %d / %d " % ( a , b )

Eksempel på implementering af JavaScript :

klasse Brøk { konstruktør ( tal , betegnelse ) { dette . tal = tal ; dette . denom = denom ; } copy () { return new Brøk ( dette . tal , dette . denom ); } } funktion * farey ( n , asc = sand ) { lad [ a , b ] = asc ? [ ny brøk ( 0 , 1 ), ny brøk ( 1 , n ) ] : [ ny brøk ( 1 , 1 ), ny brøk ( n - 1 , n ) ]; give et . kopi (); mens ( asc && b . tal <= n || ! asc && a . numer > 0 ) { udbytte b . kopi (); const k = Matematik . etage (( n + a . denom ) / b . denom ), næste = ny Brøk ( k * b . tal - a . tal , k * b . denom - a . denom ); a = b _ b = næste ; } }

Det er således muligt at konstruere et vilkårligt stort sæt af alle brøker i en forkortet form, som fx kan bruges til at løse den diofantiske ligning ved udtømmende søgning i rationelle tal.

Historie

John Farey er en berømt geolog, en af geofysikkens pionerer . Hans eneste bidrag til matematik var brøkerne opkaldt efter ham. I 1816 blev Fareys artikel "On a curious property of vulgære fraktions" publiceret, hvori han definerede sekvensen . Dette papir nåede Cauchy , som samme år offentliggjorde et bevis på Fareys formodning om, at hver ny term i ordenen Farey-sekvensen er medianen af dens naboer. Sekvensen beskrevet af Farey i 1816 blev brugt af Charles Haros i hans papir fra 1802 om tilnærmelse af decimaler ved almindelige brøker. $F_{n}$ $n+1$