22 listopada 2011

Ulamki egipskie

Ułamki egipskie to nazwa sum dodatnich ułamków właściwych zwykłych z 1 w licznikach. Żadna inna wartość niż 1 w liczniku się nie pojawia.
Przejście na ułamki egipskie należy do trudnych zagadnień. Algorytm zachłanny zawsze działa, lecz mianowniki uzyskiwane pod koniec przekształceń są ogromne. Są dwa kryteria doboru optymalnych sum:
- jak najmniej składowych;
- suma mianowników jest najmniejsza.
Kryteria te czasem wykluczają się nawzajem. Istnieje ułamek egipski będący sumą 3 ułamków zwykłych, ale suma mianowników jest najmniejsza dla sumy 4 ułamków zwykłych.

Zwłaszcza ułamki egipskie powstałe z ułamka zwykłego postaci (2^n-1)/2^m wymagają ostrożnego podejścia. Np. 15/32 = 1/3 + 1/8 + 1/96 oraz 15/32 = 1/4 + 1/8 + 1/16 + 1/32.
Pierwsza postać ma długość (liczność składników sumy) 3, druga 4. Suma mianowników w pierwszym przykładzie to 107, w drugim 60.

Do rozkładu należy ewolucyjnie zaprząc 3 algorytmy: próba rozkładu lub rozszerzenie przez liczbę dopasowaną do dzielników mianownika, oraz algorytm zachłanny wyłączający największy ułamek postaci 1/n mieszczący się w rozkładanym. Po każdym wyłączeniu składnika należy sprawdzić wyniki tych trzech algorytmów i wybrać najlepszy.
Dla ułamków mających dzielniki najczęściej dobry jest rozkład. Jeżeli wielokrotność licznika nieco przekracza dzielnik mianownika, rozszerzanie jest bardzo opłacalne. Gdy mianownik jest liczbą pierwszą, algorytm zachłanny bywa najlepszy.

Wśród nierozwiązanych problemów jest hipoteza Erdosa: każdy ułamek 4/n można przekształcić na ułamek egipski długości 3.
Dowód według mnie można sprowadzić do rozszerzenia takiego, by rozszerzyć ułamek i skrócić przez dzielnik powstałego mianownika. Odpowiednie rozszerzenie zawsze istnieje dla liczb mniejszych od pierwotnego mianownika. Jest ich nawet więcej niż trzeba.

Wysuwam hipotezę: długość ułamka egipskiego otrzymanego z a/n nie przekracza 1+lg_2(a).
Dla 3/n nie można zmniejszyć, zatem przy 4 nie obejmuje hipotezy Erdosa. Niemniej graniczne szacowanie jest rzadko spełniane, trzeba specjalnie dobierać mianowniki, jako np. n=a*b+1.

1 komentarz:

jaNusz pisze...

Rozkład, np. 8/15 = (5+3)/(3*5) = 5/15+3/15 = 1/3 + 1/5
Rozszerzenie, np. 4/7 = (4*2)/(7*2) = (7+1)/(7*2) = 1/2 + 1/14
Zachłannie: 3/7 > 1/3, 3/7 = 9/21 = 7/21 + 2/21 = 1/3 + 2/21 = ...