Jeśli jesteś właścicielem tej strony, możesz wyłączyć reklamę poniżej zmieniając pakiet na PRO lub VIP w panelu naszego hostingu już od 4zł!
Strony WWWSerwery VPSDomenyHostingDarmowy Hosting CBA.pl

Wersja z 2015-09-12

Grzegorz Jagodziński

Ułamki egipskie

1 2 3 4 5 6

Algorytm znajdujący rozkłady zwyczajne

Przeanalizujemy teraz, jak znaleźć wszystkie rozkłady, spełniające narzucone wcześniej warunki, a więc przede wszystkim jak znaleźć rozkłady o najmniejszej możliwej liczbie posegregowanych składników. Ponieważ wielkość ułamków ma być jedynie elementem dodatkowym, będziemy chcieli znaleźć wszystkie możliwe rozwiązania zwyczajne (o rozpatrywanych właściwościach). Algorytm ten będzie modyfikacją metody Fibonacciego, a właściwie jej rozszerzeniem.

Zauważmy, że jeśli badany ułamek da się przedstawić jako sumę dwóch składników: `p/q = 1/a + 1/b`, a do tego te składniki mają być uporządkowane według wielkości (od składnika największego, czyli o najmniejszym mianowniku), to wówczas pierwszy składnik musi być większy od połowy badanego ułamka: `1/a > 1/2*p/q`, a przy tym oczywiście musi być mniejszy od tego ułamka (jeśli `1/b` ma być liczbą dodatnią). Łącznie otrzymamy zatem dwa warunki, które możemy zapisać w postaci `p/(2*q) < 1/a < p/q`.

W świecie kartki i długopisu (w przeciwieństwie do świata informatycznego) porównywanie ułamków właściwych nie należy do czynności najprostszych, łatwiej będzie nam więc porównać ich odwrotności. Pierwszym etapem naszego postępowania będzie więc wyznaczenie wszystkich (naturalnych) wartości `a` spełniających warunek `q/p < a < (2q)/p`. Algorytm będziemy stosować dalej dla każdej z otrzymanych wartości. W przypadku wielu ułamków będzie to oczywiście zadanie bardzo żmudne, jedynie dla wytrwałych.

Jeśli szukamy jedynie rozwiązań z ułamkami o najmniejszych możliwych mianownikach, warto (z pozoru paradoksalnie) zacząć od największej możliwej wartości `a` (czyli od najmniejszego ułamka `1/a`, zupełnie przeciwnie niż w metodzie Fibonacciego). Duża wartość `a` oznacza bowiem, że `1/a` jest stosunkowo bliskie połowie badanego ułamka, a wówczas `1/b`, o ile istnieje, nie może być znacznie mniejsze (czyli `b` nie może być bardzo duże). Jeśli jednak szukamy wszystkich rozkładów zwyczajnych, wówczas kolejność sprawdzania wartości `a` nie ma znaczenia, a nawet zaczęcie od najmniejszej możliwej wartości `a` jest z pewnych powodów lepsze.

Zauważmy, że w naszym wypadku założyliśmy rozkład `p/q = 1/a + 1/b`, a zatem będziemy szukać tylko takich wartości `a`, dla których różnica `p/q - 1/a` okaże się ułamkiem egipskim (nie możemy rzecz jasna zapomnieć o skracaniu otrzymywanych w obliczeniach ułamków!). Jeśli w ogóle znajdziemy takie rozwiązania, to algorytm uznamy za zakończony. Znacznie gorzej będzie, jeśli nie znajdziemy ani jednego rozwiązania na tym etapie. Pamiętajmy wówczas o zapisaniu wszystkich obliczonych różnic, ponieważ przydadzą się nam one na kolejnym etapie.

W takim bowiem wypadku będziemy musieli założyć, że rozkład jest trójskładnikowy i ma postać `p/q = 1/a + 1/b + 1/c`, co wprowadzi nieco komplikacji. Zauważmy przede wszystkim, że gdyby wszystkie trzy ułamki były niezbyt różne od siebie, wówczas `1/a` byłby niewiele większy od `1/3*p/q`, a nie jak poprzednio od `1/2*p/q`. Aby nie zgubić jakiegoś rozwiązania, musimy więc tym razem rozszerzyć zakres wartości `a` tak, by spełniały one warunek `q/p < a < (3q)/p`. Rozszerzenie takie jest konieczne, istnieją bowiem ułamki mające „eleganckie” (a nawet jedyne możliwe) rozkłady trójskładnikowe z wartością `a` większą niż `(2q)/p` (a mniejszą niż `(3q)/p`). Przykładem niech będzie `47/60`, którego rozkład `1/3 + 1/4 + 1/5` znajdziemy dopiero po rozszerzeniu badanego zakresu wartości `a` (bez tego znajdziemy natomiast mniej ładnie wyglądające rozkłady `1/2 + 1/5 + 1/12` i `1/2 + 1/4 + 1/30`).

Przy poszukiwaniu rozwiązań o najmniejszych mianownikach powinniśmy i tym razem zacząć od największych wartości `a` (które na tym etapie będą większe niż na etapie poprzednim). Oznacza to konieczność obliczania na początku różnic `p/q - 1/a`, jakich dotąd nie liczyliśmy. Dla mniejszych wartości `a` będziemy już jednak dysponować różnicami obliczonymi wcześniej. Właśnie dlatego, jeśli szukamy wszystkich rozkładów zwyczajnych, lepiej jest zacząć od małych wartości `a` (po ponownym przebadaniu znanych już różnic bierzemy pod uwagę jeszcze kilka dodatkowych wartości `a`).

Teraz naszym zadaniem będzie znalezienie rozkładu każdej kolejno znalezionej różnicy na dwa składniki `1/b + 1/c`. Zadanie to trzeba wykonać dokładnie tak samo jak próbę znalezienia rozwiązania całościowego (dwuskładnikowego) na pierwszym etapie (czyli dla każdej wartości `a` sprawdzamy kolejno wartości `b` spełniające odpowiednio dobrany warunek, pamiętajmy, że teraz ograniczenie ma być mnożone przez `2`, a nie przez `3`, bo zakładamy dalszy rozkład różnicy na jeszcze dwa składniki).

Pamiętajmy też, że `b` musi być większe od `a`. Odrzucamy wartości `b = a` (bo ułamki w rozkładzie muszą mieć różne mianowniki). Możemy też śmiało odrzucić wartości `b` mniejsze od `a` ponieważ te same liczby wystąpią w innym miejscu w odwrotnych oznaczeniach.

Dla ułamków bardziej złożonych rozkład jest zadaniem naprawdę żmudnym, zwłaszcza, jeśli chcemy znaleźć wszystkie możliwe rozwiązania. Może się bowiem zdarzyć, że badany przez nas ułamek nie da się rozłożyć nawet do postaci `1/a + 1/b + 1/c`. Czytelników zachęca się do samodzielnego odszukania przykładu. W takim wypadku trzeba procedurę rozpoczynać od nowa, zakładając rozkład `1/a + 1/b + 1/c + 1/d`. Trzeba przy tym pamiętać, by tym razem szukać `a` w przedziale `q/p < a < (4q)/p`, `b` w przedziale `r_1 < b < 3r_1`, a `c` w przedziale `r_2 < c < 2r_2` (gdzie `r_1`, `r_2` oznaczają różnice otrzymane odpowiednio w pierwszym i drugim kroku).

Podobnie w wypadku konieczności poszukiwania dłuższych sum trzeba pamiętać o rozszerzaniu obszaru poszukiwań. Współczynnik liczbowy po prawej stronie układu nierówności powinien być zawsze równy ilości pozostałych jeszcze, nieznanych składników.

Jeśli ułamek `p/q` ma rozkład `n`-składnikowy, a pierwszym, największym składnikiem jest `1/a`, to mianownik tego ułamka spełnia warunek `q/p < a < (n q)/p`. Reguła ta obowiązuje na każdym etapie obliczeń. Zauważmy, że szukając `b` mamy już `n - 1` składników itd., i stosownie do tego ustalamy pole poszukiwań wartości `b`. Podobnie jest z każdym kolejnym mianownikiem.

Przykłady działania algorytmu

Podamy teraz kilka przykładów zastosowania opisanej wyżej metody, zaczynając od najprostszych nieskracalnych ułamków właściwych nieegipskich. Będziemy zajmować się kolejno ułamkami o coraz większych mianownikach.

Mianownik `2` występuje tylko u jednego ułamka właściwego, `1/2`. Jest to ułamek egipski, zatem nie podlega rozkładowi zwyczajnemu (o tym, że można go przedstawić, i to na nieskończenie wiele sposobów, jako sumę innych ułamków egipskich, wspominaliśmy wyżej, ale takiego działania nie uważamy za rozkład zwyczajny).

Mianownik `3` występuje w ułamkach właściwych `1/3` i `2/3`, i tylko drugi z nich nie jest egipski. Jest to najprostszy możliwy ułamek, który można poddać rozkładowi.

Zgodnie z wytycznymi zaczniemy od znalezienia wszystkich `a` spełniających warunek `q/p < a < (2q)/p`. Obliczamy `q/p = 3/2 = 1.5`, `(2q)/p = 6/2 = 3`. Istnieje tylko jedna liczba naturalna `a` spełniająca warunek `1.5 < a < 3`, jest nią `2`. Pierwszym składnikiem rozkładu będzie więc `1/2`. Obliczamy różnicę: `2/3 - 1/2 = (2*2 - 3*1)/(3*2) = (4 - 3)/6 = 1/6`. Bez skracania i dalszych działań otrzymaliśmy właśnie jedyny możliwy rozkład zwyczajny: `2/3 = 1/2 + 1/6`.

Mianownik `4` także wystąpi tylko w jednym ułamku. Dzieje się tak, ponieważ `1/4` jest ułamkiem egipskim, a `2/4` jest ułamkiem skracalnym (i jak się okazuje po skróceniu, także egipskim). Pozostaje więc jedynie znaleźć rozkład ułamka `3/4`.

Obliczamy odwrotność `4/3 ~~ 1.33` oraz jej dwukrotność `8/3 ~~ 2.67`; jedyną liczbą naturalną między tymi wartościami jest `2`, czyli `1/a = 1/2`. Obliczamy różnicę `3/4 - 1/2 = 1/4`. Zatem jedynym rozkładem zwyczajnym jest `3/4 = 1/2 + 1/4` (rozkład ten powinniśmy znaleźć także metodą „zdroworozsądkową”).

Mianownik `5` spotkamy już w trzech ułamkach, które można poddać rozkładowi zwyczajnemu. Wyniki rozkładu zbierzemy w tabeli poniżej, tu omówimy tylko najciekawszy przypadek `4/5`.

Odwrotność naszego ułamka to `5/4 = 1.25`, jej dwukrotność to `2.5`, jedyną wartością `a` jest zatem `2`. Obliczamy różnicę: `4/5 - 1/2 = (4*2 - 5*1)/(5*2) = 3/10`. Otrzymaliśmy ułamek nieegipski, co oznacza, że badany ułamek nie ma rozkładu dwuskładnikowego.

Skoro rozkład jest (co najmniej) trójskładnikowy, musimy zbadać nowy warunek `q/p < a < (3q)/p`. Obliczamy więc, że `1.25 < a < 3.75`, a to sprawia, że musimy także rozważyć `a = 3` czyli `1/a = 1/3`. Jest to przypadek nowy, obliczamy więc różnicę: `4/5 - 1/3 = (4*3 - 1*5)/(5*3) = (12 - 5)/15 = 7/15`. Mamy więc do zbadania dwa (niedokończone) rozkłady, `4/5 = 1/3 + 7/15` oraz `4/5 = 1/2 + 3/10`.

Rozkładamy najpierw `7/15` (`a = 3`), zakładając, że rozkład jest dwuskładnikowy. Obliczamy `15/7 ~~ 2.14` oraz `30/7 ~~ 4.29`, co daje dwie wartości `b`: `3` i `4`. Wartość `3` odrzucamy, bo jest równa `a`. Obliczamy różnicę:

Jak widać, rozkład nie spełnia założenia (nie otrzymaliśmy ułamka egipskiego). Próbujemy więc teraz rozłożyć `3/10` (`a = 2`). W tym celu obliczamy `10/3 ~~ 3.33` oraz `20/3 ~~ 6.67`, musimy zbadać zatem trzy wartości `b`: `4`, `5` i `6`. Obliczamy różnice:

Tym razem aż dwa rozwiązania pasują do założonego schematu. Zgodnie z przyjętymi założeniami, które ma spełniać rozkład zwyczajny, uznajemy oba te rozwiązania (i nie szukamy żadnych innych). Mamy więc `4/5 = 1/2 + 1/5 + 1/10` oraz `4/5 = 1/2 + 1/4 + 1/20`. Tylko ten drugi rozkład znajdziemy metodą Fibonacciego.

Mianownik `6` wystąpi w tylko jednym rozkładalnym ułamku, `5/6`. Wszystkie inne ułamki o tym mianowniku są egipskie lub skracalne.

Obliczmy ograniczenia dla `a` w rozkładzie dwuskładnikowym: `6/5 = 1.2`, `12/5 = 2.4`, skąd jedyna wartość `a = 2`. Łatwo ustalimy stąd jedyny rozkład zwyczajny: `5/6 = 1/2 + 1/3`.

Mianownik `7` występuje w pięciu ułamkach rozkładalnych (jakie to ułamki?). Ciekawą rzeczą jest to, że znalezienie rozkładu `2/7 = 1/4 + 1/28` pozwala automatycznie znaleźć rozkład ułamka `4/7`. Wystarczy bowiem podwoić oba składniki, dzieląc przez dwa ich mianowniki: `4/7 = 1/2 + 1/14`. Czytelnikowi pozostawiamy do sprawdzenia, czy są to jedyne rozkłady zwyczajne tych ułamków.

Spośród rozkładalnych ułamków o mianowniku `7` najciekawszym jest `3/7`, bo ma aż sześć różnych zwyczajnych rozkładów trójskładnikowych. Poniżej umieszczono tabele pokazujące szczegółowo sposób rozkładu tego i innych ułamków; opis poszczególnych działań jest chyba teraz zbyteczny.

* * *

Zbadajmy jeszcze kilka wybranych ułamków o wyższych mianownikach. Jeśli ułamek `41/42` ma rozkład dwuskładnikowy, to `42/41 < a < 84/41`, co oznacza około `1.02 < a < 2.05`, zatem `a` może mieć tylko jedną wartość `a = 2`. Odejmowanie `41/42 - 1/2` daje wynik `10/21`, zatem rozkładu dwuskładnikowego nie ma.

Badając ewentualne rozkłady trójskładnikowe musimy założyć `42/41 < a < 126/41`, czyli około `1.02 < a < 3.07`, skąd wynikają dwie wartości `a`: `2` i `3`. Liczymy różnicę `41/42 - 1/3 = 9/14`. Jeśli `41/42` ma mieć rozkład trójskładnikowy z pierwszym składnikiem `1/3`, to wówczas `9/14` musi mieć rozkład dwuskładnikowy, czyli `b` musi spełniać warunek `14/9 < b < 28/9` i dodatkowo `b > a` czyli `b > 3`. Z tej nierówności oraz z poprzedniej przybliżonej `1.56 < b < 3` wnioskujemy, że nie ma (naturalnej) wartości spełniającej podane warunki, zatem pierwszym składnikiem rozkładu trójskładnikowego (o ile taki istnieje) nie może być `1/3`.

Badamy więc jedynie przypadek `a = 2`. Jak już wiemy, `41/42 - 1/2 = 10/21`, zatem `21/10 < b < 42/10` (i `b > 2`, co tym razem nie ma już znaczenia). Wynikają stąd dwie możliwe wartości `b`: `3` i `4`. Liczymy `10/21 - 1/4 = 19/84` oraz `10/21 - 1/3 = 1/7`. Mamy więc dokładnie jeden rozkład trójskładnikowy badanego ułamka: `41/42 = 1/2 + 1/3 + 1/7`.

Zbadajmy teraz ułamek `37/60`. Dla ewentualnego rozkładu dwuskładnikowego mamy warunek `60/37 < a < 120/37`, co daje mniej więcej `1.62 < a < 3.24`. Badamy więc dwie wartości: `a = 3` i `a = 2`. Obliczamy `37/60 - 1/3 = 17/60` oraz `37/60 - 1/2 = 7/60`, z czego wnioskujemy, że rozkład dwuskładnikowy badanego ułamka nie istnieje.

Poszukując rozkładów trójskładnikowych rozszerzamy obszar poszukiwań mianownika pierwszego ułamka do `1.62 < a < 4.86`, z czego wynika nowa wartość `a = 4`. Obliczamy `37/60 - 1/4 = 11/30`. Poszukiwania `b` będziemy więc prowadzić, próbując rozłożyć na dwa składniki ułamki `11/30`, `17/60`, `7/60` (odpowiednio dla `a` równego `4`, `3` i `2`).

Zaczynamy od pierwszego z nich (dla `a = 4`), i tworzymy warunki `30/11 < b < 60/11` oraz `b > 4`, z czego łącznie wynika `4 < b < 5.45`, czyli jedyna wartość `b = 5`. Obliczamy `11/30 - 1/5 = 1/6`, co oznacza, że znaleźliśmy (bardzo elegancki) rozkład badanego ułamka na trzy składniki: `37/60 = 1/4 + 1/5 + 1/6`. Zauważmy, że do znalezienia tego rozwiązania konieczne było rozszerzenie obszaru poszukiwań `a`.

Zbadajmy drugą różnicę `17/60` (dla `a = 3`). Warunki to `60/17 < b < 120/17` i `b > 3`, czyli około `3.53 < b < 7.06`. Obliczamy kolejno `17/60 - 1/7 = 59/420`, `17/60 - 1/6 = 7/60`, `17/60 - 1/5 = 1/12` oraz `17/60 - 1/4 = 1/30`. Znaleźliśmy tym sposobem dwa nowe rozkłady badanego ułamka: `37/60 = 1/3 + 1/5 + 1/12` oraz `37/60 = 1/3 + 1/4 + 1/30`.

Do zbadania pozostała różnica `7/60` (dla `a = 2`), z której wynikają warunki `60/7 < b < 120/7` i `b > 2`, co daje `8.57 < b < 17.14` i dość sporo wartości `b` do przeanalizowania. Liczymy kolejno `7/60 - 1/17 = 59/1020`, `7/60 - 1/16 = 13/240`, `7/60 - 1/15 = 1/20`, `7/60 - 1/14 = 19/420`, `7/60 - 1/13 = 31/780`, `7/60 - 1/12 = 1/30`, `7/60 - 1/11 = 17/660`, `7/60 - 1/10 = 1/60`, `7/60 - 1/9 = 1/180`. Do listy rozkładów badanego ułamka dopisujemy `37/60 = 1/2 + 1/15 + 1/20`, `37/60 = 1/2 + 1/12 + 1/30`, `37/60 = 1/2 + 1/10 + 1/60` oraz `37/60 = 1/2 + 1/9 + 1/180`. Łącznie otrzymaliśmy więc siedem różnych rozkładów zwyczajnych ułamka `37/60`.

Na koniec zauważmy jeszcze, że założenie, że rozkład zwyczajny ma składać się z najmniejszej możliwej liczby składników eliminuje czasem ciekawe i eleganckie sumy, które w rozumieniu przyjętej definicji rozkładami zwyczajnymi nie są. Na przykład ułamek `19/20` ma jedyny rozkład zwyczajny `1/2 + 1/4 + 1/5` o trzech składnikach (można się o tym przekonać samemu, używając opisanego tu algorytmu). Okazuje się jednak, że można go rozłożyć także do bardzo eleganckiej sumy czterech składników: `1/3 + 1/4 + 1/5 + 1/6`. Rozkład ten nie jest jednak rozkładem zwyczajnym.