Girig algoritm för egyptiska bråk

Den giriga algoritmen för egyptiska bråk är en girig algoritm som omvandlar rationella tal till egyptiska bråk , och väljer vid varje steg den största möjliga alikvoten som kan användas i restbråket.

Nedbrytningen som erhålls av en girig algoritm för numret kallas den giriga egyptiska nedbrytningen , Sylvester -nedbrytningen eller Fibonacci-Sylvester-nedbrytningen av talet . $x$ $x$

Historik

Bland flera olika metoder för att konstruera egyptiska fraktioner som Fibonacci gav i Abacusboken fanns en girig algoritm, som föreslogs användas endast om andra metoder misslyckades [1] . Därefter återupptäcktes den giriga algoritmen och dess förlängningar för att approximera irrationella tal flera gånger, det tidigaste och mest kända fallet var Sylvester- algoritmen [2] [3] . En metod som ger närmaste approximation vid varje steg, för vilken negativa bråk är tillåtna, tillhör Lambert [4] .

Algoritm och exempel

Fibonacci-algoritmen utför nedbrytning genom sekventiell ersättning: $x/y$

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

(förenkla den andra termen vid behov). Till exempel:

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

I denna expansion är nämnaren för den första alikvoten resultatet av avrundning uppåt till nästa (högre) heltal, och resten är resultatet av reduktionen . Divisorn för den andra bråkdelen - , - är resultatet av avrundning uppåt till nästa (större) heltal, och resten är det som är kvar efter subtrahering och . $3$ $15/7$ $15/2$ $(-15{\pmod 7})/(15\cdot 3)=6/45$ $åtta$ $15/2$ $1/120$ $15/7$ $1/3$ $1/8$

Eftersom varje expansionssteg minskar täljaren för resten, kommer denna metod att slutföras i ett begränsat antal steg. Men jämfört med forntida egyptiska nedbrytningsmetoder eller mer moderna metoder kan denna metod ge en nedbrytning med ganska stora nämnare. Till exempel, den giriga expansionen av ett nummer : $5/121$

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

medan andra metoder ger en mycket enklare expansion:

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

och för den giriga algoritmen ger den en expansion till tio bråk, varav den sista har 500 siffror i nämnaren, medan det finns en representation [5] : $31/311$

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

Sylvesters sekvens

Sylvester-sekvensen kan representeras som bildad av den oändliga expansionen av enhet med hjälp av en girig algoritm, där vid varje steg en nämnare väljs istället för . Om vi skär av denna sekvens med termer och bildar motsvarande egyptiska bråk, till exempel för : $2,3,7,43,1807,\prickar$ $\lgolv y/x\rgolv +1$ $\lceil y/x\rceil$ $k$ $k = 4$

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

då får vi den närmaste approximationen till underifrån bland egyptiska bråk med medlemmar [6] [7] . Till exempel kräver varje egyptisk bråkdel minst fem termer för ett tal i ett öppet intervall . Tillämpningen av sådana närmaste expansioner för en lägre uppskattning av antalet divisorer av ett perfekt antal [6] , samt i gruppteorin [8] beskrivs . $ett$ $k$ $(1805/1806.1)$

Maximal längdexpansion och modulovillkor

Vilken bråkdel som helst ger de maximala termerna i den giriga algoritmen. Förhållandena under vilka expansionen kräver exakt fraktioner [9] [10] undersöks , dessa förhållanden kan beskrivas i termer av modulo-jämförelser: $x/y$ $x$ $x/y$ $x$ $y$

vilket bråk som helst leder till en term i expansionen, det enklaste bråket är ; $1/år$ $1/1$
varje bråkdel av formen för udda kräver två termer i expansionen, den enklaste bråkdelen är ; $2/år$ $y>1$ $2/3$
i expansionen av en bråkdel behövs tre termer om och endast om , i detta fall, och är udda, så resten av expansionen efter det första steget: $3/år$ $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}}$ irreducible, den enklaste bråkdelen av formen , vilket ger en expansion med tre medlemmar - ; $3/år$ $3/7$
expansion av ett bråk ger fyra termer om och endast om eller . I dessa fall är täljaren för restbråket lika och nämnaren är jämförbar med . Den enklaste fraktionen av arten med fyra expansionstermer är , Erdős-Strauss-förmodan säger att alla fraktioner av arten har en nedbrytning med tre eller färre termer, men för eller sådana expansioner bör sökas med andra metoder än den giriga algoritmen. $4/år$ $y\equiv 1{\pmod {24}}$ $y\equiv 17{\pmod {24}}$ $y{\bmod x}$ $3$ $1{\pmod 6}$ $4/år$ $17/4$ $4/år$ $y\equiv 1{\pmod 2}4$ $y\equiv 17{\pmod 2}4$

I det allmänna fallet, sekvensen av bråk med minsta nämnaren , som har expansion med en girig algoritm med medlemmar [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)),\prickar

Ungefärlig beräkning av polynomens rötter

Det finns en metod för ungefärlig beräkning av rötterna till ett polynom baserat på den giriga algoritmen [12] [13] som bestämmer rotens giriga nedbrytning. Vid varje steg bildas ytterligare ett polynom, som har resten av expansionen som en rot. Till exempel, för att beräkna den giriga expansionen av det gyllene snittet som en av de två lösningarna till ekvationen , utför algoritmen följande steg. $P_{0}(x)=x^{2}-x-1=0$

Eftersom för och för alla måste roten ligga mellan och . Den första termen av expansionen är alltså . Om är resten efter det första steget av den giriga expansionen, måste ekvationen vara uppfylld , som kan konverteras till . $P_{0}(x)<0$ $x=1$ $P_{0}(x)>0$ $x\geqslant 2$ $P_{0}(x)$ $ett$ $2$ $1/1$ $x_{1}$ $P_{0}(x_{1}+1)=0$ $P_{1}(x_{1})=x_{1}^{2}+x_{1}-1=0$
Eftersom för och för alla ligger roten mellan och , den första termen i expansionen (den andra termen i expansionen av det gyllene snittet) är . Om är resten efter detta giriga expansionssteg, uppfyller den ekvationen , som kan konverteras till . $P_{1}(x)<0$ $x=1/2$ $P_{1}(x)>0$ $x>1$ $P_1$ $1/2$ $ett$ $x_{1}$ $1/2$ $x_{2}$ $P_{1}(x_{2}+1/2)=0$ $P_{2}(x_{2})=4x_{2}^{2}+8x_{2}-1=0$
Eftersom för och för alla är nästa termin i expansionen . Om är resten efter detta giriga expansionssteg, uppfyller den ekvationen , som kan omvandlas till en ekvation med heltalskoefficienter . $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$

Genom att fortsätta denna approximationsprocess erhåller man expansionen av det gyllene snittet till en egyptisk fraktion [14] :

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

Andra heltalssekvenser

Längden, minsta nämnaren och maximala nämnaren för den giriga expansionen för bråk med små täljare och nämnare ingår i Encyclopedia of Integer Sequences [15] . Dessutom leder den giriga expansionen av alla irrationella tal till en oändligt ökande sekvens av heltal, och OEIS innehåller expansioner av några välkända konstanter.

Relaterade expansioner

Det är möjligt att definiera en girig algoritm med några begränsningar för nämnaren:

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

där väljs bland alla värden som uppfyller de pålagda restriktionerna och har minsta möjliga värde, vid vilket och sådant som skiljer sig från alla tidigare nämnare. Till exempel kan Engel-nedbrytningen ses som en algoritm av denna typ, där varje tillåten nämnare måste erhållas genom att multiplicera den föregående med något heltal. Det är dock ofta inte trivialt att fastställa om en sådan algoritm alltid leder till en ändlig nedbrytning. I synnerhet bildas den udda giriga expansionen av ett bråk av en girig algoritm med en begränsning av de udda nämnare. Det är känt att för udda finns en expansion till en egyptisk bråkdel där alla nämnare är udda, men om en udda girig algoritm alltid kommer att leda till en finit expansion är okänt. $d$ $xd>y$ $d$ $x/y$ $y$

Anteckningar

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

Litteratur

E. Cahen. Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fraktions continues // Nouvelles Annales des Mathématiques. - 1891. - T. 10 . — S. 508–514 .
D.R. Curtis. Om Kelloggs diofantproblem // American Mathematical Monthly . - 1922. - T. 29 , nr. 10 . — S. 380–387 . - doi : 10.2307/2299023 . — .
HT Freitag, GM Phillips. Tillämpningar av Fibonacci-nummer, vol. 8 (Rochester, NY, 1998). Dordrecht: Kluwer Acad. Publ., 1999, s. 155–163.
JH Lambert. Beyträge zum Gebrauche der Mathematik und deren Anwendung. - Berlin: Zweyter Theil, 1770. - S. 99-104 .
Michael Mays. Ett värsta fall av Fibonacci–Sylvester-expansionen // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1987. - T. 1 . — s. 141–148 .
H.E. Salzer. Approximationen av siffror som summor av reciproka // American Mathematical Monthly . - 1947. - T. 54 , nr. 3 . — S. 135–142 . - doi : 10.2307/2305906 . — .
H.E. Salzer. Ytterligare anmärkningar om approximation av siffror som summor av reciproka // American Mathematical Monthly . - 1948. - T. 55 , nr. 6 . — S. 350–356 . - doi : 10.2307/2304960 . — .
Laurence E. Sigler (översättning). Fibonaccis Liber Abaci. - Springer-Verlag, 2002. - ISBN 0-387-95419-8 .
K. Soundarajan. Ungefär 1 underifrån med n egyptiska bråk. - 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. Pseudofria handlingar och den giriga algoritmen // Mathematische Annalen. - 1983. - T. 265 , nr. 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. På en punkt i teorin om vulgära bråk // American Journal of Mathematics . - 1880. - T. 3 , nr. 4 . — S. 332–335 . - doi : 10.2307/2369261 . — .
S. Vagn. Mathematica in Action . - W. H. Freeman, 1991. - S. 271-277 .