Похлепни алгоритам за египатске разломке

У математици, похлепни алгоритам за египатске разломке је похлепни алгоритам, прво описан од стране Фибоначија, за трансформисање рационалних бројева у египатске разломке. Египатски разломак је представљање несводљивог разломка као суме јединичних разломака, као на пример 5/6 = 1/2 + 1/3. Као што име назначава, ово представљање се користи још из времена старог Египта, али први објављени метод за конструисање таквих проширења је објашњен у Liber Abaci од стране Леонарда из Пизе (Фибоначи). Назива се похлепни алгоритам јер у сваком кораку алгоритам похлепно бира највећи могући јединични разломак који се може искористити у било ком представљању преосталих разломака.

Фибоначи заправо наводи више различитих метода за конструисање представљања египатских разломака. Он наводи похлепни метод као последње средство за ситуације када једноставније методе не успеју; погледати египатске разломке за детаљнији списак ових метода. Како Salzer (1948) описује, похлепни алгоритам, и његови наставци за апроксимацију ирационалних бројева, су били изнова откривени више пута од стране модерних математичара. Уско везан метод проширења који ствара ближе апроксимације при сваком кораку дозвољавајући неким јединичним разломцима у суми да буду негативни датира назад до Lambert-a(1770).

Проширење створено овом методом за број x се назива похлепно египатско проширење, Силвестерово проширење, или Фибоначи-Силвестерово проширење x-а. Ипак, израз Фибоначијево проширење се обично односи, не на овај метод, већ на представљање целих бројева као суме Фибоначијевих бројева.

Алгоритам и примери

Фибоначијев алгоритам проширује разломак x/y до представљања, тако што више пута понавља замену

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

(упрошћавањем другог израза у овој замени по потреби). На пример:

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

у овом проширењу, именилац 3 првог јединичног разломка је резултат заокруживања 15/7 до највећег следећег целог броја, и преостали разломак 2/15 је резултат упрошћавања (-15 mod 7)/(15×3) = 6/45. Именилац другог јединичног разломка, 8, је резултат заокруживања 15/2 до највећег следећег целог броја, а преостали разломак 1/120 јео оно што преостаје од 7/15 након одузимања 1/3 и 1/8.

Како сваки следећи корак проширења смањује бројилац преосталих разломака кој треба проширити, овај метод се увек поноштава са коначним проширењем; међутим, у поређењу са старим египатским проширењем или са много модернијим методама, овај метод може произвести проширења која су веома дугачка, са великим имениоцима. На пример, овај метод проширује

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

док други методи воде до много бољих решења

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

Wagon(1991) сугерише на још гори пример, 31/311. Похлепни метод води до проширења са десет израза, где последњи има преко 500 цифара у свом имениоцу; међутим, 31/311 има мого краћу не-похлепну презентацију, 1/12 + 1/63 + 1/2799 + 1/8708.

Силвестерова секвенца и најближа апроксимација

Силвестерова секвенца 2, 3, 7, 43, 1807, ... се може посматрати као генерисана од стране бесконачно похлепних проширења овог типа за број један, где при сваком кораку ми бирамо именилац $\lfloor y/x\rfloor +1$ уместо $\lceil y/x\rceil$. Смањивањем ове секвенце на k израза и формирањем одговарајућих египатских разломака, на пример (за k = 4)

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

резултује у најближу могућу лошу процену јединице за било који k- израз египатског разломка . То значи, на пример, сваки египатски разломак за број у отвореном интервалу (1805/1806,1) захтева најмање пет израза. Curtiss (1922) описује примену ових најближих-апроксимација резултата у стварању доње границе броја делилаца савршеног броја, док Stong (1983) описује примену у теорији група.

Проширења максималне дужине и услов подударности

Сваки разломак x/y захтева највише x израза у свом похлепном проширењу. Mays(1987) и Freitag и Phillips(1999) испитују услове под којим x/y води до проширења са тачно x израза; ови се могу описати у изразима услова подударности за y.

• Сваки разломак 1/y захтева један израз у свом проширењу; најпростији такав разломак је 1/1.

• Сваки разломак 2/y за непаран y > 1 захтева два израза у свом проширењу; најпростији такав разломак је 2/3.

• Разломак 3/y захтева три израза у свом проширењу ако и само ако y ≡ 1 (mod 6), тада је -y mod x = 2 и y(y+2)/3 је непар, тако да разломак који је преостао након једног корака похлепног проширења,

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

је најпростији израз. Најпростији разломак 3/y са троизразним проширењем је 3/7.

• Разломак 4/y захтева четири израза у свом проширењу ако и само ако y ≡ 1 or 17 (mod 24), јер тада је бројилац -y mod x преосталог разломка 3 а иманеилац је 1 (mod 6). Најпростији разломак 4/y са четворо-изразним проширењем је 4/17. Erdős–Straus претпоставка да сви разломци типа 4/y имају проширење са три или мање израза, али када је y ≡ 1 или 17 (mod 24) таква проширења се морају наћи методама другачијим од похлепног алгоритма.

Уопштено секвенца разломака x/y који имају x-изразна проширења и који имају најмањи могући именилац 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$.

Апроксимација корена полинома

Stratemeyer(1930) и Salzer(1947) описују метод проналажења тачне апроксимације корена полинома заснованом на похлепном алгоритму. Њихов алгоритам израчунава похлепно проширење корена; при сваком кораку у овом проширењу он одржава помоћни полином који има свој корен преостали разломак за проширење. Размотримо као пример примена ове методе да се нађе похлепно проширење златног пресека, једно од два решења полиномске једначине P₀(x) = x² - x - 1 = 0. Алгоритам Stratemeyer-а и Salzer-а се одвија по следећим корацима:

1. Пошто је P₀(x) < 0 за x = 1, и P₀(x) > 0 за свако x ≥ 2, онда мора постојати и корен P₀(x) између 1 и 2. Онда је, први израз похлепног проширења златног пресека 1/1. Ако је x₁ преостали разломак након првог корака похлепног проширења, он задовољава једначину P₀(x₁ + 1) = 0, која се може проширити као P₁(x₁) = x₁² + x₁ - 1 = 0.
2. Пошто је P₁(x) < 0 за x = 1/2, и P₁(x) > 0 за свако x > 1, корен P₁ се налази између 1/2 и 1, и први израз у његовом похлепном проширењу (други израз у похлепном проширењу златног пресека) је 1/2. Ако је x₂ преостали разломак након овог корака похлепног проширења, он задовољава једначину P₁(x₂ + 1/2) = 0, која се може проширити као P₂(x₂) = 4x₂² + 8x₂ - 1 = 0.
3. Пошто је P₂(x) < 0 за x = 1/9, и P₂(x) > 0 за свако x > 1/8, следећи израз у похлепном проширењу је 1/9. Ако је x₃ преостали разломак након овог корака похлепног проширења, он задовољава једначину P₂(x₃ + 1/9) = 0, која се поново може проширити као полиномска једначина са целобројним коефицијентима, P₃(x₃) = 324x₃² + 720x₃ - 5 = 0.

Настављајући овај поступак апроксимације на крају производи похлепно проширење за златни пресек,

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

Остале целобројне секвенце

Дужина, минимални именилац, и максимални именилац похлепног проширења за све разломке са малим бројиоцем и имениоцем, се могу наћи у On-Line Encyclopedia of Integer Sequences. Уз то, похлепно проширење било ког ирационалног броја води до бесконачно повећавајуће секвенце целих бројева.

Сродна проширења

У глобалу, ако неко жели проширење египатског разломка у коме су имениоци ограничени на неки начин, могуће је дефинисати похлепни алгоритам у коме при сваком кораку тај неко бира проширење

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

где је d изабрано, међу свим могућим вредностима задовољавајући ограничења, што мање могуће тако да xd > y и такво да се d разликује од свих осталих претходно изабраних именилаца. На пример, Engel-ово проширење се може посматрати као алгоритам овог типа у коме сваки узастопни именилац мора бити већи од претходног. Међутим, може бити тешко одредити да ли алгоритам овог типа може увек наћи коначно проширење. Посебно, непарни похлепни алгоритам разломка x/y се формира помоћу похлепног алгоритма овог типа у коме су сви имениоци ограничени на непарне бројеве; познато је да, кад год је y непарно, постоји коначно проширење египатског разломка у којем су сви имениоци непарни, али није познато да ли је непарно похлепно проширење увек коначно.