Pohlepni algoritam za egipatske razlomke

U matematici, pohlepni algoritam za egipatske razlomke je pohlepni algoritam, prvo opisan od strane Fibonačija, za transformisanje racionalnih brojeva u egipatske razlomke. Egipatski razlomak je predstavljanje nesvodljivog razlomka kao sume jediničnih razlomaka, kao na primer 5/6 = 1/2 + 1/3. Kao što ime naznačava, ovo predstavljanje se koristi još iz vremena starog Egipta, ali prvi objavljeni metod za konstruisanje takvih proširenja je objašnjen u Liber Abaci od strane Leonarda iz Pize (Fibonači). Naziva se pohlepni algoritam jer u svakom koraku algoritam pohlepno bira najveći mogući jedinični razlomak koji se može iskoristiti u bilo kom predstavljanju preostalih razlomaka.

Fibonači zapravo navodi više različitih metoda za konstruisanje predstavljanja egipatskih razlomaka. On navodi pohlepni metod kao poslednje sredstvo za situacije kada jednostavnije metode ne uspeju; pogledati egipatske razlomke za detaljniji spisak ovih metoda. Kako Salzer (1948) opisuje, pohlepni algoritam, i njegovi nastavci za aproksimaciju iracionalnih brojeva, su bili iznova otkriveni više puta od strane modernih matematičara. Usko vezan metod proširenja koji stvara bliže aproksimacije pri svakom koraku dozvoljavajući nekim jediničnim razlomcima u sumi da budu negativni datira nazad do Lambert-a(1770).

Proširenje stvoreno ovom metodom za broj x se naziva pohlepno egipatsko proširenje, Silvesterovo proširenje, ili Fibonači-Silvesterovo proširenje x-a. Ipak, izraz Fibonačijevo proširenje se obično odnosi, ne na ovaj metod, već na predstavljanje celih brojeva kao sume Fibonačijevih brojeva.

Algoritam i primeri

Fibonačijev algoritam proširuje razlomak x/y do predstavljanja, tako što više puta ponavlja zamenu

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

(uprošćavanjem drugog izraza u ovoj zameni po potrebi). Na primer:

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

u ovom proširenju, imenilac 3 prvog jediničnog razlomka je rezultat zaokruživanja 15/7 do najvećeg sledećeg celog broja, i preostali razlomak 2/15 je rezultat uprošćavanja (-15 mod 7)/(15×3) = 6/45. Imenilac drugog jediničnog razlomka, 8, je rezultat zaokruživanja 15/2 do najvećeg sledećeg celog broja, a preostali razlomak 1/120 jeo ono što preostaje od 7/15 nakon oduzimanja 1/3 i 1/8.

Kako svaki sledeći korak proširenja smanjuje brojilac preostalih razlomaka koj treba proširiti, ovaj metod se uvek ponoštava sa konačnim proširenjem; međutim, u poređenju sa starim egipatskim proširenjem ili sa mnogo modernijim metodama, ovaj metod može proizvesti proširenja koja su veoma dugačka, sa velikim imeniocima. Na primer, ovaj metod proširuje

${\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763309}}+{\frac {1}{873960180913}}+{\frac {1}{1527612795642093418846225}},$

dok drugi metodi vode do mnogo boljih rešenja

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

Wagon(1991) sugeriše na još gori primer, 31/311. Pohlepni metod vodi do proširenja sa deset izraza, gde poslednji ima preko 500 cifara u svom imeniocu; međutim, 31/311 ima mogo kraću ne-pohlepnu prezentaciju, 1/12 + 1/63 + 1/2799 + 1/8708.

Silvesterova sekvenca i najbliža aproksimacija

Silvesterova sekvenca 2, 3, 7, 43, 1807, ... se može posmatrati kao generisana od strane beskonačno pohlepnih proširenja ovog tipa za broj jedan, gde pri svakom koraku mi biramo imenilac $\lfloor y/x\rfloor +1$ umesto $\lceil y/x\rceil$. Smanjivanjem ove sekvence na k izraza i formiranjem odgovarajućih egipatskih razlomaka, na primer (za k = 4)

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

rezultuje u najbližu moguću lošu procenu jedinice za bilo koji k- izraz egipatskog razlomka . To znači, na primer, svaki egipatski razlomak za broj u otvorenom intervalu (1805/1806,1) zahteva najmanje pet izraza. Curtiss (1922) opisuje primenu ovih najbližih-aproksimacija rezultata u stvaranju donje granice broja delilaca savršenog broja, dok Stong (1983) opisuje primenu u teoriji grupa.

Proširenja maksimalne dužine i uslov podudarnosti

Svaki razlomak x/y zahteva najviše x izraza u svom pohlepnom proširenju. Mays(1987) i Freitag i Phillips(1999) ispituju uslove pod kojim x/y vodi do proširenja sa tačno x izraza; ovi se mogu opisati u izrazima uslova podudarnosti za y.

• Svaki razlomak 1/y zahteva jedan izraz u svom proširenju; najprostiji takav razlomak je 1/1.

• Svaki razlomak 2/y za neparan y > 1 zahteva dva izraza u svom proširenju; najprostiji takav razlomak je 2/3.

• Razlomak 3/y zahteva tri izraza u svom proširenju ako i samo ako y ≡ 1 (mod 6), tada je -y mod x = 2 i y(y+2)/3 je nepar, tako da razlomak koji je preostao nakon jednog koraka pohlepnog proširenja,

${\frac {(-y){\bmod {x}}}{y\lceil y/x\rceil }}={\frac {2}{y(y+2)/3}}$

je najprostiji izraz. Najprostiji razlomak 3/y sa troizraznim proširenjem je 3/7.

• Razlomak 4/y zahteva četiri izraza u svom proširenju ako i samo ako y ≡ 1 or 17 (mod 24), jer tada je brojilac -y mod x preostalog razlomka 3 a imaneilac je 1 (mod 6). Najprostiji razlomak 4/y sa četvoro-izraznim proširenjem je 4/17. Erdős–Straus pretpostavka da svi razlomci tipa 4/y imaju proširenje sa tri ili manje izraza, ali kada je y ≡ 1 ili 17 (mod 24) takva proširenja se moraju naći metodama drugačijim od pohlepnog algoritma.

Uopšteno sekvenca razlomaka x/y koji imaju x-izrazna proširenja i koji imaju najmanji mogući imenilac y za svako x je

$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$.

Aproksimacija korena polinoma

Stratemeyer(1930) i Salzer(1947) opisuju metod pronalaženja tačne aproksimacije korena polinoma zasnovanom na pohlepnom algoritmu. Njihov algoritam izračunava pohlepno proširenje korena; pri svakom koraku u ovom proširenju on održava pomoćni polinom koji ima svoj koren preostali razlomak za proširenje. Razmotrimo kao primer primena ove metode da se nađe pohlepno proširenje zlatnog preseka, jedno od dva rešenja polinomske jednačine P₀(x) = x² - x - 1 = 0. Algoritam Stratemeyer-a i Salzer-a se odvija po sledećim koracima:

1. Pošto je P₀(x) < 0 za x = 1, i P₀(x) > 0 za svako x ≥ 2, onda mora postojati i koren P₀(x) između 1 i 2. Onda je, prvi izraz pohlepnog proširenja zlatnog preseka 1/1. Ako je x₁ preostali razlomak nakon prvog koraka pohlepnog proširenja, on zadovoljava jednačinu P₀(x₁ + 1) = 0, koja se može proširiti kao P₁(x₁) = x₁² + x₁ - 1 = 0.
2. Pošto je P₁(x) < 0 za x = 1/2, i P₁(x) > 0 za svako x > 1, koren P₁ se nalazi između 1/2 i 1, i prvi izraz u njegovom pohlepnom proširenju (drugi izraz u pohlepnom proširenju zlatnog preseka) je 1/2. Ako je x₂ preostali razlomak nakon ovog koraka pohlepnog proširenja, on zadovoljava jednačinu P₁(x₂ + 1/2) = 0, koja se može proširiti kao P₂(x₂) = 4x₂² + 8x₂ - 1 = 0.
3. Pošto je P₂(x) < 0 za x = 1/9, i P₂(x) > 0 za svako x > 1/8, sledeći izraz u pohlepnom proširenju je 1/9. Ako je x₃ preostali razlomak nakon ovog koraka pohlepnog proširenja, on zadovoljava jednačinu P₂(x₃ + 1/9) = 0, koja se ponovo može proširiti kao polinomska jednačina sa celobrojnim koeficijentima, P₃(x₃) = 324x₃² + 720x₃ - 5 = 0.

Nastavljajući ovaj postupak aproksimacije na kraju proizvodi pohlepno proširenje za zlatni presek,

$\varphi ={\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{9}}+{\frac {1}{145}}+{\frac {1}{37986}}+\cdots$.

Ostale celobrojne sekvence

Dužina, minimalni imenilac, i maksimalni imenilac pohlepnog proširenja za sve razlomke sa malim brojiocem i imeniocem, se mogu naći u On-Line Encyclopedia of Integer Sequences. Uz to, pohlepno proširenje bilo kog iracionalnog broja vodi do beskonačno povećavajuće sekvence celih brojeva.

Srodna proširenja

U globalu, ako neko želi proširenje egipatskog razlomka u kome su imenioci ograničeni na neki način, moguće je definisati pohlepni algoritam u kome pri svakom koraku taj neko bira proširenje

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

gde je d izabrano, među svim mogućim vrednostima zadovoljavajući ograničenja, što manje moguće tako da xd > y i takvo da se d razlikuje od svih ostalih prethodno izabranih imenilaca. Na primer, Engel-ovo proširenje se može posmatrati kao algoritam ovog tipa u kome svaki uzastopni imenilac mora biti veći od prethodnog. Međutim, može biti teško odrediti da li algoritam ovog tipa može uvek naći konačno proširenje. Posebno, neparni pohlepni algoritam razlomka x/y se formira pomoću pohlepnog algoritma ovog tipa u kome su svi imenioci ograničeni na neparne brojeve; poznato je da, kad god je y neparno, postoji konačno proširenje egipatskog razlomka u kojem su svi imenioci neparni, ali nije poznato da li je neparno pohlepno proširenje uvek konačno.