Mohó algoritmus egyiptomi törtekhez

Az egyiptomi törtek mohó algoritmusa egy mohó algoritmus , amely a racionális számokat egyiptomi törtekké alakítja , és minden lépésben kiválasztja a maradék törtben felhasználható legnagyobb alikvot részt.

A szám mohó algoritmusával kapott dekompozíciót mohó egyiptomi dekompozíciónak , Sylvester dekompozíciónak vagy a szám Fibonacci-Sylveszter dekompozíciójának nevezzük . $x$ $x$

Történelem

A Fibonacci által az Abacus könyvében megadott egyiptomi törtek megalkotásának számos különböző módszere között volt egy mohó algoritmus, amelyet csak akkor javasoltak használni, ha más módszerek kudarcot vallanak [1] . Ezt követően többször újra felfedezték a mohó algoritmust és az irracionális számok közelítésére szolgáló kiterjesztéseit, a legkorábbi és leghíresebb eset a Sylvester algoritmus [2] [3] . Lamberthez tartozik egy módszer, amely minden lépésnél a legközelebbi közelítést adja meg, amelyre negatív törtek megengedettek .

Algoritmus és példák

A Fibonacci algoritmus szekvenciális helyettesítéssel hajtja végre a dekompozíciót: $x/y$

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

(szükség esetén leegyszerűsítve a második kifejezést). Például:

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

Ebben a bővítésben az első aliquot nevezője a következő (nagyobb) egész számra való felkerekítés eredménye, a maradék pedig a csökkentés eredménye . A második tört osztója - , - a következő (nagyobb) egész számra kerekítés eredménye, a maradék pedig az és a kivonás után megmarad . $3$ $15/7$ $2/15$ $(-15{\pmod 7})/(15\cdot 3)=6/45$ $nyolc$ $15/2$ $1/120$ $7/15$ $1/3$ $1/8$

Mivel minden bővítési lépés csökkenti a maradék számlálóját, ez a módszer véges számú lépésben fejeződik be. Az ókori egyiptomi dekompozíciós módszerekhez vagy a modernebb módszerekhez képest azonban ez a módszer meglehetősen nagy nevezőkkel tud dekompozíciót adni. Például egy szám mohó kiterjesztése : $5/121$

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

míg más módszerek sokkal egyszerűbb bővítést adnak:

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

a mohó algoritmusnál pedig tíz törtre való kiterjesztést ad, amelyek közül az utolsónak 500 számjegye van a nevezőben, míg van egy reprezentáció [5] : $31/311$

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

Sylvester sorozata

A Sylvester sorozatot úgy ábrázolhatjuk, hogy az egység végtelen kibővítésével jött létre egy mohó algoritmus segítségével, ahol minden lépésben egy nevezőt választunk a helyett . Ha ezt a sorozatot kifejezésekkel levágjuk, és létrehozzuk a megfelelő egyiptomi törtet, például : $2,3,7,43,1807,\pontok$ $\lfloor y/x\rfloor +1$ $\lceil y/x\rceil$ $k$ $k = 4$

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

akkor a [6] [7] tagú egyiptomi törtek közül a legközelebbi közelítést kapjuk alulról . Például bármely egyiptomi törthez legalább öt tagra van szükség egy nyitott tartományban lévő számhoz . Leírják az ilyen legközelebbi bővítések alkalmazását egy tökéletes szám osztói számának alacsonyabb becslésére [6] , valamint a csoportelméletben [8] . $egy$ $k$ $(1805/1806.1)$

Maximális hosszkiterjesztések és modulo feltételek

Bármely tört megadja a maximális tagokat a mohó algoritmusban. Vizsgálják azokat a feltételeket, amelyek mellett a bővítéshez pontosan törtekre van szükség [9] [10] , ezeket a feltételeket modulo összehasonlítással lehet leírni: $x/y$ $x$ $x/y$ $x$ $y$

bármely tört egy taghoz vezet a bővítésben, a legegyszerűbb ilyen tört a ; $1/év$ $1/1$
A páratlan alak bármely törtrésze két tagot igényel a bővítésben, a legegyszerűbb ilyen tört a ; $2/év$ $y>1$ $2/3$
egy tört kiterjesztésekor három tagra akkor és csak akkor van szükség, ha , ebben az esetben és páratlan, tehát az első lépés után a bővítés maradéka: $3/y$ $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}}$ irreducibilis, a forma legegyszerűbb törtrésze , amely háromtagú bővítést ad - ; $3/y$ $3/7$
egy tört kiterjesztése akkor és csak akkor ad négy tagot, ha vagy . Ezekben az esetekben a maradék tört számlálója egyenlő , a nevező pedig a -hoz hasonlítható . A faj legegyszerűbb , négy bővítési tagú törtrésze a , az Erdős-Strauss-sejtés azt állítja, hogy a faj minden frakciója rendelkezik három vagy annál kevesebb taggal, de az ilyen bővítéseket a mohó algoritmustól eltérő módszerekkel kell keresni. $4/y$ $y\equiv 1{\pmod {24}}$ $y\equiv 17{\pmod {24}}$ $y{\bmod x}$ $3$ $1{\pmod 6}$ $4/y$ $4/17$ $4/y$ $y\equiv 1{\pmod 2}4$ $y\equiv 17{\pmod 2}4$

Általános esetben a minimális nevezővel rendelkező törtek sorozata , amely egy mohó algoritmussal bővíthető tagokkal [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

Polinomok gyökeinek hozzávetőleges számítása

Létezik egy módszer a polinom gyökeinek közelítő kiszámítására a mohó algoritmus [12] [13] alapján, amely meghatározza a gyökér mohó dekompozícióját. Minden lépésben egy további polinom jön létre, amelynek gyöke a kiterjesztés maradék része. Például az aranymetszet mohó kiterjesztésének kiszámításához az egyenlet két megoldásának egyikeként , az algoritmus a következő lépéseket hajtja végre. $P_{0}(x)=x^{2}-x-1=0$

Mivel a for and for all gyökérnek és között kell lennie . Így a bővítés első tagja . Ha a maradék a mohó bővítés első lépése után, akkor teljesülnie kell az egyenletnek , amely átváltható -ra . $P_{0}(x)<0$ $x=1$ $P_{0}(x)>0$ $x\geqslant 2$ $P_{0}(x)$ $egy$ $2$ $1/1$ $x_{1}$ $P_{0}(x_{1}+1)=0$ $P_{1}(x_{1})=x_{1}^{2}+x_{1}-1=0$
Mivel for and for all , a gyök és között van , az első tag a bővítésben (a második tag az aranymetszet bővítésében) a . Ha e mohó bővítési lépés után a maradék, akkor az kielégíti az egyenletet , amely átalakítható -ra . $P_{1}(x)<0$ $x=1/2$ $P_{1}(x)>0$ $x>1$ $P_1$ $1/2$ $egy$ $x_{1}$ $1/2$ $x_{2}$ $P_{1}(x_{2}+1/2)=0$ $P_{2}(x_{2})=4x_{2}^{2}+8x_{2}-1=0$
Mivel mindenki számára a következő kifejezés a kiterjesztésben . Ha e mohó bővítési lépés után a maradék, akkor az teljesíti az egyenletet , amely egész együtthatós egyenletté alakítható . $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$

Ezt a közelítési folyamatot folytatva megkapjuk az aranymetszet egyiptomi törtté való kiterjesztését [14] :

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

Egyéb egész sorozatok

A kis számlálóval és nevezővel rendelkező törtek mohó bővítésének hosszát, minimális nevezőjét és maximális nevezőjét az Integer Sequences Encyclopedia of Integer Sequences [15] tartalmazza . Ezenkívül bármely irracionális szám mohó kiterjesztése egész számok végtelen növekvő sorozatához vezet, az OEIS pedig néhány jól ismert állandó kiterjesztését tartalmazza.

Kapcsolódó bővítések

Lehetőség van mohó algoritmus meghatározására a nevezőre vonatkozó bizonyos korlátozásokkal:

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

ahol az összes olyan érték közül kerül kiválasztásra, amelyek megfelelnek a megszabott korlátozásoknak és a lehető legkisebb értékkel rendelkeznek, amelyen és amelyen eltér az összes korábbi nevezőtől. Például az Engel-felbontás felfogható egy ilyen típusú algoritmusnak, amelyben minden megengedett nevezőt úgy kell megkapni, hogy az előzőt megszorozzuk valamilyen egész számmal. Azonban gyakran nem triviális annak megállapítása, hogy egy ilyen algoritmus mindig véges dekompozícióhoz vezet-e. Egy tört páratlan mohó kiterjesztését egy mohó algoritmus képezi, a páratlan nevezők korlátozásával. Ismeretes, hogy a páratlan egy egyiptomi törtté bővül, amelyben minden nevező páratlan, de nem ismert, hogy egy páratlan mohó algoritmus mindig véges bővüléshez vezet-e. $d$ $xd>y$ $d$ $x/y$ $y$

Jegyzetek

↑ Sigler, 2002 , II.7. fejezet
↑ Sylvester, 1880 .
↑ Cahen, 1891 .
↑ Lambert, 1770 .
↑ Kocsi, 1991 .
↑ 12 Curtiss , 1922 .
↑ Soundarajan, 2005 .
↑ Stong, 1983 .
↑ 1987. május .
↑ Freitag, Phillips, 1999 .
↑ OEIS szekvencia A048860 _
↑ Stratemeyer, 1930 .
↑ Salzer, 1947 .
↑ OEIS szekvencia A117116 _
↑ A050205 , A050206 , A050210

Irodalom

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. A Kellogg-diofantin problémáról // American Mathematical Monthly . - 1922. - T. 29 , sz. 10 . – S. 380–387 . - doi : 10.2307/2299023 . — .
HT Freitag, GM Phillips. Fibonacci-számok alkalmazásai, Vol. 8 (Rochester, NY, 1998). Dordrecht: Kluwer Acad. Publ., 1999, 155–163.
JH Lambert. Beyträge zum Gebrauche der Mathematik und deren Anwendung. - Berlin: Zweyter Theil, 1770. - S. 99-104 .
Michael Mays. A Fibonacci–Sylvester expanzió legrosszabb esete // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1987. - T. 1 . – 141–148 .
H. E. Salzer. A számok közelítése reciprok összegeként // American Mathematical Monthly . - 1947. - T. 54 , sz. 3 . – S. 135–142 . - doi : 10.2307/2305906 . — .
H. E. Salzer. További megjegyzések a számok közelítéséhez a reciprok összegeiként // American Mathematical Monthly . - 1948. - T. 55 , sz. 6 . – S. 350–356 . - doi : 10.2307/2304960 . — .
Laurence E. Sigler (ford.). Fibonacci Liber Abacija. - Springer-Verlag, 2002. - ISBN 0-387-95419-8 .
K. Soundarajan. 1-et alulról közelítve n egyiptomi tört felhasználásával. - 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. Álmentes cselekvések és a mohó algoritmus // Mathematische Annalen. - 1983. - T. 265 , sz. 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. A vulgáris törtek elméletének egy pontjáról // American Journal of Mathematics . - 1880. - T. 3 , sz. 4 . – S. 332–335 . - doi : 10.2307/2369261 . — .
S. Wagon. Mathematica in Action . - W. H. Freeman, 1991. - S. 271-277 .