Algoritm lacom pentru fracțiile egiptene

Algoritmul greedy pentru fracțiile egiptene este un algoritm lacom care convertește numerele raționale în fracții egiptene , alegând la fiecare pas cea mai mare alicotă posibilă care poate fi utilizată în fracția reziduală.

Descompunerea obținută de un algoritm lacom pentru număr se numește descompunerea egipteană lacomă , descompunerea lui Sylvester sau descompunerea numărului Fibonacci-Sylvester . $X$ $X$

Istorie

Printre mai multe metode diferite de construire a fracțiilor egiptene date de Fibonacci în Cartea Abacului a fost un algoritm lacom, care a fost sugerat să fie folosit numai dacă alte metode au eșuat [1] . Ulterior, algoritmul greedy și extensiile sale pentru aproximarea numerelor iraționale au fost redescoperite de mai multe ori, cel mai vechi și mai faimos caz fiind algoritmul Sylvester [2] [3] . O metodă care oferă cea mai apropiată aproximare la fiecare pas, pentru care sunt permise fracții negative, îi aparține lui Lambert [4] .

Algoritm și exemple

Algoritmul Fibonacci efectuează descompunerea prin înlocuire secvențială: $X y$

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

(simplificarea celui de-al doilea termen dacă este necesar). De exemplu:

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

În această expansiune, numitorul primei alicote este rezultatul rotunjirii la următorul număr întreg (mai mare), iar restul este rezultatul reducerii . Împărțitorul celei de-a doua fracții - , - este rezultatul rotunjirii la următorul număr întreg (mai mare), iar restul este ceea ce rămâne după scăderea și . $3$ $15/7$ $2/15$ $(-15{\pmod 7})/(15\cdot 3)=6/45$ $opt$ $15/2$ $1/120$ $7/15$ $1/3$ $1/8$

Deoarece fiecare pas de extindere scade numărătorul restului, această metodă se va finaliza într-un număr finit de pași. Cu toate acestea, în comparație cu metodele egiptene antice de descompunere sau cu metodele mai moderne, această metodă poate da o descompunere cu numitori destul de mari. De exemplu, expansiunea lacomă a unui număr : $5/121$

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

în timp ce alte metode oferă o extindere mult mai simplă:

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

iar pentru algoritmul lacom, dă o expansiune în zece fracții, ultima dintre acestea având 500 de cifre la numitor, în timp ce există o reprezentare [5] : $31/311$

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

secvența lui Sylvester

Secvența Sylvester poate fi reprezentată ca fiind formată din expansiunea infinită a unității prin intermediul unui algoritm lacom, unde la fiecare pas se alege un numitor în loc de . Dacă tăiem această secvență cu termeni și formăm fracția egipteană corespunzătoare, de exemplu, pentru : $2,3,7,43,1807,\dots$ $\lfloor y/x\rfloor +1$ $\lceil y/x\rceil$ $k$ $k = 4$

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

atunci obținem cea mai apropiată aproximare de dedesubt dintre fracțiile egiptene cu membri [6] [7] . De exemplu, orice fracție egipteană necesită cel puțin cinci termeni pentru un număr dintr-un interval deschis . Este descrisă aplicarea acestor expansiuni cele mai apropiate pentru o estimare mai mică a numărului de divizori ai unui număr perfect [6] , precum și în teoria grupurilor [8] . $unu$ $k$ $(1805/1806.1)$

Expansiuni de lungime maximă și condiții modulo

Orice fracție oferă termenii maximi în algoritmul lacom. Sunt investigate condițiile în care expansiunea necesită exact fracții [9] [10] , aceste condiții pot fi descrise în termeni de comparații modulo: $X y$ $X$ $X y$ $X$ $y$

orice fracție duce la un termen în expansiune, cea mai simplă astfel de fracție este ; $1/a$ $1/1$
orice fracție de formă pentru impar necesită doi termeni în expansiune, cea mai simplă astfel de fracție este ; $2/a$ $y>1$ $2/3$
în expansiunea unei fracții , sunt necesari trei termeni dacă și numai dacă , în acest caz, și este impar, deci restul expansiunii după primul pas: $3/a$ $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}}$ ireductibil, cea mai simplă fracțiune a formei , dând o expansiune cu trei membri - ; $3/a$ $3/7$
expansiunea unei fracții dă patru termeni dacă și numai dacă sau . În aceste cazuri, numărătorul fracției reziduale este egal și numitorul este comparabil cu . Cea mai simplă fracțiune a speciei cu patru termeni de expansiune este , conjectura Erdős-Strauss afirmă că toate fracțiile speciei au o descompunere cu trei sau mai puțini termeni, dar pentru sau astfel de expansiuni ar trebui căutate prin alte metode decât algoritmul lacom. $4/a$ $y\equiv 1{\pmod {24}}$ $y\equiv 17{\pmod {24}}$ $y{\bmod x}$ $3$ $1{\pmod 6}$ $4/a$ $4/17$ $4/a$ $y\equiv 1{\pmod 2}4$ $y\equiv 17{\pmod 2}4$

În cazul general, succesiunea fracțiilor cu numitorul minim , având expansiune printr-un algoritm lacom cu membri [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

Calculul aproximativ al rădăcinilor polinoamelor

Există o metodă de calcul aproximativ al rădăcinilor unui polinom bazată pe algoritmul greedy [12] [13] care determină descompunerea lacomă a rădăcinii. La fiecare pas, se formează un polinom suplimentar, care are ca rădăcină restul expansiunii. De exemplu, pentru a calcula expansiunea lacomă a secțiunii de aur ca una dintre cele două soluții ale ecuației , algoritmul efectuează următorii pași. $P_{0}(x)=x^{2}-x-1=0$

Deoarece pentru și pentru toți , rădăcina trebuie să fie între și . Astfel, primul termen al expansiunii este . Dacă este restul după primul pas al expansiunii lacome, trebuie îndeplinită ecuația , care poate fi convertită în . $P_{0}(x)<0$ $x=1$ $P_{0}(x)>0$ $x\geqslant 2$ $P_{0}(x)$ $unu$ $2$ $1/1$ $x_{1}$ $P_{0}(x_{1}+1)=0$ $P_{1}(x_{1})=x_{1}^{2}+x_{1}-1=0$
Deoarece pentru și pentru toți , rădăcina se află între și , primul termen din expansiune (al doilea termen din extinderea secțiunii de aur) este . Dacă este restul după acest pas de expansiune lacom, acesta satisface ecuația , care poate fi convertită în . $P_{1}(x)<0$ $x=1/2$ $P_{1}(x)>0$ $x>1$ $P_1$ $1/2$ $unu$ $x_{1}$ $1/2$ $x_{2}$ $P_{1}(x_{2}+1/2)=0$ $P_{2}(x_{2})=4x_{2}^{2}+8x_{2}-1=0$
Deoarece pentru și pentru toți , următorul termen în expansiune este . Dacă este restul după acest pas de expansiune lacom, aceasta satisface ecuația , care poate fi convertită într-o ecuație cu coeficienți întregi . $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$

Continuând acest proces de aproximare, se obține extinderea secțiunii de aur într-o fracție egipteană [14] :

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

Alte secvențe întregi

Lungimea, numitorul minim și numitorul maxim al expansiunii lacome pentru fracțiile cu numărători și numitori mici sunt incluse în Enciclopedia secvențelor întregi [15] . În plus, expansiunea lacomă a oricărui număr irațional duce la o succesiune infinită de numere întregi, iar OEIS conține expansiuni ale unor constante binecunoscute.

Extinderi înrudite

Este posibil să definiți un algoritm lacom cu unele restricții asupra numitorului:

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

unde se alege dintre toate valorile care îndeplinesc restricțiile impuse și au cea mai mică valoare posibilă, la care și astfel care diferă de toți numitorii anteriori. De exemplu, descompunerea Engel poate fi gândită ca un algoritm de acest tip, în care fiecare numitor admisibil trebuie obținut prin înmulțirea celui precedent cu un număr întreg. Cu toate acestea, este adesea netrivial să se stabilească dacă un astfel de algoritm duce întotdeauna la o descompunere finită. În special , expansiunea impară greedy a unei fracții este formată dintr-un algoritm greedy cu o restricție asupra numitorilor impari. Se știe că pentru impar există o expansiune într-o fracție egipteană în care toți numitorii sunt impari, dar nu se știe dacă un algoritm lacom impar va duce întotdeauna la o expansiune finită. $d$ $xd>y$ $d$ $X y$ $y$

Note

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

Literatură

E. Cahen. Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fractions continue // Nouvelles Annales des Mathématiques. - 1891. - T. 10 . — S. 508–514 .
D. R. Curtis. Despre problema diofantică a lui Kellogg // American Mathematical Monthly . - 1922. - T. 29 , nr. 10 . — S. 380–387 . - doi : 10.2307/2299023 . — .
HT Freitag, GM Phillips. Aplicații ale numerelor Fibonacci, Vol. 8 (Rochester, NY, 1998). Dordrecht: Kluwer Acad. Publ., 1999, p. 155–163.
JH Lambert. Beyträge zum Gebrauche der Mathematik und deren Anwendung. - Berlin: Zweyter Theil, 1770. - S. 99-104 .
Michael Mays. Cel mai rău caz al expansiunii Fibonacci–Sylvester // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1987. - T. 1 . — p. 141–148 .
S.E. Salzer. Aproximarea numerelor ca sume de reciproce // American Mathematical Monthly . - 1947. - T. 54 , nr. 3 . — S. 135–142 . - doi : 10.2307/2305906 . — .
S.E. Salzer. Alte observații despre aproximarea numerelor ca sume de reciproce // American Mathematical Monthly . - 1948. - T. 55 , nr. 6 . — S. 350–356 . - doi : 10.2307/2304960 . — .
Laurence E. Sigler (trad.). Liber Abaci al lui Fibonacci. - Springer-Verlag, 2002. - ISBN 0-387-95419-8 .
K. Soundarajan. Aproximând 1 de jos folosind n fracții egiptene. - 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. Acțiuni pseudolibere și algoritmul lacom // 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. Pe un punct din teoria fracțiilor vulgare // American Journal of Mathematics . - 1880. - T. 3 , nr. 4 . — S. 332–335 . - doi : 10.2307/2369261 . — .
S. Vagon. Mathematica în acțiune . - W. H. Freeman, 1991. - S. 271-277 .