Algorytm zachłanny dla ułamków egipskich

W matematyce algorytm zachłanny dla ułamków egipskich to algorytm zachłanny , po raz pierwszy opisany przez Fibonacciego , służący do przekształcania liczb wymiernych na ułamki egipskie . 5/6 jest Ułamek 1/2 np egipski = + 1/3 ułamków jednostkowych reprezentacją ułamka nieredukowalnego jako sumy odrębnych , . . Jak sama nazwa wskazuje, reprezentacje te były używane już w starożytnym Egipcie , ale pierwsza opublikowana systematyczna metoda konstruowania takich rozszerzeń została opisana w 1202 roku w Liber Abaci Leonarda z Pizy ( Fibonacciego). Nazywa się to algorytmem zachłannym, ponieważ na każdym kroku algorytm wybiera zachłannie największy możliwy ułamek jednostkowy , który można wykorzystać w dowolnej reprezentacji pozostałego ułamka.

Fibonacci faktycznie wymienia kilka różnych metod konstruowania reprezentacji ułamków egipskich. Uwzględnia metodę zachłanną jako ostateczność w sytuacjach, gdy zawodzi kilka prostszych metod; patrz frakcja egipska, aby uzyskać bardziej szczegółową listę tych metod. Jak podaje Salzer (1948), metoda chciwa i jej rozszerzenia służące do aproksymacji liczb niewymiernych były kilkakrotnie ponownie odkrywane przez współczesnych matematyków, najwcześniej, a przede wszystkim przez JJ Sylvestera ( 1880 ) . ) Ściśle powiązana metoda rozszerzania, która daje bliższe przybliżenia na każdym kroku, dopuszczając, aby niektóre ułamki jednostkowe sumy były ujemne, pochodzi z Lamberta (1770) .

Ekspansja uzyskana tą metodą dla liczby $Fibonacciego$ jest chciwą ekspansją egipską , ekspansją Sylwestra lub ekspansją – Sylvestra z ${\ displaystyle x}$ . Jednak termin rozwinięcie Fibonacciego zwykle odnosi się nie do tej metody, ale do reprezentacji liczb całkowitych jako sum liczb Fibonacciego .

Algorytm i przykłady

Algorytm Fibonacciego rozszerza ułamek, $ma$ być reprezentowany, poprzez wielokrotne

$${\ Displaystyle {\ Frac {x} {y}} = {\ Frac {1} {\ lewo \ lceil {\ Frac {y} }{x}}\right\rceil }}+{\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }} }$$

(w razie potrzeby upraszczając drugi termin w tym zastąpieniu). Na przykład:

$${\ Displaystyle {\ Frac {7} {15}} = {\ Frac {1} {3}} + {\ Frac {2} {15}} = {\ Frac {1} {3}} + {\ frac {1}{8}}+{\frac {1}{120}}.}$$

ułamka jednostkowego jest jest wynikiem zaokrąglenia 15/7 2/15 × w górę do następnej większej liczby całkowitej, a pozostały ułamek wynikiem uproszczenia −15 mod 7/15 3 = 6 / 45 . Mianownik w jest drugiego ułamka jednostkowego, 8 1/120 15/2 , wynikiem zaokrąglenia górę do następnej większej liczby całkowitej, a pozostały ułamek to to, co zostało z 7 / 15 po odjęciu 1 / 3 i 1 / 8 .

Ponieważ każdy krok rozwinięcia zmniejsza licznik pozostałego ułamka do rozwinięcia, metoda ta zawsze kończy się skończonym rozwinięciem; jednakże w porównaniu ze starożytnymi egipskimi ekspansjami lub bardziej nowoczesnymi metodami, ta metoda może dawać dość długie ekspansje z dużymi mianownikami. Na przykład ta metoda rozwija się

$${\ Frac {1} {25}}+{\frac {1}{757}}+{\frac {1}{763\,309}}+{\frac {1}{873\,960\,180\,913}}+ {\frac {1}{1\,527\,612\,795\,642\,093\,418\,846\,225}},}$$

podczas gdy inne metody prowadzą do znacznie lepszej ekspansji

$${\ Displaystyle {\ Frac {5} {121}} = {\ Frac {1} {33}} + {\ Frac {1} {121}} + {\ Frac {1} {363}}.}$$

Wagon (1991) sugeruje jeszcze bardziej niegrzeczny przykład, 31 / 311 . Metoda zachłanna prowadzi do rozwinięcia z dziesięcioma wyrazami, z których ostatni ma ponad 500 cyfr w mianowniku; jednak 31 / 311 ma znacznie krótszą reprezentację bez chciwości, 1 / 12 + 1 / 63 + 1 / 2799 + 1 / 8708 .

Sekwencja Sylwestra i najbliższe przybliżenie

Sekwencję Sylwestra 2, 3, 7, 43, 1807, ... ( OEIS : A000058 ) można postrzegać jako wygenerowaną przez nieskończoną zachłanną ekspansję tego typu dla liczby 1, gdzie na każdym kroku wybieramy mianownik ⌊ y / x ⌋ + 1 zamiast ⌈ y / x ⌉ . Skrócenie tej sekwencji do k wyrazów i utworzenie odpowiedniego ułamka egipskiego, np. (dla k = 4)

$${\ Displaystyle {\ Frac {1} {2}} + {\ Frac {1} {3}} + {\ Frac {1} {7}} + {\frac {1}{43}}={\frac {1805}{1806}}}$$

skutkuje najbliższym możliwym niedoszacowaniem 1 przez dowolny k -terminowy ułamek egipski. To znaczy, na przykład, dowolny ułamek egipski dla liczby w przedziale otwartym ( 1805 / 1806 , 1) wymaga co najmniej pięciu wyrazów. Curtiss (1922) opisuje zastosowanie tych wyników najbliższego przybliżenia do dolnego ograniczenia liczby dzielników liczby doskonałej , podczas gdy Stong (1983) opisuje zastosowania w teorii grup .

Rozwinięcia o maksymalnej długości i warunki kongruencji

Każdy ułamek x / y wymaga co najwyżej x wyrazów w swojej zachłannej ekspansji. Mays (1987) oraz Freitag i Phillips (1999) badają warunki, w których metoda chciwa daje ekspansję x / y z dokładnie x wyrazami; można je opisać w kategoriach warunków kongruencji na y .

• Każdy ułamek 1 / y wymaga jednego wyrazu w swojej zachłannej ekspansji; najprostszym takim ułamkiem jest 1 / 1 .
• Każdy ułamek 2 / y wymaga dwóch wyrazów w swoim zachłannym rozwinięciu wtedy i tylko wtedy, gdy y ≡ 1 (mod 2) ; najprostszym takim ułamkiem jest 2 / 3 .
• Ułamek 3 / y wymaga trzech wyrazów w swoim zachłannym rozwinięciu wtedy i tylko wtedy, gdy y ≡ 1 (mod 6) , wtedy − y mod x = 2 i y ( y + 2) / 3 jest nieparzyste, więc ułamek pozostały po a pojedynczy krok zachłannej ekspansji,
  $${\ Displaystyle {\ Frac {(-y) {\ bmod {x}}} {y \ lewo \ lceil {\ Frac {y }{x}}\right\rceil }}={\frac {2}{\,{\frac {y(y+2)}{3}}\,}}}$$
  jest w najprostszych słowach. Najprostszym ułamkiem 3 / y z rozwinięciem trzyczłonowym jest 3 / 7 .
• Ułamek 4 / y wymaga czterech wyrazów w swojej zachłannej ekspansji wtedy i tylko wtedy, gdy y ≡ 1 lub 17 (mod 24) , bo wtedy licznik - y mod x pozostałego ułamka wynosi 3, a mianownik to 1 (mod 6) . Najprostszym ułamkiem 4 / y z rozwinięciem czteroczłonowym jest 4 / 17 . Hipoteza Erdősa – Strausa mówi, że wszystkie ułamki 4 / y mają rozwinięcie z trzema lub mniej wyrazami, ale gdy y ≡ 1 lub 17 (mod 24) takie rozwinięcia muszą być znalezione metodami innymi niż algorytm zachłanny, przy czym przypadek 17 (mod 24) jest objęty relacją kongruencji 2 (mod 3) .

Mówiąc bardziej ogólnie, sekwencja ułamków x / y , które mają zachłanne rozwinięcia x -członowe i które mają najmniejszy możliwy mianownik y dla każdego x , to

${\ Displaystyle 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}$ (sekwencja A048860 w OEIS ).

Aproksymacja pierwiastków wielomianowych

Stratemeyer (1930) i Salzer (1947) opisują metodę znajdowania dokładnego przybliżenia pierwiastków wielomianu w oparciu o metodę zachłanności. Ich algorytm oblicza zachłanną ekspansję korzenia; na każdym etapie tego rozwinięcia zachowuje wielomian pomocniczy, którego pierwiastkiem jest pozostały ułamek do rozwinięcia. Rozważmy jako przykład zastosowania tej metody do znalezienia zachłannej ekspansji złotego podziału , jedno z dwóch rozwiązań równania wielomianowego ₀ P ( x ) = x ² − x − 1 = 0 . Algorytm Stratemeyera i Salzera wykonuje następującą sekwencję kroków:

1. ₀ Ponieważ ₀ P ( x ) < 0 dla x = 1 i ₀ P ( x ) > 0 dla wszystkich x ≥ 2 , musi istnieć pierwiastek z P ( x ) między 1 a 2. Oznacza to, że pierwszy wyraz zachłannej ekspansji złotego podziału wynosi 1 / 1 . Jeśli x ₁ jest ułamkiem pozostałym po pierwszym kroku ekspansji zachłannej, spełnia równanie ₀ P ( x ₁ + 1) = 0 , które można rozwinąć jako P ₁ ( x ₁ ) = x
   ² ₁ + x ₁ - 1 = 0 .
2. Ponieważ P ₁ ( x ) < 0 dla x = 1 / 2 , a P ₁ ( x ) > 0 dla wszystkich x > 1 , pierwiastek z P ₁ leży między 1 / 2 a 1, a pierwszy wyraz w jego zachłannym rozwinięciu (drugi wyraz w zachłannym rozwinięciu złotego podziału) to 1 / 2 . Jeśli x2 _{_} jest pozostałym ułamkiem po tym etapie zachłannego rozwinięcia, spełnia równanie P ₁ ( x ₂ + 1 / 2 ) = 0 , które można rozwinąć jako P ₂ ( x ₂ ) = 4 x
   ² ₂ + 8 x ₂ − 1 = 0 .
3. Ponieważ _wyrazem P2 ( x ) < 0 jest 1/9 dla x = 1/9 i wszystkich x P2 ( x ) > 0 _dla > 1/8 , następnym rozwinięciu . w zachłannym Jeśli x ₃ jest ułamkiem pozostałym po tym etapie zachłannej ekspansji, spełnia równanie P ₂ ( x ₃ + 1 / 9 ) = 0 , które ponownie można rozwinąć jako równanie wielomianowe o współczynnikach całkowitych, P ₃ ( x ₃ ) = 324 x
   ² ₃ + 720 x ₃ - 5 = 0 .

Kontynuowanie tego procesu zbliżania ostatecznie prowadzi do zachłannej ekspansji złotego podziału,

${\ Displaystyle \ varphi = {\ Frac {1} {1}} + {\ Frac {1} {2}} + {\ Frac { 1}{9}}+{\frac {1}{145}}+{\frac {1}{37986}}+\cdots }$ (sekwencja A117116 w OEIS ).

Inne sekwencje całkowite

Długość, minimalny mianownik i maksymalny mianownik zachłannej ekspansji dla wszystkich ułamków z małymi licznikami i mianownikami można znaleźć w On-Line Encyclopedia of Integer Sequences jako sekwencje OEIS : A050205 , OEIS : A050206 i OEIS : A050210 , odpowiednio. Ponadto zachłanne rozwinięcie dowolnej liczby niewymiernej prowadzi do nieskończonej rosnącej sekwencji liczb całkowitych, a OEIS zawiera rozwinięcia kilku dobrze znanych stałych . Niektóre dodatkowe wpisy w OEIS , chociaż nie są oznaczone jako utworzone przez zachłanny algorytm, wydają się być tego samego typu.

Powiązane rozszerzenia

Ogólnie rzecz biorąc, jeśli ktoś chce rozwinięcia ułamka egipskiego, w którym mianowniki są w jakiś sposób ograniczone, można zdefiniować zachłanny algorytm, w którym na każdym kroku wybiera się rozwinięcie

$${\ Displaystyle {\ Frac {x} {y}} = {\ Frac {1} {d}} + {\ Frac {xd-y} {yd}} ,}$$

gdzie wybrano spośród wszystkich możliwych wartości spełniających ograniczenia, tak małe, jak to możliwe, takie, że $takie$$,$ się od wszystkich wcześniej wybranych $d}$ mianowniki. Przykłady metod zdefiniowanych w ten sposób obejmują rozwinięcie Engela , w którym każdy kolejny mianownik musi być wielokrotnością poprzedniego, oraz nieparzyste rozwinięcie zachłanne , w którym wszystkie mianowniki są ograniczone do liczb nieparzystych.

Jednak ustalenie, czy algorytm tego typu zawsze może odnieść sukces w znalezieniu skończonego rozwinięcia, może być trudne. W szczególności nie wiadomo, czy nieparzyste zachłanne rozwinięcie kończy się skończonym rozwinięciem dla wszystkich ułamków, ${\ displaystyle$ których jest nieparzyste, chociaż możliwe jest znalezienie skończonych nieparzystych rozwinięć dla $x/y }$ te frakcje metodami nie-chciwymi.

Notatki

• Cahen, E. (1891), "Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en ułamki trwa", Nouvelles Annales des Mathématiques , Ser. 3, 10 : 508–514 .
•   Curtiss, DR (1922), „O problemie diofantycznym Kellogga”, American Mathematical Monthly , 29 (10): 380–387, doi : 10.2307/2299023 , JSTOR 2299023 .
•   Freitag, HT ; Phillips, GM (1999), „Algorytm Sylwestra i liczby Fibonacciego”, Zastosowania liczb Fibonacciego, tom. 8 (Rochester, NY, 1998) , Dordrecht: Kluwer Acad. Publ., s. 155–163, MR 1737669 .
• Lambert, JH (1770), Beyträge zum Gebrauche der Mathematik und deren Anwendung , Berlin: Zweyter Theil, s. 99–104 .
•   Mays, Michael (1987), „Najgorszy przypadek ekspansji Fibonacciego – Sylwestra”, Journal of Combinatorial Mathematics and Combinatorial Computing , 1 : 141–148, MR 0888838 .
•    Salzer, HE (1947), „Przybliżenie liczb jako sum odwrotności”, American Mathematical Monthly , 54 (3): 135–142, doi : 10,2307/2305906 , JSTOR 2305906 , MR 0020339 .
•    Salzer, HE (1948), „Dalsze uwagi na temat przybliżenia liczb jako sum odwrotności”, American Mathematical Monthly , 55 (6): 350–356, doi : 10.2307/2304960 , JSTOR 2304960 , MR 0025512 .
•   Sigler, Laurence E. (tłum.) (2002), Liber Abaci Fibonacciego , Springer-Verlag, ISBN 0-387-95419-8 .
• Soundararajan, K. (2005), Przybliżanie 1 od dołu przy użyciu n ułamków egipskich , arXiv : math.CA/0502247 .
• Spiess, O. (1907), „Über eine Klasse unendlicher Reihen”, Archiv der Mathematik und Physik , seria trzecia, 12 : 124–134 .
•    Stong, RE (1983), „Pseudowolne działania i chciwy algorytm”, Mathematische Annalen , 265 (4): 501–512, doi : 10.1007/BF01455950 , MR 0721884 , S2CID 120347233 .
•   Stratemeyer, G. (1930), "Stammbruchentwickelungen für die Quadratwurzel aus einer racjonalen Zahl", Mathematische Zeitschrift , 31 : 767–768, doi : 10.1007/BF01246446 , S2CID 120956180 .
•   Sylvester, JJ (1880), „O punkcie teorii ułamków wulgarnych”, American Journal of Mathematics , 3 (4): 332–335, doi : 10,2307/2369261 , JSTOR 2369261 .
• Wagon, S. (1991), Mathematica in Action , WH Freeman, s. 271–277 .