Grådig algoritme til egyptiske brøker

Den grådige algoritme for egyptiske brøker er en grådig algoritme , der konverterer rationelle tal til egyptiske brøker , idet den ved hvert trin vælger den størst mulige aliquot , der kan bruges i restbrøken.

Nedbrydningen opnået af en grådig algoritme for tallet kaldes den grådige egyptiske dekomponering , Sylvester -nedbrydningen eller Fibonacci-Sylvester-nedbrydningen af tallet . $x$ $x$

Historie

Blandt flere forskellige metoder til at konstruere egyptiske fraktioner givet af Fibonacci i Abacusbogen var en grådig algoritme, som blev foreslået kun at blive brugt, hvis andre metoder mislykkedes [1] . Efterfølgende blev den grådige algoritme og dens udvidelser til at tilnærme irrationelle tal genopdaget flere gange, hvor det tidligste og mest berømte tilfælde var Sylvester- algoritmen [2] [3] . En metode, der giver den nærmeste tilnærmelse ved hvert trin, hvor negative brøker er tilladt, tilhører Lambert [4] .

Algoritme og eksempler

Fibonacci-algoritmen udfører dekomponering ved sekventiel udskiftning: $x/y$

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

(om nødvendigt forenkles anden term). For eksempel:

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

I denne udvidelse er nævneren for den første aliquot resultatet af afrunding til det næste (højere) hele tal, og resten er resultatet af reduktionen . Divisor af den anden brøk - , - er resultatet af at runde op til det næste (større) hele tal, og resten er det, der er tilbage efter subtraktion og . $3$ $15/7$ $2/15$ $(-15{\pmod 7})/(15\cdot 3)=6/45$ $otte$ $15/2$ $1/120$ $15/7$ $1/3$ $1/8$

Fordi hvert udvidelsestrin mindsker tælleren for resten, vil denne metode fuldføres i et begrænset antal trin. Men sammenlignet med gamle egyptiske nedbrydningsmetoder eller mere moderne metoder, kan denne metode give en nedbrydning med ret store nævnere. For eksempel den grådige udvidelse af et tal : $5/121$

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

mens andre metoder giver en meget enklere udvidelse:

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

og for den grådige algoritme giver den en udvidelse til ti brøker, hvoraf den sidste har 500 cifre i nævneren, mens der er en repræsentation [5] : $31/311$

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

Sylvesters sekvens

Sylvester-sekvensen kan repræsenteres som værende dannet af den uendelige udvidelse af enhed ved hjælp af en grådig algoritme, hvor der ved hvert trin vælges en nævner i stedet for . Hvis vi afskærer denne sekvens med udtryk og danner den tilsvarende egyptiske brøk, for eksempel for : $2,3,7,43,1807,\prikker$ $\lgulv y/x\rgulv +1$ $\lceil y/x\rceil$ $k$ $k = 4$

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

så opnår vi den nærmeste tilnærmelse til nedefra blandt egyptiske fraktioner med medlemmer [6] [7] . For eksempel kræver enhver egyptisk brøk mindst fem led for et tal i et åbent område . Anvendelsen af sådanne nærmeste udvidelser for et lavere estimat af antallet af divisorer af et perfekt tal [6] såvel som i gruppeteori [8] er beskrevet . $en$ $k$ $(1805/1806.1)$

Maksimal længdeudvidelser og modulo-betingelser

Enhver brøk giver de maksimale udtryk i den grådige algoritme. De forhold, hvorunder ekspansionen kræver nøjagtigt fraktioner [9] [10] er undersøgt , disse forhold kan beskrives i form af modulo sammenligninger: $x/y$ $x$ $x/y$ $x$ $y$

enhver brøk fører til et led i udvidelsen, den enkleste sådan brøk er ; $1/år$ $1/1$
enhver brøkdel af formen for ulige kræver to led i udvidelsen, den enkleste sådan brøk er ; $2/år$ $y>1$ $2/3$
i udvidelsen af en brøk , er tre udtryk nødvendige, hvis og kun hvis , i dette tilfælde, og er ulige, så resten af udvidelsen efter det første trin: $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 enkleste brøkdel af formen , hvilket giver en udvidelse med tre medlemmer - ; $3/år$ $3/7$
udvidelse af en brøk giver fire led, hvis og kun hvis eller . I disse tilfælde er tælleren for restbrøken lig , og nævneren er sammenlignelig med . Den enkleste brøkdel af arten med fire ekspansionsled er , Erdős-Strauss-formodningen siger, at alle fraktioner af arten har en nedbrydning med tre eller færre led, men for eller sådanne udvidelser bør søges ved andre metoder end den grådige algoritme. $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 generelle tilfælde, sekvensen af brøker med minimumsnævneren , der udvides med en grådig algoritme med medlemmer [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)),\prikker

Tilnærmet beregning af rødderne af polynomier

Der findes en metode til tilnærmet beregning af rødderne af et polynomium baseret på den grådige algoritme [12] [13] , der bestemmer den grådige nedbrydning af roden. Ved hvert trin dannes et ekstra polynomium, som har resten af udvidelsen som en rod. For at beregne den grådige udvidelse af det gyldne snit som en af de to løsninger til ligningen , udfører algoritmen følgende trin. $P_{0}(x)=x^{2}-x-1=0$

Da roden for og for alle skal være mellem og . Udvidelsens første sigt er således . Hvis er resten efter det første trin af den grådige ekspansion, skal ligningen være opfyldt , som kan konverteres til . $P_{0}(x)<0$ $x=1$ $P_{0}(x)>0$ $x\geqslant 2$ $P_{0}(x)$ $en$ $2$ $1/1$ $x_{1}$ $P_{0}(x_{1}+1)=0$ $P_{1}(x_{1})=x_{1}^{2}+x_{1}-1=0$
Da roden for og for alle ligger mellem og , er det første led i udvidelsen (det andet led i udvidelsen af det gyldne snit) . Hvis er resten efter dette grådige ekspansionstrin, opfylder det ligningen , som kan konverteres til . $P_{1}(x)<0$ $x=1/2$ $P_{1}(x)>0$ $x>1$ $P_1$ $1/2$ $en$ $x_{1}$ $1/2$ $x_{2}$ $P_{1}(x_{2}+1/2)=0$ $P_{2}(x_{2})=4x_{2}^{2}+8x_{2}-1=0$
Da for og for alle er næste termin i udvidelsen . Hvis er resten efter dette grådige ekspansionstrin, opfylder det ligningen , som kan konverteres til en ligning 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$

Ved at fortsætte denne tilnærmelsesproces opnår man udvidelsen af det gyldne snit til en egyptisk fraktion [14] :

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

Andre heltalssekvenser

Længden, minimumsnævneren og maksimumnævneren af den grådige udvidelse for brøker med små tællere og nævnere er inkluderet i Encyclopedia of Integer Sequences [15] . Derudover fører den grådige udvidelse af ethvert irrationelt tal til en uendelig stigende sekvens af heltal, og OEIS indeholder udvidelser af nogle velkendte konstanter.

Relaterede udvidelser

Det er muligt at definere en grådig algoritme med nogle begrænsninger for nævneren:

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

hvor er valgt blandt alle værdier, der opfylder de pålagte begrænsninger og har den mindst mulige værdi, ved hvilken og sådan, der adskiller sig fra alle tidligere nævnere. For eksempel kan Engel-dekomponeringen opfattes som en algoritme af denne type, hvor hver tilladelig nævner skal opnås ved at gange den foregående med et heltal. Det er dog ofte ikke-trivielt at fastslå, om en sådan algoritme altid fører til en endelig dekomponering. Især er den ulige grådige udvidelse af en brøk dannet af en grådig algoritme med en begrænsning på de ulige nævnere. Det er kendt, at der for ulige er en udvidelse til en egyptisk brøk, hvor alle nævnere er ulige, men om en ulige grådig algoritme altid vil føre til en endelig udvidelse er ukendt. $d$ $xd>y$ $d$ $x/y$ $y$

Noter

↑ Sigler, 2002 , kapitel II.7
↑ Sylvester, 1880 .
↑ Cahen, 1891 .
↑ Lambert, 1770 .
↑ Vogn, 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 diophantiske problem // American Mathematical Monthly . - 1922. - T. 29 , Nr. 10 . — S. 380–387 . - doi : 10.2307/2299023 . — .
HT Freitag, GM Phillips. Anvendelser af Fibonacci-numre, 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. Et værste tilfælde af Fibonacci-Sylvester-udvidelsen // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1987. - T. 1 . — s. 141–148 .
H.E. Salzer. Tilnærmelsen af tal som summer af gensidige // American Mathematical Monthly . - 1947. - T. 54 , Nr. 3 . — S. 135–142 . - doi : 10.2307/2305906 . — .
H.E. Salzer. Yderligere bemærkninger om tilnærmelse af tal som summer af gensidige // American Mathematical Monthly . - 1948. - T. 55 , Nr. 6 . — S. 350–356 . - doi : 10.2307/2304960 . — .
Laurence E. Sigler (oversættelse). Fibonaccis Liber Abaci. - Springer-Verlag, 2002. - ISBN 0-387-95419-8 .
K. Soundarajan. Tilnærmelsesvis 1 nedefra ved hjælp af n egyptiske brøker. - 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. Pseudofrie handlinger og den grådige algoritme // 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. Om et punkt i teorien om vulgære brøker // American Journal of Mathematics . - 1880. - T. 3 , Nr. 4 . — S. 332–335 . - doi : 10.2307/2369261 . — .
S. Vogn. Mathematica i aktion . - W. H. Freeman, 1991. - S. 271-277 .