Tym razem zamiast opisu kolejnego sposobu rozkładu liczb na czynniki, zapresentuję sposób, jak do niego doszłem. Mój zapis jest okropny, przypomina kod w LISPie opisany w nonsensopedii. Zaś złożoność i sposób przechodzenia do nowej iteracji nieodłącznie kojarzy mi się z dźdźownicą. Ma takie same fazy o znikomej złożoności.
Sposób należy do grupy prezentacji liczb, w którym każda cyfra jest zapisana w innym systemie liczbowym, czyli
\sum _{i} \prod _{0<k<i} a_i p_k
gdzie a_i są cyframi, a p_k iloczynami kolejnych podstaw. Odpowiednikiem w systemie dziesiętnym p_k są: 10, 100, 1000, ... Dalej p_k będzie oznaczać największy przyrost podstawy p_k = (i-1)/(i-2), bo reszta jest wyłączana przed nawias.
Jeśli mamy liczbę postaci N = A*p+a, to jest ona równa A*(p+2) + (a-2A), w ten sposób będę sprawdzać reszty z dzielenia. Warto zatem, by A było podzielne przez (p+2), by jak najłagodniej przekształcić a-2A w liczbę dodatnią nie większą niż p+2. W budowie A wyłączamy zatem p+2 do ostatniej cyfry w zapisie, by mieć mniej kłopotu z przenosinami. Niestety, okazuje się, że składnik z (p+2) występuje wewnątrz A i zarazem pojawia się drugi przy przekształceniu. Aby któryś opuścić, należy pomnożyć przez taki pozostałe cyfry liczby A. To są stosunkowo spore wartości, które po przenoszeniu na sąsiednią, bardziej odpowiadajacą im pozycję będą musiały być dzielone przez wartość bliską tej, przez którą mnożymy.
I można zapobiec temu wielokrotnemu mnożeniu i dzieleniu. Mamy przecież tożsamość b : (p+2) = (p+4)-2 = (p+6)-4, itd, dzięki czemu każdą kolejną cyfrę zapisujemy jako sumę wielokrotności p_k poprzedzającego cyfrę i jakiejś reszty. To jest rozwinięcie zapisu przypominające wygięcie pierścieni dżdżownicy.
Stosując teraz rozdzielność mnożenia względem dodawania, łączymy elementy o tej samej wartości p_k z sąsiednich cyfr, co wygładza obliczenia i powstaje prosta postać liczby, rozpisana minimalną licznością symboli.Mamy sumę trzech wartości, pochodzących z A, -2A oraz przekształcenia b. Wymaga jeszcze dopasowania do ograniczeń na cyfry, by były nieujemne nie większe niż p_k, przenosinami, których jest do kilku sztuk. Obawiam się, że złożoność tych przekształceń dąży asymptotycznie do stałej.
Inicjacja liczby, reszta z dzielenia przez 3 to cyfra najmniej znacząca, następna jest resztą z dzielenia części całkowitej ilorazu przez 5, itd rekursja przez kolejne liczby nieparzyste aż liczba zmaleje poniżej p_k.
Podczas iteracji wartości podstaw (p+k) przechodzą na (p+k+2), i to stosunkowo niskim kosztem przeniesień. Na kadej cyfrze mamy delikatne tłumienie, co jest najlepiej widoczne na cyfrze najbardziej znaczącej.
Nie zapisuję przykładu, bo wyglądałby tak 2+3*(4+5*(...)), co przechodzi w 3+5*(2+7*(...)).
I patrząc na odwłok tej pełznącej matematycznej dżdżownicy widać zmiany reszt z dzielenia przez kolejne liczby nieparzyste...
Brak komentarzy:
Prześlij komentarz