Ahne algoritmi Egyptin murtoluvuille

Egyptin murto - osien ahne algoritmi on ahne algoritmi , joka muuntaa rationaaliset luvut egyptiläisiksi murtoluvuiksi ja valitsee jokaisessa vaiheessa suurimman mahdollisen alikvootin , jota voidaan käyttää jäännösmurtoluvussa.

Lukulle ahneella algoritmilla saatua hajotusta kutsutaan ahneeksi egyptiläiseksi hajotukseksi , Sylvester -hajotelmaksi tai luvun Fibonacci-Sylvester- hajotukseksi . $x$ $x$

Historia

Fibonaccin Abacus - kirjassa esittämien Egyptin murtolukujen muodostamismenetelmien joukossa oli ahne algoritmi, jota ehdotettiin käytettäväksi vain, jos muut menetelmät epäonnistuivat [1] . Myöhemmin ahne algoritmi ja sen laajennukset irrationaalisten lukujen approksimoimiseksi löydettiin uudelleen useita kertoja, varhaisin ja tunnetuin tapaus oli Sylvester -algoritmi [2] [3] . Menetelmä, joka antaa lähimmän likiarvon kussakin vaiheessa, jolle negatiiviset murtoluvut ovat sallittuja, kuuluu Lambertille [4] .

Algoritmi ja esimerkit

Fibonacci-algoritmi suorittaa hajotuksen peräkkäisellä korvauksella: $x/y$

{\frac {x}{y}}={\frac {1}{\lceil y/x\rceil }}+{\frac {(-y){\bmod x}}{y\lceil y/x\ rceil}}

(yksinkertaistaa tarvittaessa toista termiä). Esimerkiksi:

{\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1} {8}}+{\frac {1}{120}}

Tässä laajennuksessa ensimmäisen alikvootin nimittäjä saadaan pyöristämällä ylöspäin seuraavaan (suurempaan) kokonaislukuun, ja loppuosa on vähennyksen tulos . Toisen murtoluvun jakaja - , - saadaan pyöristämällä ylöspäin seuraavaan (suurempaan) kokonaislukuun, ja jäännös on se, mikä jää jäljelle vähentämisen ja . $3$ $15/7$ $2/15$ $(-15{\pmod 7})/(15\cdot 3)=6/45$ $kahdeksan$ $15/2$ $1/120$ $7/15$ $1/3$ $1/8$

Koska jokainen laajennusvaihe pienentää jäännöksen osoittajaa, tämä menetelmä valmistuu äärellisessä määrässä vaiheita. Kuitenkin verrattuna muinaisiin egyptiläisiin hajotusmenetelmiin tai nykyaikaisimpiin menetelmiin tämä menetelmä voi antaa hajotuksen melko suurilla nimittäjillä. Esimerkiksi luvun ahne laajennus : $5/121$

{\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763309}}+{\frac {1}{873960180913}}+{\frac {1} {1527612795642093418846225}}

kun taas muut menetelmät antavat paljon yksinkertaisemman laajennuksen:

{\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}

ja ahneelle algoritmille se antaa laajennuksen kymmeneen murto-osaan, joista viimeisen nimittäjässä on 500 numeroa, kun taas on esitys [5] : $31/311$

{\frac 1{12}}+{\frac 1{63}}+{\frac 1{2799}}+{\frac 1{8708}}

Sylvesterin sekvenssi

Sylvester-sekvenssi voidaan esittää muodostuneen yksikön äärettömällä laajennuksella ahneella algoritmilla, jossa jokaisessa vaiheessa valitaan nimittäjä :n sijaan . Jos katkaisemme tämän sekvenssin termeillä ja muodostamme vastaavan egyptiläisen murto-osan, esimerkiksi : $2,3,7,43,1807,\pistettä$ $\lfloor y/x\rfloor +1$ $\lceil y/x\rceil$ $k$ $k = 4$

{\frac 12}+{\frac 13}+{\frac 17}+{\frac 1{43}}={\frac {1805}{1806}}

niin saadaan lähin likiarvo alhaalta Egyptin murtoluvuista, joissa on jäseniä [6] [7] . Esimerkiksi mikä tahansa egyptiläinen murtoluku edellyttää vähintään viisi termiä avoimen alueen luvulle . Sellaisten lähimpien laajennusten soveltaminen täydellisen luvun jakajien lukumäärän pienempään estimaatiin [6] sekä ryhmäteoriassa [8] kuvataan . $yksi$ $k$ $(1805/1806.1)$

Maksimipituuslaajennukset ja moduloehdot

Mikä tahansa murtoluku antaa ahneen algoritmin enimmäistermit. Olosuhteet, joissa laajennus vaatii täsmälleen murto -osia [9] [10] , tutkitaan , nämä olosuhteet voidaan kuvata modulo-vertailuilla: $x/y$ $x$ $x/y$ $x$ $y$

mikä tahansa murtoluku johtaa yhteen termiin laajennuksessa, yksinkertaisin tällainen murtoluku on ; $1/v$ $1/1$
mikä tahansa parittoman muodon murto-osa vaatii laajennuksessa kaksi termiä, yksinkertaisin tällainen murtoluku on ; $2/v$ $y>1$ $2/3$
murtoluvun laajennuksessa tarvitaan kolme termiä, jos ja vain jos , tässä tapauksessa ja on pariton, joten ensimmäisen vaiheen jälkeinen laajennuksen loppuosa: $3/v$ $y\equiv 1{\pmod 6}$ $y=2{\pmod x}$ $y(y+2)/3$ ${\frac {(-y){\bmod x}}{y\lceil y/x\rceil }}={\frac 2{y(y+2)/3}}$ redusoitumaton, muodon yksinkertaisin murto-osa , joka antaa kolmijäsenisen laajennuksen - ; $3/v$ $3/7$
murto-osan laajennus antaa neljä termiä jos ja vain jos tai . Näissä tapauksissa jäännösmurto-osuuden osoittaja on yhtä suuri ja nimittäjä on verrattavissa . Lajin yksinkertaisin osa neljällä laajennustermillä on , Erdős-Straussin arvelussa sanotaan, että kaikilla lajin murto - osilla on kolmen tai vähemmän termin hajoaminen, mutta tällaisia laajennuksia tulisi etsiä muilla menetelmillä kuin ahneella algoritmilla. $4/v$ $y\equiv 1{\pmod {24}}$ $y\equiv 17{\pmod {24}}$ $y{\bmod x}$ $3$ $1{\pmod 6}$ $4/v$ $4/17$ $4/v$ $y\equiv 1{\pmod 2}4$ $y\equiv 17{\pmod 2}4$

Yleisessä tapauksessa murto-osien sarja, jonka nimittäjä on pienin ja joka laajenee ahneella algoritmilla, jossa on jäseniä [11] : $x/y$ $y$ $x$

1,{\frac {2}{3)),{\frac {3}{7)),{\frac {4}{17)),{\frac {5}{31)),{\frac { 6}{109)),{\frac {7}{253)),{\frac {8}{97)),{\frac {9}{271)),\dots

Polynomien juurien likimääräinen laskelma

On olemassa menetelmä polynomin juurien likimääräiseen laskemiseen, joka perustuu ahneeseen algoritmiin [12] [13] , joka määrittää juuren ahneen hajoamisen. Jokaisessa vaiheessa muodostetaan ylimääräinen polynomi, jonka juurena on loppuosa laajennuksesta. Esimerkiksi laskeakseen kultaisen leikkauksen ahneen laajennuksen yhdeksi yhtälön kahdesta ratkaisusta , algoritmi suorittaa seuraavat vaiheet. $P_{0}(x)=x^{2}-x-1=0$

Koska for ja for all , juuren on oltava välillä ja . Laajennuksen ensimmäinen termi on siis . Jos on jäännös ahneen laajennuksen ensimmäisen vaiheen jälkeen, yhtälön tulee täyttyä , joka voidaan muuntaa muotoon . $P_{0}(x)<0$ $x=1$ $P_{0}(x)>0$ $x\geqslant 2$ $P_{0}(x)$ $yksi$ $2$ $1/1$ $x_{1}$ $P_{0}(x_{1}+1)=0$ $P_{1}(x_{1})=x_{1}^{2}+x_{1}-1=0$
Koska ja kaikille , Juuri sijaitsee välillä ja , ensimmäinen termi laajennus (toinen termi laajentaminen kultainen leikkaus) on . Jos on tämän ahneen laajennusvaiheen jälkeen jäävä osa, se täyttää yhtälön , joka voidaan muuntaa muotoon . $P_{1}(x)<0$ $x = 1/2$ $P_{1}(x)>0$ $x>1$ $P_1$ $1/2$ $yksi$ $x_{1}$ $1/2$ $x_{2}$ $P_{1}(x_{2}+1/2)=0$ $P_{2}(x_{2})=4x_{2}^{2}+8x_{2}-1=0$
Koska kaikille , laajennuksen seuraava termi on . Jos on tämän ahneen laajennusvaiheen jälkeen jäävä osa, se täyttää yhtälön , joka voidaan muuntaa yhtälöksi kokonaislukukertoimilla . $P_{2}(x)<0$ $x = 1/9$ $P_{2}(x)>0$ $x>1/8$ $1/9$ $x_{3}$ $P_{2}(x_{3}+1/9)=0$ $P_{3}(x_{3})=324x_{3}^{2}+720x_{3}-5=0$

Jatkamalla tätä lähentämisprosessia saadaan kultaleikkauksen laajennus egyptiläiseksi jakeeksi [14] :

\varphi ={\frac 11}+{\frac 12}+{\frac 19}+{\frac 1{145}}+{\frac 1{37986}}}+\cdots

Muut kokonaislukusekvenssit

Pienillä osoittajilla ja nimittäjillä olevien murtolukujen ahneen laajennuksen pituus, pienin nimittäjä ja maksiminimittäjä sisältyvät Encyclopedia of Integer Sequences [15] . Lisäksi minkä tahansa irrationaalisen luvun ahne laajennus johtaa äärettömään kasvavaan kokonaislukujonoon, ja OEIS sisältää joidenkin hyvin tunnettujen vakioiden laajennuksia.

Aiheeseen liittyvät laajennukset

On mahdollista määritellä ahne algoritmi tietyin nimittäjän rajoituksin:

{\frac {x}{y}}={\frac {1}{d}}+{\frac {xd-y}{yd}}

jossa valitaan kaikista arvoista, jotka täyttävät asetetut rajoitukset ja joilla on pienin mahdollinen arvo, jolla ja sellaisella, joka eroaa kaikista aikaisemmista nimittäjistä. Esimerkiksi Engel-hajotelma voidaan ajatella tämän tyyppisenä algoritmina, jossa jokainen sallittu nimittäjä on hankittava kertomalla edellinen jollain kokonaisluvulla. Usein ei kuitenkaan ole triviaalia määrittää, johtaako tällainen algoritmi aina äärelliseen hajoamiseen. Erityisesti murto -osan pariton ahne laajennus muodostetaan ahneella algoritmilla, jossa on rajoitus parittomille nimittäjille. Tiedetään, että parittomalla on laajennus egyptiläiseksi murto-osaksi, jossa kaikki nimittäjät ovat parittomia, mutta johtaako pariton ahne algoritmi aina äärelliseen laajennukseen, ei tiedetä. $d$ $xd>y$ $d$ $x/y$ $y$

Muistiinpanot

↑ Sigler, 2002 , luku II.7
↑ Sylvester, 1880 .
↑ Cahen, 1891 .
↑ Lambert, 1770 .
↑ Wagon, 1991 .
↑ 12 Curtiss , 1922 .
↑ Soundarajan, 2005 .
↑ Stong, 1983 .
↑ Toukokuu, 1987 .
↑ Freitag, Phillips, 1999 .
↑ OEIS - sekvenssi A048860 _
↑ Stratemeyer, 1930 .
↑ Salzer, 1947 .
↑ OEIS - sekvenssi A117116 _
↑ A050205 , A050206 , A050210

Kirjallisuus

E. Cahen. Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fractions jatkuu // Nouvelles Annales des Mathématiques. - 1891. - T. 10 . — S. 508–514 .
D. R. Curtis. Kelloggin diofantiiniongelmasta // American Mathematical Monthly . - 1922. - T. 29 , no. 10 . — S. 380–387 . - doi : 10.2307/2299023 . — .
HT Freitag, GM Phillips. Fibonacci-lukujen sovellukset, Voi. 8 (Rochester, NY, 1998). Dordrecht: Kluwer Acad. Publ., 1999, s. 155–163.
JH Lambert. Beyträge zum Gebrauche der Mathematik und deren Anwendung. - Berliini: Zweyter Theil, 1770. - S. 99-104 .
Michael Mays. Fibonacci–Sylvesterin laajennuksen pahin tapaus // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1987. - T. 1 . — s. 141–148 .
H.E. Salzer. Lukujen approksimaatio käänteissummana // American Mathematical Monthly . - 1947. - T. 54 , no. 3 . — S. 135–142 . - doi : 10.2307/2305906 . — .
H.E. Salzer. Lisähuomautuksia lukujen likiarvosta käänteissummaina // American Mathematical Monthly . - 1948. - T. 55 , no. 6 . - S. 350-356 . - doi : 10.2307/2304960 . — .
Laurence E. Sigler (käänn.). Fibonaccin Liber Abaci. - Springer-Verlag, 2002. - ISBN 0-387-95419-8 .
K. Soundarajan. Arvioidaan 1 alhaalta käyttäen n egyptiläistä murtolukua. - 2005. - arXiv : math.CA/0502247 .
O. Spiess. Über eine Klasse unendlicher Reihen // Archiv der Mathematik und Physik, Ser. 3. - 1907. - T. 12 . — S. 124–134 .
R.E. Stong. Pseudovapaat toimet ja ahne algoritmi // Mathematische Annalen. - 1983. - T. 265 , no. 4 . — S. 501–512 . - doi : 10.1007/BF01455950 .
G. Stratemeyer. Stammbruchentwickelungen für die Quadratwurzel aus einer rationalen Zahl // Mathematische Zeitschrift. - 1930. - T. 31 . — S. 767–768 . - doi : 10.1007/BF01246446 .
JJ Sylvester. Kohdasta vulgaaristen murtolukujen teoriassa // American Journal of Mathematics . - 1880. - T. 3 , no. 4 . — S. 332–335 . - doi : 10.2307/2369261 . — .
S. Wagon. Mathematica toiminnassa . - W. H. Freeman, 1991. - S. 271-277 .