Chamtivý algoritmus pro egyptské zlomky

Chamtivý algoritmus pro egyptské zlomky je chamtivý algoritmus , který převádí racionální čísla na egyptské zlomky , přičemž v každém kroku vybírá největší možný alikvot , který lze použít ve zbytkovém zlomku.

Rozklad získaný chamtivým algoritmem pro číslo se nazývá chamtivý egyptský rozklad , Sylvesterův rozklad nebo Fibonacciho-Sylvesterův rozklad čísla . $X$ $X$

Historie

Mezi několika různými metodami pro konstrukci egyptských zlomků daný Fibonacci v Book of the Abacus byl chamtivý algoritmus, který byl navržen k použití pouze v případě, že jiné metody selhaly [1] . Následně byl chamtivý algoritmus a jeho rozšíření pro aproximaci iracionálních čísel několikrát znovu objeven, nejstarším a nejznámějším případem byl Sylvesterův algoritmus [2] [3] . Metoda, která v každém kroku udává nejbližší aproximaci, pro kterou jsou povoleny záporné zlomky, patří Lambertovi [4] .

Algoritmus a příklady

Fibonacciho algoritmus provádí rozklad postupným nahrazováním: $x/y$

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

(v případě potřeby zjednodušení druhého termínu). Například:

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

V tomto rozšíření je jmenovatel prvního alikvotu výsledkem zaokrouhlení nahoru na další (vyšší) celé číslo a zbytek je výsledkem snížení . Dělitel druhého zlomku - , - je výsledkem zaokrouhlení nahoru na další (větší) celé číslo a zbytek je to, co zbyde po odečtení a . $3$ $15/7$ $2/15$ $(-15{\pmod 7})/(15\cdot 3)=6/45$ $osm$ $15/2$ $1/120$ $7/15$ $1/3$ $1/8$

Protože každý krok rozšíření snižuje čitatel zbytku, bude tato metoda dokončena v konečném počtu kroků. Ve srovnání se staroegyptskými metodami rozkladu nebo modernějšími metodami však tato metoda může poskytnout rozklad s poměrně velkými jmenovateli. Například chamtivé rozšíření čísla : $5/121$

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

zatímco jiné metody poskytují mnohem jednodušší rozšíření:

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

a pro chamtivý algoritmus poskytuje rozšíření do deseti zlomků, z nichž poslední má 500 číslic ve jmenovateli, přičemž existuje reprezentace [5] : $31/311$

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

Sylvesterova sekvence

Sylvesterova posloupnost může být reprezentována jako tvořená nekonečnou expanzí jednoty pomocí chamtivého algoritmu, kde je v každém kroku zvolen jmenovatel místo . Pokud tuto posloupnost ořízneme členy a vytvoříme odpovídající egyptský zlomek, například pro : $2,3,7,43,1807,\tečky$ $\lpatro y/x\rpatro +1$ $\lceil y/x\rceil$ $k$ $k = 4$

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

pak získáme z egyptských zlomků se členy nejbližší aproximaci zdola [6] [7] . Například jakýkoli egyptský zlomek vyžaduje alespoň pět výrazů pro číslo v otevřeném rozsahu . Je popsáno použití takových nejbližších rozšíření pro nižší odhad počtu dělitelů dokonalého čísla [6] , stejně jako v teorii grup [8] . $jeden$ $k$ $(1805/1806,1)$

Rozšíření maximální délky a podmínky modulo

Libovolný zlomek poskytuje maximální podmínky v chamtivém algoritmu. Jsou zkoumány podmínky, za kterých expanze vyžaduje přesně zlomky [9] [10] , tyto podmínky lze popsat pomocí modulových srovnání: $x/y$ $X$ $x/y$ $X$ $y$

jakýkoli zlomek vede k jednomu členu v expanzi, nejjednodušší takový zlomek je ; $1/r$ $1/1$
jakýkoli zlomek tvaru pro liché vyžaduje dva členy v rozšíření, nejjednodušší takový zlomek je ; $2/r$ $y>1$ $2/3$
v expanzi zlomku jsou potřeba tři členy právě tehdy, když , v tomto případě a je liché, takže zbytek rozšíření po prvním kroku: $3/r$ $y\ekviv 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}}$ neredukovatelný, nejjednodušší zlomek tvaru , dává expanzi se třemi členy - ; $3/r$ $3/7$
expanze zlomku dává čtyři členy tehdy a jen tehdy, když nebo . V těchto případech je čitatel zbytkového zlomku roven a jmenovatel je srovnatelný s . Nejjednodušší zlomek druhů se čtyřmi členy expanze je , Erdős-Straussův dohad uvádí, že všechny zlomky druhů mají rozklad se třemi nebo méně členy, ale pro nebo takové expanze by měly být hledány jinými metodami než chamtivým algoritmem. $4/r$ $y\ekviv 1{\pmod {24}}$ $y\equiv 17{\pmod {24}}$ $y{\bmod x}$ $3$ $1{\pmod 6}$ $4/r$ $4/17$ $4/r$ $y\ekviv 1{\pmod 2}4$ $y\equiv 17{\pmod 2}4$

V obecném případě posloupnost zlomků s minimálním jmenovatelem , která se rozšiřuje o chamtivý algoritmus se členy [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)),\tečky

Přibližný výpočet kořenů polynomů

Existuje metoda pro přibližný výpočet kořenů polynomu založená na greedy algoritmu [12] [13] , který určuje hrabivý rozklad kořene. V každém kroku se vytvoří další polynom, který má zbytek rozšíření jako kořen. Například pro výpočet zištné expanze zlatého řezu jako jednoho ze dvou řešení rovnice provede algoritmus následující kroky. $P_{0}(x)=x^{2}-x-1=0$

Protože pro a pro všechny musí být kořen mezi a . První termín expanze je tedy . Pokud je zbytek po prvním kroku chamtivé expanze, musí být splněna rovnice , kterou lze převést na . $P_{0}(x)<0$ $x=1$ $P_{0}(x)>0$ $x\geqslant 2$ $P_{0}(x)$ $jeden$ $2$ $1/1$ $x_{1}$ $P_{0}(x_{1}+1)=0$ $P_{1}(x_{1})=x_{1}^{2}+x_{1}-1=0$
Protože pro a pro všechny , kořen leží mezi a , první člen v expanzi (druhý člen v expanzi zlatého řezu) je . Pokud je zbytek po tomto kroku chamtivé expanze, splňuje rovnici , kterou lze převést na . $P_{1}(x)<0$ $x = 1/2$ $P_{1}(x)>0$ $x>1$ $P_1$ $1/2$ $jeden$ $x_{1}$ $1/2$ $x_{2}$ $P_{1}(x_{2}+1/2)=0$ $P_{2}(x_{2})=4x_{2}^{2}+8x_{2}-1=0$
Protože pro a pro všechny je dalším termínem rozšíření . Pokud je zbytek po tomto chtivém expanzním kroku, splňuje rovnici , kterou lze převést na rovnici s celočíselnými koeficienty . $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$

Pokračujeme-li v tomto procesu aproximace, získáme expanzi zlatého řezu na egyptský zlomek [14] :

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

Další celočíselné posloupnosti

Délka, minimální jmenovatel a maximální jmenovatel zištného rozšíření pro zlomky s malými čitateli a jmenovateli jsou zahrnuty v Encyklopedie celočíselných sekvencí [15] . Navíc chamtivé rozšiřování jakéhokoli iracionálního čísla vede k nekonečné rostoucí posloupnosti celých čísel a OEIS obsahuje rozšíření některých dobře známých konstant.

Související rozšíření

Je možné definovat chamtivý algoritmus s určitými omezeními ve jmenovateli:

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

kde je vybráno ze všech hodnot, které splňují uložená omezení a mají nejmenší možnou hodnotu, při které a takové, které se liší od všech předchozích jmenovatelů. Například Engelův rozklad lze považovat za algoritmus tohoto typu, ve kterém každý přípustný jmenovatel musí být získán vynásobením předchozího nějakým celým číslem. Je však často netriviální zjistit, zda takový algoritmus vždy vede ke konečnému rozkladu. Zejména liché chamtivé rozšíření zlomku je tvořeno chamtivým algoritmem s omezením na liché jmenovatele. Je známo, že pro liché existuje expanze do egyptského zlomku, ve kterém jsou všichni jmenovatelé lichí, ale zda lichý chamtivý algoritmus vždy povede ke konečnému rozšíření, není známo. $d$ $xd>y$ $d$ $x/y$ $y$

Poznámky

↑ Sigler, 2002 , kapitola II.7
↑ Silvestr, 1880 .
↑ Cahen, 1891 .
↑ Lambert, 1770 .
↑ Vůz, 1991 .
↑ 12 Curtiss , 1922 .
↑ Soundarajan, 2005 .
↑ Stong, 1983 .
↑ Květen, 1987 .
↑ Freitag, Phillips, 1999 .
↑ OEIS sekvence A048860 _
↑ Stratemeyer, 1930 .
↑ Salzer, 1947 .
↑ OEIS sekvence A117116 _
↑ A050205 , A050206 , A050210

Literatura

E. Cahen. Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en zlomky pokračuje // Nouvelles Annales des Mathématiques. - 1891. - T. 10 . — S. 508–514 .
D. R. Curtis. O Kelloggově diofantickém problému // American Mathematical Monthly . - 1922. - T. 29 , čís. 10 . — S. 380–387 . - doi : 10.2307/2299023 . — .
HT Freitag, GM Phillips. Aplikace Fibonacciho čísel, sv. 8 (Rochester, NY, 1998). Dordrecht: Kluwer Acad. Publ., 1999, s. 155–163.
JH Lambert. Beyträge zum Gebrauche der Mathematik und deren Anwendung. - Berlín: Zweyter Theil, 1770. - S. 99-104 .
Michael Mays. Nejhorší případ Fibonacciho-Sylvesterova rozšíření // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1987. - T. 1 . — s. 141–148 .
H. E. Salzer. Aproximace čísel jako součtů převrácených hodnot // American Mathematical Monthly . - 1947. - T. 54 , čís. 3 . — S. 135–142 . - doi : 10.2307/2305906 . — .
H. E. Salzer. Další poznámky k aproximaci čísel jako součtů převrácených hodnot // American Mathematical Monthly . - 1948. - T. 55 , čís. 6 . — S. 350–356 . - doi : 10.2307/2304960 . — .
Laurence E. Sigler (přel.). Fibonacciho Liber Abaci. - Springer-Verlag, 2002. - ISBN 0-387-95419-8 .
K. Soundarajan. Aproximace 1 zdola pomocí n egyptských zlomků. - 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. Pseudofree akce a chamtivý algoritmus // Mathematische Annalen. - 1983. - T. 265 , čís. 4 . — S. 501–512 . - doi : 10.1007/BF01455950 .
G. Stratemeyer. Stammbruchentwickelungen für die Quadratwurzel aus einer reasonen Zahl // Mathematische Zeitschrift. - 1930. - T. 31 . — S. 767–768 . - doi : 10.1007/BF01246446 .
JJ Sylvester. K bodu v teorii vulgárních zlomků // American Journal of Mathematics . - 1880. - T. 3 , čís. 4 . — S. 332–335 . - doi : 10.2307/2369261 . — .
S. Vagon. Mathematica v akci . - W. H. Freeman, 1991. - S. 271-277 .