Kolejne przeglądy zupełne oparte m.in. na połowieniu systemu

W Świecie Nauki czerwiec 2023 jest definicja cyfry jako konkretny symbol przypisany systemowi dziesiątkowemu. I nie można wtedy mówić o 'sumie cyfr' jako o sumie symboli. A co z systemami, które potrzebowałyby tysiące, jak nie miliony symboli graficznych na oznaczenie cyfr? Dlatego:

Cyfrą systemu pozycyjnego nazywamy nieujemną liczbę całkowitą ograniczoną z góry przez podstawę systemu.
Przy tej definicji można dodawać i odejmować cyfry jako liczby. Pozwalam też sobie przenieść terminy 'cyfra setek', 'cyfra dziesiątek', 'cyfra najmniej znacząca' tzn. 'cyfra jedności' zachowując ich znaczenie z systemu dziesiątkowego.

 

Pod koniec ostatniego posta z końca kwietnia wspomniałem, że wystarczy zakręcić się wokół podstawy będącą potęgą 2. Od niej albo ciągle zwiększać, albo zmniejszać podstawę p korzystając z jednego skoku (podwajanie systemu przy zmniejszaniu podstaw; połowienie systemu przy zmniejszaniu) wracamy do potęgi początkowej 2 z drugiej strony.

Wizualizacją wspomnianego sposobu jest chodzenie po spirali utworzonej z podstawy stożka, a w jednym miejscu przeskok na sąsiedni zwój spirali. Tym miejscem są specjalne postacie [4, 0, ?]_p albo [0, ?, ?]_p, gdzie w miejsce pytajników lądują cyfry liczby zapisane przy podstawie p (dla purystów, trzeba położyć obok  [4, 0, ?]_p także [4, 1, ?]_p albo dopuścić podstawę ułamkową - gdzie 2p jest liczbą naturalną). 

Z reguł połowienia podstawy systemów: cyfra najmniej znacząca przy połowieniu podstawy może się zmniejszyć na skutek przeniesień. Zatem ciąg cyfr jedności liczby przy ciągu połowionych podstaw p = [2^k *b, ..., 4b, 2b, b] tworzy funkcję słabo monotoniczną. Podzielność występuje wtedy, gdy cyfra jedności jest dzielnikiem podstawy.

I tu nie doceniałem różnicy naprzemiennej A = a-b+c-d+... , będącej cechą podzielności przez (p+1). Różnica ta łatwo potrafi być ujemna. Ale jeśli bierze się ją modulo podstawę systemu p, to pojawia się prosta zależność
A = q<0 => A = (p+1)-q (modulo p). 

Więcej, pojawia się możliwość oszacowania reszty bardziej oddalonej niż dla sąsiedniej podstawy systemu. Dla kolejnych podstaw druga różnica skończona A (odpowiednik różniczki dwukrotnej) jest przedziałami stała, co jest mocniejsze niż monotoniczność cyfr. Przy czym długość przedziałów jest zależna od cyfr setek oraz dziesiątek, wartość przyrostów (pierwsza różnica skończona) zależy tylko od cyfry setek. 

Pozwala to szacować wielkość A kilka podstaw dalej - zaś A=0 (modulo p) oznacza podzielność liczby przez (p-1). Nie zawsze to działa, szwankuje gdy następuje przeniesienie z cyfry dziesiątek lub setek, lecz takie zdarzenia przy dużych podstawach są stosunkowo rzadkie.

Wreszcie jeszcze jedno kryterium przeglądu zupełnego: liczbę N można zapisać jako sumę wielokrotności kwadratu i liczby złożonej, która ma dzielnik nie mniejszy niż przesunięcie wewnątrz kwadratu: 

N = a(p+k)^2 + (p+k)*b , 

co wynika z postaci przy podstawie dzielnika N = [a, b, 0]_p. Wartość k staje się dystansem od dzielnika. Narzucając ograniczenia na parametry zmniejszamy krotność przypadków podczas przeglądu zupełnego.

Prototyp rozkładu przeniesieniami

Mam liczbę w systemie siódemkowym [2, 6, 3]_7. Domyślam, się, że jest złożona, pokażę kolejny sposób, który ewentualnie moze być użyty do rozkładu liczb. Jest to prototyp dla małej wartości podstawy p=7. 

Jeśli mam iloczyn (ap+b)*(cp+d) o nieznanych a, b, c, d, to mogę przenieść w jednym z czynników 'dziesiątkę;, tu dokładniej siódemkę uzyskując zamiast cp+d = (c+1)p+(d-p) = (c+1)p - e. Co to powoduje w zapisie liczby

(ap+b)*(cp+d) = acp^2 + (bc+ad)p + bd ?

Wykorzystamy przeniesienie, które można zapisać xp = xd+xe, gdxie x jest dowolną wartością: a, b. Teraz 

(ap+b)*((c+1)p-e) = a(c+1)p^2 + (bc+b-ae)p - be . 

Różnice na pozycjach między tymi dwoma zapisami można podsumować +[a, b-ap, -pb]_p, kompletnie nie zależą one od c oraz d. 

W przykładzie 

[2+a, 6-7a+b, 3-7b]_7

zarazem 2>=ac, załóżmy a>=c, zatem a może być równe 1, 2, c równe 1, ewentualnie 0, gdyby się okazało, że podstawa p jest odpowiednio duża. Załóżmy, że a=1 oraz skorzystamy z jeszcze jednego przeniesienia by mieć pewność wartości ujemnej w cyfrze jednostek: 

[3, -1+b-1, 3-7-7b] _7 = [3, -2+b, -4-7b]_7

Sugerowana jest wartość ujemna na cyfrze 'dziesiątek' -2+b, przeniesiemy z cyfry setek zmniejszając tu równocześnie ac=1: 

[1, 5+b, -4-7b]_7 . 

W postaciach ogólnych mieliśmy w cyfrze jedności bd, -be, istnieje wspólny dzielnik będący wielokrotnością b. Jakie wartości przyjmuje cyfra jedności dla kolejnych b, szukamy podzielnych przez 3: -4, -11, -18. Różnica 3-(-18) = 3*7, co sugeruje b=3. Wstawmy siłowo: 

[1, 5+3, -4-7*3]_7 

W tym zamieszamiu przeniesieniami tracimy wartość liczby rozkładanej. Przywracamy jej postać, już po uwzględnieniu wartości a i b na cyfrach innych niż jedności, przy okazji ustawiamy c=1: 

[1, 8, 38]_7

Ponieważ cyfra jedności powinna być złożona, a kombinacja liniowa dzielników powinna dać cyfrę 'dziesiątek', kolejne przeniesienia korygują: 

[1, 8, 38] _7 = [1, 9, 31]_7 = [1, 10, 24]_7 

i rozpoznajemy: 24=4*6, 1*4+1*6=10 spełnia te warunki. Naszymi dzielnikami liczby początkowej są [1, 4]_7 = 11, [1, 6]_7 = 13, i można sprawdzić, że naszą początkową wartością jest [2, 6, 3]_7 = 11*13 = 143...

Z innych znalezionych ostatnio własności: sposób zmniejszania podstawy o 1 przez dodawania cyfry poprzedzajacej działa także dla systemu binarnego! W szczególności przy odpowiednim sumowaniu (jest symetryczne dla długości liczby, choć dopiero niedawno na to wpadłem) w cyfrze jedności odkłada się suma ustawionych bitów zapisu liczby binarnej. 

Faktoryzację przeglądem zupełnym warto zaczynać nie od dzielników najmniejszych 2, 3, ... , ale od podstaw równych największym możliwym potęgom 2, a mniejsze dzielniki uzyskamy przez połowienie podstawy systemu - mniej obliczeń i znacznie mniejsza redundancja możliwych podstaw.

Palindrom i hiperbola

Mam palindrom nad systemem niedziesiątkowym. Czy mogę przejść na inny palindrom mający tę samą resztę? 

Jest to możliwe, rozkładając na czynniki wartość stojącą jako druga najmniej znacząca. Wtedy wystarczy konwersja zmiany systemu na wielokrotność podstawy systemu, oraz naprawa uszkodzonego przekształceniem palindromu. 

W ogólności nie można tego zrobić, gdyż wartość na pozycji najmniej znaczącej jest zależna od dzielników liczby zapisanej palindromem. To znaczy, jeśli chcemy zachować resztę 1, a liczba należy do orbity 3N+2, w systemie trójkowym nie uzyskamy palindromu z resztą 1 na pozycjach skrajnych. 

Jaki jest związek palindromu z hiperbolą? Przekształcenie niezmiennicze palindromu nad systemem wyraża się prostym równaniem nieliniowym, będącym akurat równaniem hiperboli, co zaraz uzasadnię. 

W szczególności, nawiązując do szukania dzielników liczb. Niezmiennikiem wartości palindromu N = [a, b, a]_2 nad systemem binarnym jest [a+2, b-5, a+2]_2, a ogólniej N = [a+2k, b-5k, a+2k]_2 dla dowolnego k całkowitego. 

Dzielniki występują wtedy, gdy każdy współczynnik palindromu jest podzielny przez pewną wartość d: [ad, bd, ad]_2. W szczególności wspólny dzielnik nwd(bd, ad) >= d >1. Załóżmy więcej, nawet wielokrotność b = sa. Wykorzystując niezmiennik, rozwiążemy równanie b-5k = s(a+2k). Uwzględnimy jeszcze, że N jest nieparzyste, zaczniemy od a=1, do b odłożymy największą (nad systemem binarnym) wartość i dostajemy zależność:

(N-5)/2 - 5k = s(1+2k) 

w liczbach całkowitych. Sprowadza się ona do równania hiperboli 

2ks + 5k + s - n = 0 , n jest stałą n = (N-5)/2.

Punkty kratowe tej hiperboli są związane z dzielnikami liczby N. Gdyż po wstawieniu rozwiązania (k,s) mamy wartość dzielnika (1+2k) na pozycji skrajnej palindromu.

Programowanie rekursywne współbieżne, szukanie wzorca w napisie

 Jestem blisko stylu programowania, o którym już dawno myślałem. Chcę ominąć ograniczenia, które przyjmuje się za podstawy programowania rekursywnego. 

Tymi ograniczeniami są: szybkie zużycie stosu na ciała wywołań kolejnych funkcji, wielokrotne obliczane tego samego. 

Moje podejście wydaje się omijać oba ograniczenia. Zamiast stosu używam kolejki, dzięki czemu nie muszę pamiętać wcześniejszego wywołania, oraz ograniczam pętle, wskazując konkretnie, gdzie odkładać wyniki pośrednie. 

Wiążą się z tym jednak inne problemy do rozwiązania. Pierwszym z nich jest: gdzie pojawią się wyniki? Należy w ciele wywołania funkcji trzymać adres klasy, do której trafią wyniki. Ma też inne zachowania, np. pozwala zastosować funkcje wielowartościowe.

Zastosowałem ten sposób do znajdywania wzorca w napisie. Najlepsze logarytmy mają złożoność O(n+m), gdzie n jest długością napisu, a m długością wzorca. Ta złożoność u mnie zachodzi dla dokładnie jednego wzorca, kiedy nie ma tekstów zaczynających się tak samo jak wzorzec. Moją złożoność szacuję na O(n*m), zależy od napisu i wzorca. Trzeba dodatkowo zapamiętać położenie pierwszej zgodności wartości oraz położenie wyników, te dane przy wychodzeniu z funkcji (rekursywnych mojego typu) są tracone.

Wywołanie odbywa się przez zapakowanie do klasy i uruchomienie ciągu: 

0. [szukajTekstu, napis, indeksNapisu, wzorzec, indeksWzorca, skadZgodnosc, wynik]

Klasa ma jedną metodę, która porównuje ze sobą dwie wartości

napis[ indeksNapisu ] == wzorzec[ indeksWzorca ]

Jeżeli są zgodne oraz skadZgodnosc jest ustawiona na jakąś pozycję, kolejny znak tekstu jest zgodny ze wzorcem. Jeśli nie, ustawia się skadZgodnosc na pozycję indeksNapisu, oraz wywołuje dwie funkcje, przez odłożenie ciągów

1. [szukajTekstu, napis, indeksNapisu+1, wzorzec, indeksWzorca+1, skadZgodnosc, wynik]

dla kontynuacji, oraz 

2. [szukajTekstu, napis, indeksNapisu+1, wzorzec, 0, nil, wynik]

dla poszukiwania początku kolejnego wzorca w napisie.

Jeśli wartości nie są zgodne, rekursja jest zatrzymywana dla tego konkretnego przypadku, ale póki nie sprawdzony jest cały napis, należy ponownie wywoływać 2. 

Oczywiście przy wywołaniu rekursywnym należy zacząć od przypadków szczególnych, indeksNapisu maksymalny to zakończenie tego ciągu rekursji, zaś indeksWzorca maksymalny to odłożenie do wyniku ciągu

3. [wynik, ?, skadZgodnosc]

W miejsce pytajnika należy podać informację o przebiegu. Nie wiadomo, czy algorytm się zatrzyma i kiedy. Dlatego klasa wynik musi być czymś w rodzaju sprytnego wskaźnika dla wywołań.

Jedno przejście po napisie wystarczy, by wyłapać wszystkie wystąpienia wzorca. Szukając 'na' w tekście 'ananas nasz' algorytm zwrócił tablicę [1,3,7]. Ale dla tego samego wzorca i napisu 'nanas nasz' o wyniku [0,2,6] pojawił się problem, jak trzymać w pamięci skadZgodnosc. Należało go zwiększyć o 1, gdyż inaczej blokowało wynik. Przyczyna nieznana, wszystkie dane były traktowane praktycznie jako void i kompilator nie wiedział co zrobić z semaforem na nil. Ewentualnie można przyjąć liczenie pozycji od 1, zaś 0 stosować jako semafor.

Szybkie sprawdzanie podzielności przez niektóre liczby

Mnożenie liczb mających w systemie binarnym same jedynki daje pośrednio (przed użyciem przeniesień między cyframi) bardzo specyficzną strukturę - piramidę, np. 3*7 = [1 2 2 1] _2. 

Długość piramidy jest o 1 mniejsza niż długość (liczność bitów) większego z dzielników, największa wartość piramidy to liczność bitów krótszego dzielnika. Zatem mogąc utworzyć z liczby taką piramidę - wartość w nawiasie powtarza się: 

1 (2) 1, 

1 2 (3) 2 1, 

1 2 3 (4) 3 2 1, itd. 

łatwo dopasujemy dzielnik. 

 Istnieje jeszcze jedna własność, gdy w dzielniku p dokładnie jeden z bitów jest wyzerowany, np. 2^k, liczba N = p*q, to przez dodanie t = q*2^k uzyskamy piramidę o znanym rozkładzie. Korzystając wtedy z 

N+q*2^k = q*(p + 2^k) = (2^r-1) * (2^s-1) 

uzyskujemy, że dodawana wartość jest wielokrotnością dzielnika N. Zatem dopełniając N do piramidy, oraz licząc największy wspólny dzielnik gcd(t,N), uzyskamy niezwykle szybko rozkład N. 

 Uzupełnianie do piramidy odbywa się następująco: przechodzimy po bitach N wyłączając skrajne najmniej i najbardziej znaczące cyfry. Jeśli jest tam 0, wstawiamy 2, jeśli 1 zostawiamy. Uzyskana podwojona wartość binarna jest tą, która jest iloczynem 3*(2^n-1) o postaci 1 (2) 1. 

By uzyskać kolejny poziom, dodajemy po prostu wartość (2^(n-2*k)-1)*2^k dla odpowiedniego k przy długości nieparzystej podstawy piramidy. Dla długości parzystej modyfikacja jest niewielka. Zasada - w kolejnym składniku usuwamy obie skrajne jedynki i mnożymy przez 2.

I tak mając 25 = [1 1 0 0 1], aby uzyskać piramidę, należy dodać [1 2 2]*2 = 20, wspólny dzielnik gcd(25, 20) = 5 jest dzielnikiem. 

Ten sposób działa dla 7, 13, 11, 5, 31 i innych, zawodzi przy 19, która ma dwa bity wyzerowane w zapisie.

Sposób rozkładu liczb na dźdźownicę

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...