Farey sor

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. december 6-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A Farey-sorozat (más néven Farey-törtek , Farey- sorozat vagy Farey- tabló ) a racionális számok véges részhalmazainak családja .

Definíció

A harmadrendű Farey sorozat az összes pozitív irreducibilis saját tört növekvő sorozata, amelyek nevezője kisebb vagy egyenlő, mint : $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\}.

Egy rendelés Farey sorozata a következő szabállyal összeállítható a sorrendből : $n+1$ $n$

A sorrend összes elemét másoljuk . $n$
Ha a rendsorozat két szomszédos törtében a nevezők összege nem nagyobb számot ad, mint , akkor ezek közé a törtek közé beillesztjük a mediánjukat , amely megegyezik a számlálóik összegének a nevezők összegéhez viszonyított arányával. $n$ $n+1$

Példa

Farey szekvenciák 1-től 8-ig: $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}\jobbra\}.

Tulajdonságok

Ha két szomszédos tört van a Farey sorozatban, akkor . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Bizonyíték.

Vegye figyelembe, hogy a háromszög a csúcsokkal rendelkező síkban van , és nem tartalmazhat más egész pontokat, csak csúcsokat. Ellenkező esetben, ha az egész pont benne van , akkor a tört és között van , és a nevező nem haladja meg a -t . Tehát a Peak formula szerint a területe egyenlő . Másrészt a terület . H. t. d. $A=(0,\;0)$ $B=(p_1,\;q_1)$ $C=(p_2,\;q_2)$ $(r,\;s)$ $\háromszög ABC$ $r/s$ $p_1/q_1$ $p_2/q_2$ $s$ $\max\{q_1,\;q_2\}$ $1/2$ $\háromszög ABC$ $(q_1p_2-q_2p_1)/2$

Ez fordítva is igaz: ha a törtek olyanok, hogy , akkor a Farey sorozat szomszédos tagjai . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$ $F_{\max\{q_1,q_2\}}$

Generációs algoritmus

Az összes F n tört előállítási algoritmusa nagyon egyszerű, mind növekvő, mind csökkenő sorrendben. Az algoritmus minden iterációja az előző kettő alapján felépíti a következő törtet. Így ha és két már megszerkesztett tört, és a következő ismeretlen, akkor . Ez azt jelenti, hogy valamilyen egész számra és igaz , tehát és . Mivel a lehető legközelebb kell lennie a -hoz , akkor a nevezőt a lehető legnagyobbra állítjuk , vagyis innen, figyelembe véve azt, hogy egész szám, van és ${\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

Megvalósítási példa Pythonban :

def farey ( n , asc = igaz ): ha asc : a , b , c , d = 0 , 1 , 1 , n else : a , b , c , d = 1 , 1 , n - 1 , n print " % d / %d " % ( a , b ) míg ( asc és c <= n ) vagy ( nem emelkedő és a > 0 ): k = int ( ( n + b ) / d ) a , b , c , d = c , d , k * c - a , k * d - b nyomtatás " %d / %d " % ( a , b )

JavaScript megvalósítási példa :

class Tört { konstruktor ( szám , denom ) { this . numer = szám ; ezt . denom = denom ; } copy () { return new Tört ( ez . szám , ez . denom ); } } function * farey ( n , asc = igaz ) { legyen [ a , b ] = asc ? [ új Tört ( 0 , 1 ), új Tört ( 1 , n ) ] : [ új Tört ( 1 , 1 ), új Tört ( n - 1 , n ) ]; hozam a . másolat (); while ( asc && b . numer <= n || ! asc && a . numer > 0 ) { hozam b . másolat (); const k = Math . emelet (( n + a . denom ) / b . denom ), next = new Tört ( k * b . numer - a . numer , k * b . denom - a . denom ); a = b _ b = következő ; } }

Így az összes törtből tetszőlegesen nagy halmazt lehet rövidített formában megszerkeszteni, amivel például racionális számokban kimerítő kereséssel megoldható a diofantini egyenlet .

Történelem

John Farey híres geológus, a geofizika egyik úttörője . Egyetlen hozzájárulása a matematikához a róla elnevezett törtek voltak. 1816-ban megjelent Farey "A vulgáris frakciók különös tulajdonságáról" című cikke, amelyben meghatározta a sorozatot . Ez a tanulmány eljutott Cauchy -hoz , aki ugyanabban az évben bizonyítékot közölt a Farey-sejtésről, amely szerint a Farey-sorrend minden új tagja a szomszédjainak mediánja . A Farey által 1816-ban leírt sorozatot Charles Haros használta a tizedesjegyek közönséges törtekkel való közelítéséről szóló 1802-es tanulmányában . $F_{n}$ $n+1$

Lásd még

Linkek

Knop K. Nem bináris rendszer // Otthoni számítógép. - 2001. - 8. sz . Az eredetiből archiválva: 2007. március 12.
Weisstein, Eric W. Farey Sequence (angol) a Wolfram MathWorld webhelyén .
A Farey-sorozat számlálói és nevezői: OEIS - szekvencia A006842 és OEIS - szekvencia A006843 .