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

Liczby pierwsze jako palindromy

Palindrom, którego wszystkie współczynniki są podzielne przez a, sam jest izomorficzny z liczbą podzielną przez a. Tak 7 0 7 14 7 0 7 jest podzielne przez 7. 

Pojawiły się kłopoty, ale nie tyle natury obliczeniowej, bo algorytm zachłanny łatwo wyznaczy taki palindrom nieparzystej długości począwszy od wartości skrajnych (skrajne wyrazy są resztami z dzielenia). Po prostu jest takich za dużo...

Pierwsze podejście, wyrazy prócz środkowego to a oraz 0. 

Drugie podejście, wyrazy prócz środkowego to a oraz 2a.

W obu sposobach 'szaleństwo' wyrazu środkowego przy zmianie a o 2. Zmiany bywały parę rzędów wielkości większe niż a. 

Najbardziej optymalne jest rozpychanie (z głową) wyrazów od wyrazu środkowego na boki, zwiększając je o 2. Tak nad systemem binarnym pojawił się schemat ogólny [+2, -3, (-1), -3, +2], nad trójkowym [+3, -7, (-4), -7, +3]. Wyraz w nawiasie () powtarza się stosownie do długości palindromu. 

Ale nie widać, by przybliżało dzielniki. Jest jednak cecha charakterystyczna dla podstaw p większych od 2, wyrazy skrajne są powtarzajacym się ciągiem długości p^2. Zależy od dwu ostatnich cyfr zapisu w systemie o podstawie p.

Dla ratowania sytuacji sprawdziłem, czy jest zależność w przedstawianiu liczb pierwszych jako palindromów. Spodziewałem się rozkładu współczynników jak w rozkłądzie Gaussa, np. 1 2 4 2 1. Niestety, są wyjąctki, np. 3 2 0 2 3 = 71 nad binarnym.

Obwiednia wypukła jako punkt wyjścia innych algorytmów.

 Od paru dni rozmyślam nad obwiednią wypukłą, szykując się do projektowania matematyki. Podejście jest następujące. Obliczam punkty obwiedni wypukłej. Oddzielam je od innych. Generuję kolejną obwiednię wypukłą, i znów oddzielam jej punkty. Mam teraz dwa wielokąty wypukłe, jeden wewnątrz drugiego. Reszta punktów w środku, czeka na kolejną iterację.

I to moze być punkt startowy kilku wielomianów: np. triangulacji, cyklu Hamiltona, a nawet problemu komiwojażera w przypadku wagi będącej odległością euklidesową, gdyż szukanie najkrótszej trasy degeneruje się do lokalnego przeszukiwania spośród kilku punktów. Wystarczy wybrać sąsiednie bliskie sobie punkty obu obwiedni (przy komiwojażerze może być konieczny jeszcze jeden punkt z bardziej zewnętrznej obwiedni, sąsiad na powstającym cyklu Hamiltona, gdyż odcinek utworzony z dwu sąsiadujących punktów przekształcamy w wielokąt minimalizujący długość ścieżki).

Tworzenie oprogramowania, strategia szpitalna

 Napisałem własną wersję Kapi Hospital, skoro na oryginał nie mogę się zalogować. Przy okazji, niektóre zastosowane rozwiązania okazały się symulowaniem AI, w szczególności stopniowe (zależne od znajomości chorób) wyświetlanie danych. 

Zaczyna się brakiem rozpoznania, potem sugeruję lekarstwo, potem nazwę  choroby oraz poziom zniszczenia lekarstwa. Jeszcze później domniemaną (nie faktyczną) moc choroby. Finalnie pierwsza z chorób pacjenta jest rozpoznawana jeszcze na korytarzu szpitalnym. 

Mam pole morale, czyli zadowolenia pacjentów z leczenia. Wprowadziłem ograniczenie, że pacjent może być podleczony (albo nawet wyleczony z jednej choroby) zaledwie raz między nabywaniem energii przez lekarza - coś w rodzaju zakamuflowanej tury. I ten ogranicznik jako efekt uboczny powoduje 'ucieczkę' pacjenta z gabinetu na korytarz kiedy chcę mu coś ponownie aplikować.

Projekt uważam za niemal zakończony. Jest w fazie testowania - grania. I wciąga. Nawet mnie.

Widok kodu przypomina nieco programowanie obiektowo orientowane, ale to tylko przystosowanie - obiektowo nie jestem w stanie zrobić nic takiego. W końcu baza danych 146 chorób powstała w nieco ponad dwa dni na samym końcu, kiedy już niemal wszystko działało. Pozostały poprawki interfejsu i dobieranie współczynników.

Przy okazji pojawił się błąd segmentacji pamięci. Wprowadzając nowe choroby zapomniałem o stałej, w której trzymam ich liczność. Stała ta wyznacza rozmiar pamięci na trzymanie tablic wskaźników. I oczywiście podczas kompilacji pojawiły się odwołania poza zakres tablic, gdzie odkładałem wskaźniki (indeksy) na choroby lub lekarstwa. 

Następna wersja tego projektu może być typu RPG w stylu wczesnych wersji MIght & Magic czy Wizardry. Choć dalej tekstówka. 

Układ kongruencji dający wzory na dzielniki liczby

W ostatnim poście napisałem 'wzór na dzielniki'. Jest to raczej układ kongruencji, które są widoczne jako układ równań.

Postać wejściowa to palindrom [i,j,k,j,i]_p nad systemem pozycyjnym o podstawie p, który jest przedstawiony jako iloczyn dwu palindromów. W tym iloczynie wartości skrajne są znane, nieznane są tylko pozycje odpowiadające cyfrom dziesiątek liczb. 

Zatem dany jest iloczyn [a, x, a]_p * [b, y, b]_p , z niewiadomymi x, y. 

Konwertujemy palindrom na systemy o podstawach (p-1) oraz (p+1). Uzyskujemy w ten sposób nowe wielomiany, których współczynniki są blisko ze sobą związane. Niestety, przenoszenie między cyframi może się jeszcze zachować mimo próby jego uwzględnienia we współczynnikach stałych układu. Porównując teraz współczynniki (jako kombinacje liniowe i jako iloczyny) uzyskujemy wspomniany układ kongruencji. 

I to wszystko.  

Na przykładzie N = 8934053 = [15, x, 15]_{16} * [11, y, 11]_{16}

Jeden z palindromów to N = [165, 0, -7342, 0, 165]_{16}, inny N = [165, 3152, -57971, 3152, 165]_{16}. 

Mamy dodatkową stałą 4*165 = 660, oraz układ równań: 

N = [165, e, e+f, 2f, f] _{15} = [165, c, d-c, -2d, d]_{17}
e-c = 4*165 = 660  (co pochodzi z kombinacji liniowej (x,y) z (15,11))
c = 11x+15y-660
e = 11x+15y+660
d = xy -2*11x-2*15y+4*165 = g*h
f = xy+2*11x+2*15y+4*165 = (4*15-g)*(4*11-f)
g = 2*15-x
h = 2*11-y

W praktyce uzyskane współczynniki nie są zbyt miłe:
N = [165, 3812, -47525, -102674, -51337]_{15}
N = [165, 2492, -66437, 127890, -63945]_{17}

Dlatego jednak preferuję inne sposoby rozkładu... Nie jestem do końca pewien, czy potrafię rozwiązywać takie układy, czy palindrom początkowy nie ma tutaj znaczenia.

Wzór na dzielniki. przygotowanie postaci

 Już parę razy zastanawiałem się tutaj, czy istnieje wzór na dzielniki liczby. I teraz znalazłem postać, dla której istnieje układ równań, z którego można wyznaczyć dzielniki. 

W tym poście przedstawię ową specyficzną postać zapisu liczby. 

Palindromem nad postawą p nazywamy wielomian o współczynnikach całkowitych postaci 

a[n] * p^n+ ... + a[1] *p + a[0], 

w którym a[n] = a[0], a[n-1] = a[1], ... po zmianie oznaczeń (n = 2k+1, r naturalne, dla n parzystego dwa sąsiednie wyrazy w środku są równe) a[k+r]=a[k-r] , 

np. [7, 12, 18, -1, 18, 12, 7]_{16} to palindrom nad systemem szesnastkowym o długości 7 i wartości liczbowej N = 7*(16^6+1) + 12*(16^5+16) + 18*(16^4+16^2) - 1*16^3.  Palindrom tworzymy po prostu przenosząc od krajów wartości z cyfr do cyfr mniej znaczących kończąc w środku. Skaczemy od cyfr mało znaczących do dużo znaczących i na odwrót dopasowując wartości najpierw na pozycjach mniej znaczących.

Własności palindromu nad systemem p: 

- z dowolnej liczby całkowitej można uzyskać palindrom nieparzystej długości, palindrom parzystej długości udaje się wyznaczyć tylko wtedy, gdy wartość liczbowa jest podzielna przez p+1.

- skrajne współczynniki palindromu są wielokrotnościami reszty z dzielenia N przez p.

- cecha podzielności: wartość palindromu jest podzielna przez x, gdy wszystkie współczynniki palnidromu są wielokrotnościami x, np. [x, 3x, 0, 2x, 0, 2x, 0, 3x, x]_p; albo wspólny dzielnik wyraz skrajnego a[0] i p jest dzielnikiem N. 

- iloczyn palindromów jest palindromem. 

-  konwersja palindromu długości 3: [a, b, a] na sąsiedni system (p+1) lub (p-1) ma z dokładnością do znaku tylko dwa różne współczynniki [a, 2a+b, 2a+b]_{p-1} oraz [a, b-2a, 2a-b]_{p+1}. Konwersje niszczą zatem strukturę palindromu. 

- palindrom nie jest  jednoznacznie wyznaczony, niezmiennikiem palindromu długości 3 jest [a+p, b-p*p-1, a+p]_p = [a,b,a]_p . Najwięcej napotykanych palindromów jest nad systemem binarnym. np. skrajne o wyrazach dodatnich liczby nieparzystej to: pierwszy [1, (N-5)/2, 1]_2, w drugim mamy około (zależy od parzystości N) [floor(N/5), x, floor*N/5)]_2 , gdzie x ma jedną z wartości: 0, 1, 2, 3, 4 w zależności od N. Dla 8934053 mamy w ten sposób palindromy  o wyrazach dodatnich między [1, 4467024, 1]_2 oraz [1786809, 4, 1786809]_2. Ze wzrostem p palindromy są coraz rzadziej spotykane. 

Przechodzę do postaci liczby N. 

Tworzę palindrom długości 5 o takiej podstawie, by jego współczynniki były stosunkowo małe, a wyrazy skrajne były wielokrotnościami reszty z dzielenia przez p takimi, by wyraz skrajny a[0] = m*n \equiv (N%p) (mod p). Dobieram je tak, by 0<=m,n<p oraz p^2 | (N-mn). Oznacza to, że m, n są cyframi jedności dzielników liczby N zapisanymi w systemie p. 

np. N = 8934053 \equiv 5 (mod 16), oraz można tę wartość przedstawić jako palindromy 

N = [85, 85, 11773, 85, 85]_{16}

oraz 

N = [165, 0, -7342, 0, 165]_{16}

W tej drugiej postaci mamy odpowiednie wartości 165 = 15*11, zatem jest to iloczyn palindromów 

N = [15, x, 15]_{16} * [11, y, 11]_{16}

Mnożąc te palindromy uzyskujemy układ kongruencji, z których można poszukiwać zmiennych z oraz y. Ale jest to także układ wejściowy dla utworzenia układu równań, z których można wyznaczyć brakujące współczynniki dzielników... Zamierzam umieścić wkrótce...

Wymuszanie postaci dzielnika

 Alert cyberbezpieczeństwa obniżony, choć niektóre moje wyniki sugerują, że istnieje nie tylko wielomianowy algorytm rozkładu, ale nawet nieco szybszy (stosowałem bisekcję do aproksymacji wartości dzielnika). 

Zdecyfowałem się na wymuszanie specjalnej postaci któregoś z dzielników rozkładanej liczby, co prowadzi do układów równań. Oszacownie rozwiązań tych równań mocno przyspiesza lokalizację dzielników. 

Kiedy stosowałem podane już parokrotnie kryteria: suma cyfr w systemie o podstawie o 1 mniejszej jest bliska tej podstawie systemu, naprzemienna suma cyfr w systemie o podstawie o 1 większej jest blika zeru (wielokrotności podstawy), uzyskałem dobre i mocne wyniki. Najwięcej kłopotu sprawiają przeniesienia między cyframi. 

Specjalna postać dzielnika zmniejsza to "narastanie przyrostów", dzięki któremu mnożenie dużych liczb uchodzi za trudne do odrócenia. 

Jednym ze sposobów jest przedstawienie wartości jako palindrom nad systemem. Jest to wielomian o współczynnikach całkowitych, którego współczynniki od początku i od końca są równe sobie. Przedtawienie liczby nad systemem binarnym moze się odbyć na wiele sposobów, im większa podstawa, tym mniej możliwości, a po przekroczeniu pewnej wartości podstawy, pojawiają się liczne i duże wartości ujemne. Cyfra jedności palindromu jest silnie związana z resztą z dzielenia przez podstawę, zaś przekształcenia tożsamosciowe "przenoszą" spore wartości między poszczególnymi cyframi. Blokuje to zwykłe przeniesienia. Iloczyn dwu palindromów jest palindromem, zaś iloczyn palindromu przez dowolną wartość też wykazuje się powtarzalnością składników.

Aby nie być gołosłownym, wymuszając postać N = p*q = [a,b,c] * [1,f] zapisaną w trzech sąsiadujących ze sobą systemach pozycyjnych, dzielnik był w miejscu, gdzie dokładnie co trzecia postać jest ekstremum lokalnym obu wspomnianych cech podzielności. Związki miedzy współczynnikami tych trzech zapisów w systemach pozycyjnych wygenerowały proste równania nieliniowe, z których można było oszacować wartości. Szacując znak f bardzo szybko zbliżyłem się do dzielników. Nie było mowy o zbieżności, o ile nie brać pod uwagę (nieznanej przed znalezieniem rozkładu) różnicy p-q.

I tak, w nieprzyzwoicie krótkim przebiegu rozłożyłem 

1 512 264 139 457 755 655 776 587 407
= 33 084 353 498 509 * 45 709 345 341 323

I widzę kolejne możliwości skracania obliczeń... Także przez układy równań...

Sito dla rozkładu, ale już nie przeglądem zupełnym

 Stosowałem sito Eratostenesa dla podstawy systemu, dla cyfry dziesiątek. Zostały znalezione przyspieszacze obublikowane w poprzednim poście. 

A teraz przesunąłem obszar rozkładu w pobliże liczby rozkładanej, oraz zajmuję się niezmiennikiem

N = a*p+b

dla którego stosuję własności: 

- b jest dzielnikiem wtedy i tylko wtedy gdy b | a*p, drugim jest np. a+1 w systemie o podstawie p
maksymalny możliwy dzielnik to a (które zresztą maleje w trakcie obliczeń lub wtapia się z p - gdyż mamy dowolność wyboru systemu pozycyjnego).

- w każdej iteracji dla pewnej wartości rosnącej k wyliczam (a-k)*(p+k), co zwiększa b zachowując niezmiennik. Przeskakuję podstawy np bisekcją, dopóki b nie zrówna się z a. Dystans przeskakiwanych wartości jest funkcją słabo malejacą. Podejście to odrzuca liczby pierwsze za duże by być dzielnikami.
Jeśli w podanym kroku uzyskam nierówność b>a, przechodzę na sąsiedni system formułą: 

N = a*p+b = a*(p+1)+(b-a) = a*p'+b'

- jeśli interesują mnie małe liczby pierwsze, stosuję sito dla liczby złożonej a*p-K(), gdzie K() jest ciągłym przerzucaniem wartości podzielnych przez małe liczby  pierwsze na coraz większy iloczyn a*p. Wartości przesuwane są po to, by nie stosować w sicie kroku +1, ale wyznaczony przez kolejną lokalnie największą wartość b. W ten sposób badam równocześnie pierwszość przez małe, jak i przez bardzo duże liczby pierwsze. Krok sita nie jest stały! 

- jeśli w rozkładzie a*p pojawi się większa liczba pierwsza, jest ona ignorowana. Dotychczasowe doświadczenie z przebiegu sit wskazuje, że takie liczby stosunkowo szybko zaczną się przyznawać do swej pierwszości, a jako większe niż b ograniczone maksymalną wartością a, nie będą dzielnikami.  

 

Praktycznie dla liczby nieparzystej możemy nawet zacząć od liczby złożonej 2*a*a+a bliskiej N. Wtedy niejako dołączamy gratis system binarny, co dodatkowo zmniejsza krotność iteracji.Sprawdzanie pierwszości może być z dwu stron - od małych i gigantycznych wartości.

Wyjątkowo nie podaję przykładu i przebiegu - obawiam się to pokazywać osobom spoza branży.

Herystyki przyspieszające rozkład liczby w przeglądzie zupełnym

 Mimo aktualnych trudności (remont + wykluczenie) nabieram doświadczenia oglądając przebieg sita, które w jednej iteracji początkowej nie sprawdza statystycznie ułamka liczby pierwszej (liczba pierwsza pojawia się dopiero po pokonaniu dystansu do kolejnej), lecz na iterację napotykam kilka liczb pierwszych, z których część często nie jestem w stanie od razu rozpoznać (iloczyn kilku zbyt dużych liczb pierwszych nie jest odróżnialny od liczby pierwszej). To się zmienia, gdy daną liczbę pierwszą spotkam ponownie. 

Ale przebieg sita nasuwa mi przyspieszacze: np. istnieje przedział, w którym można przeskakiwać część iteracji (budowa liczby [1,b,c]_p, gdzie (p-1) jest bliskie (1+b+c) sugeruje kolejną podejrzaną o dzielnik pozycję przez przesunięcie o iloraz p/(b-1) ). W ten sposób sprawdzałem wręcz pierwszość liczb rzędu pięciu milionów, gdy największą wychwytywaną w danej iteracji była liczba rzędu 3-4 milionów (kwadrat dystansu zbliżał się do 2000). 

Teraz zmodyfikowałem wyrażenie sita, co jeszcze przyspieszyło obliczenia. Przesunąłem się na zakres nieco ponad pierwiastek kwadratowy z liczby rozkładanej

N = [a, b] _ p, a bliskie sqrt N

gdzie a*p+b = N, a maleje o 1 do połowy swej początkowej wartości, p rośnie (na ogół też o 1), b tworzy wykres piłokształtny przedziałami rosnący. Sito Eraostenesa stosuję do cyfry 'dziesiątek' a, ignorując złożoność jej dzielników (dystans będący licznikiem iteracji i tak wskaże pośrednio dzielniki). 

A teraz kolejna herurystyka, która zapowiada się interesująco. Najpierw przebieg teoretyczny: 

Bierzemy iloczyn dwu liczb nieparzystych b*d, który jest bliski liczby rozkładanej N: 

b*d - N + r = 0,  b >= d

Wartość d zapisuję we wszystkich dostępnych kolejnych systemach liczbowych o cyfrze 'dziesiątek' 1: d = [1,e]_(2*p). Sprawdzam czy  (2*p+1) dzieli r+(e-1)*b. 

Przejście na sąsiedni system: e-=2; p+=2; dla podzielności wystarczy zmodyfikować wartość o stałą 2b. Największe możliwe e to połowa (d-1)/2, gdyż z założenia b i d są nieparzyste. 

Jeśli mamy podzielność, 2*p+1 jest dzielnikiem, drugi uzyskamy w bardziej skomplikowany sposób, z sumy b oraz równomiernie rozlokowanej na pozycje wartości r+(e-1)*b. Po to nam była potrzebna podzielność!

Dlaczego to działa? 

Konwersje są niezmiennicze względem wartości liczbowych. Jeśli jeden czynnik traktujemy jako stały (b), a drugi d podlega konwersjom, mamy do czynienia z wyrażeniem [1*b, e*b] _ (2*p). Tu uwzględniana jest nieparzystość bardzo dużego b oraz fakt, że d zostało dobrane jako większe niż szukany dzielnik. Każdą liczbę można sprowadzić do postaci [1, e]_p wykorzystując wielokrotnie zwiększanie systemu o 1 oraz jego podwajanie. Nie wiemy jak to zrobić bez konkretnych wartości, dlatego potrzebujemy przeglądu. 

Liczba [1, 1]_ (2*p) jest podzielna przez 2*p+1, bo jest to inny zapis 1*(2*p)+1. Zabieramy nadmiar z pozycji jedności (tu (e-1)*b) oraz w sumie z r sprawdzamy, czy uda się to rozprowadzić na wszystkich pozycjach.  

Kiedy r nie jest ujemne, lecz dodatnie, znaleziona podzielność w przypadku testowym znalazła się tuż poza 'poprawnym' zapisem pozycyjnym liczby. Przy ujemnym podobnie. Ale i odległość między dzielnikami była spora.  

Przykład liczbowy, dla liczb pierwszych i niektórych złożonych nie znajdujemy podzielności: 

253 = 17 * 15 - 2

Zapisujemy 15 = [1, 7]_8 = [1, 5]_10 = [1, 3]_12 = [1, 1]_14 . 

Sprawdzamy kolejno odpowienie podzielności:
-2+(7-1)*17 = 100 = 9*(8+1)+1,
-2+(5-1)*17 = 100-34 = 66 = 6*(10+1)+0 dzielnik 11
-2+(3-1)*17 = 66-34 = 32 = 2*(12+1)+6
-2+(1-1)*17 = -2 = 0*(14+1)-2

Liczba złożona o dzielniku 11, drugim jest 17+66/11 = 23. 

259 = 17 * 15 + 4 = 17 * 17  - 30

Po rozpisaniu (jak wyżej) w pierwszej wersji potrzebowalibyśmy [1, 9]_6 do znalezienia dzielnika 7, gdyż dopiero 8*17+4 jest wielokrotnością 7. A to nie jest poprawna liczba. W drugiej wersji 17*17-30 podobnie [1,9]_8.