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.

cechy podzielnosci przez 7, 17

Wśród wielu znanych cech podzielności przez 7 podanych przez M. Szurka w Opowieściach matematycznych nie ma jednej, bardzo prostej. Jest ona podobna do cechy I, lecz działa nieco inaczej.

Cecha I polegała na odcięciu dwu ostatnich cyfr liczby, oraz dodanie do niej iloczynu 4 oraz odciętej liczby dwucyfrowej. Jeśli nowo otrzymana liczba jest podzielna przez 7, to początkowa także.

Ta cecha zaczyna się podobnie, odcinam dwie ostatnie cyfry, lecz liczbę dwucyfrową dodaję do podwojonej części.

Na przykładzie 138264, oryginalnie:
1382 + 4*64 = 1638
16 + 4*38 = 168
dokończenie 168 = 24*7.
Ten sam przykład, moją cechą podzielności
2*1382 + 64 = 2828
2*28 + 28 = 84 = 12*7

Cecha działa, ponieważ 7 dzieli 98, czyli 100-2. W każdym kroku zmniejszam o wielokrotność 98.

Bardzo podobnie zachowuje się 17, które dzieli 102.
Cecha podzielności przez 17 jest identyczna, z tą różnicą, że liczbę dwucyfrową odejmuje się zamiast dodawać.
Przykład dla tej samej wartości 138264 = 8133*17+3
2*1382 - 64 = 2700
2*27 - 0 = 54 = 3*17 + 3