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 .
A harmadrendű Farey sorozat az összes pozitív irreducibilis saját tört növekvő sorozata, amelyek nevezője kisebb vagy egyenlő, mint :
Egy rendelés Farey sorozata a következő szabállyal összeállítható a sorrendből :
Farey szekvenciák 1-től 8-ig:
Ha két szomszédos tört van a Farey sorozatban, akkor . |
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.
Ez fordítva is igaz: ha a törtek olyanok, hogy , akkor a Farey sorozat szomszédos tagjai .
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
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 .
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 .