Rozkład z użyciem palindromów

 Przy białym tle liczne możliwe literówki. Należy zmienić sposób pisania - nie jestem w stanie wychwycić błedów. 

Zatem matematyka w wersji gry RPG. 

Dostajesz zadanie: sprawdź, czy liczba nieparzysta N jest złożona, pierwsza. Możesz skorzystać z usług NPC, którty jednak ma swoje widzimisię - chce w tablicy umieszczać tylko i wyłacznie palindromy. Zadanie niewykonalne? No dobra, obok palindromu pozwoli umieścić jeszcze jedną wartość, wmawiasz mu, że palindromy wymagają tego dodatkowego argumentu, by znać ich wartość liczbową, bo są 'nad systemem' o podstawie p. Przyjmie to p, choć to duze ustępstwo z jego strony. 

Pierwszy palindrom wpakuj nad systemem binarnym, czyli po jedynce na skraje, zaś do środka połowę z N zmniejszoną o 4+1, czyli pięć. 

 

Teraz proponuję następującą procedurę: bierz palindrom z listy, a przymierzaj się do odłożenia dwu. I to tylko wtedy, gdy środek będzie nieujemy. 

Pierwszy z palindromów powstaje po podwojeniu argumentu p - podstawy systemu. Wyraz najmniej znaczący albo zostanie bez zmian, albo zwiększy się o p, Drugi skrajny podobnie wzrośnie kosztem wyrazu w środku. Palindrom się zachowa.

Z drugim palindromem jest więcej roboty. Zwiększ podstawę p o 1. Najpierw znajdź resztę z dzielenia przez p+1. Suma naprzemienna wyrazów ci pomoże. Postaraj się, by ta reszta c była jak najmniejsza nieujemna, dzieleniem. Teraz masz dwie możliwości, albo odciągniesz od N iloczyn c*(1+p*p) dla wyrazów skrajnych, wtedy środek jest na pewno podzielny przez p+1, i ładuj część całkowitą ilorazu jako środek palindromu.
Drugie podejście, gdy nie chce ci się dzielić tak dużych wartości, jakie mogą się pojawić. Rozbij palindrom na dwa wielomiany. W pierwszy wpakuj z pomocą przeniesień wartości c, 2c, 2c; zaś drugi ma być wielokrotnością p. Nie uzyskasz dokładnej wartości, coś zostanie, jakaś róznica od wyrazu skrajnego z 2c. Pierwszy palindrom podczas konwersji na system o podstawie p+1 przejdzie gładko w palindrom 'c 0 c', zaś z drugiego wielomianu wielokrotność p przekształć w wielokrotność p+1. I tu ta różnica załata powstałą lukę, że utworzą się iloczyn p+1 oraz wartości całkowitej - dodatniej lub ujemnej na wyraz środkowy. 

Gdy środek jest nieujemny, proś o odłożenie do tablicy NPCa. gdy jest ujemny, odrzuć. Gdy wyrazy skrajne się wyzerują, aktualna podstawa p jest dzielnikiem N, co zapamietaj. A kiedy opróżnisz całkowicie tablicę palindromów nie znajdując dzielników, liczba N okaże się pierwsza.

Środki ujemne zaczynają pojawiać się przy podstawach, kiedy liczba może być zapisana jako trójcyfrowa. Wyrazy ujemne przy podwajaniu podstawy jeszcze maleją. Możliwe wzrosty wyrazów skrajnych są przy przechodzeniu na podstawy nieparzyste, przy odpowiednio dużej podstawie p. Kojarzysz, reszty ze wzrostem podstawy utworzą funkcję piłokształtną przedziałami malejącą, zaś długość przedziałów też rośnie z p

Mnożenie Karatsuby i niektóre jego wariacje

W Wikipedii podane jest podejście rekursywne do mnożenia zaproponowane przez Anatolija Karatsubę w postaci dodawania. W pozycji Modern Computer Arithmetic Brenta i Zimmermanna podana jest wersja z odejmowaniem. Jest ona lepsza nie tylko dlatego, że 'unika' bardzo specyficznego błędu przeniesienia przy dodawaniu dużych liczb, nie mieszczących się w rejestrach procesora. Wersja ta ma dodatkowe własności, upraszczające rachunki, co zamierzam pokazać. 

Pozwalam tu sobie na jeszcze inne spojrzenie na to mnożenie. Pierwotnie był podział na dwie części mniej więcej równe, oraz rekursja, gdy wartości były wciąż wielkie. Podstawowym wzorem (dla odejmowania) jest: 

(a*p-b) * (c*p-d) = (ac)*p^2 - (adp+bcp) + (bd) ,

którego składnik -(ad+bc)*p wyraża się jako suma cyfr sąsiednich (ac)+(bd). Przy p=1 mamy wzór dla modyfikacji wartości przy różnych indeksach pozycji cyfr w liczbie. 

Patrząc na to jak na cyfry systemu o podstawie p fragment ten jest współczynnikiem 'cyfry dziesiątek' mnożenia pisemnego.

Przy moim spojrzeniu stosuję podział na n części, których iloczyny mieszczą się w słowie maszynowym. Wtedy rekursja znika. 

W pozycji Brenta, Zimmermanna wprowadza się moduł dla iloczynu różnicy cyfr (a-b)*(c-d). Według mnie znak ten trzeba zachować od początku, licząc na wartosciach ze znakiem signed. Zamiast tego istotna jest kolejność w różnicy - ta nie może ulegać zmianie, np. zawsze odejmując cyfrę na pozycji mniej znaczącej od bardziej znaczącej. 

Przechodzę do wizualizacji mnożenia w systemie o podstawie p. Każdy czynnik A, B ma co najwyżej n niezerowych indeksowanych pozycją wartości, pozostałe są zerami. Dołączam tu także indeksy ujemne.

Iloczyn to wielomian W mający 2n-1 pozycji. Wyznaczam iloczyny cząstkowe A[i]*B[i]. Na poszczególne pozycje wyniku W[k] wpisuję sumę n kolejnych iloczynów A[k-n+1]*B[k-n+1] + ... + A[k]*B[k]. W praktyce większość z tych składników jest zerami, np. na pozycję 0 dostaje się tylko A[0]*B[0],  bo pozostałe to zera o indeksach ujemnych. Sumy te przesuwają się o jednostkę, przez co ich obliczanie praktycznie początkowo narasta o A[i+1]*B[i+1], a po osiągnięciu sumy wszystkich maleje o A[k-n]*B[k-n]. 

Teraz wyznaczam róznice cyfr w obrębie czynników A[j]-A[i], B[j]-B[i], dla wszelkich j>i, które modyfikują wyznaczone wartości wielomianu.
Te różnice też mnożę na wszystkie możliwe sposoby, odejmując wartość na pozycji k=i+j. Ponieważ wartości były ze znakiem, czasem należy je podwójnie odjąć, czyli dodać. 

Ostatnia faza: współczynniki wielomianu nie spełniełniają warunku, by były nieujemne ograniczone z góry przez p. Należy użyć przeniesień jak w drugiej fazie mnożenia pisemnego. 

Dlaczego wersja z odejmowaniem jest lepsza niż z dodawaniem? Wyznaczając kombinację ad+bc podczas dodawania w wielomianie W składniki z takimi samymi indeksami są ujemne dla wyrugowania kombinacji, zaś czasem występują dodatnie, co powoduje mocną szatkownicę znaków, Przy odejmowaniu składniki z takim samym indeksem są zawsze dodatnie i można było użyć wspomnianych przesunięć na jednokrotne obliczanie sum na pozycjach k.

Sposób można takze odwrócić szukajac rozkładu, po zgadnięciu cyfr wyniku sprawdzamy występujące zależności między cyframi.
Przykład: 7387. Z mnożenia Karatsuby w systemie dziesiętnym na najmniej znaczącej pozycji mamy 3*9 = 27. Na pozycji dziesiątek mamy 8-2 = 6.
Wiemy, że na pozycji dziesiątek uzyskamy 27+xy - (9x+3y) przystajace do 7-6 = 1, ten warunek spelnia 8*8 = 64, bo 64+27 = 91.
Suma na pozycji dziesiątek tak wyznaczonych wartości to
8*8+3*9 - (8*9+8*3) = 64+27-(72+24) = 91-96 = -5
Sprawdzamy dla cyfr: 8-9=-1, 8-3=5, (8-9)*(8-3)=-1*5 = -5
Wynik mnożenia 83*89 = 7387

Skoki po liczbach gładkich

 Liczby p-gładkie to takie liczby złożone, których wszystkie dzielniki nie są większe od wartości p.

Tak liczbami 3-gładkimi są wszystkie potęgi 2, 3, 6, ... Te wszyystkie, których jedynymi dzielnikami są 2 oraz 3. 

Dopasowałem wzór, dzięki któremu mogę przeskakiwać między podobnymi do siebie liczbami gładkimi (co tu oznacza, że różnią się zaledwie paroma dzielnikami, pozostałe są takie same).

Wzór jest niezmiennikiem wartości będącej różnicą:
a*(c+d) - b*d = a*c - (b-a)*d . 

Dodaję do składników jakąś liczbę całkowitą dobraną tak, by któryś z dzielników przekształcił się na inny. Najciekawszy efekt występuje wtedy, gdy liczby są p-gładkie dla p osiąga wartość pierwiastka czwartego stopnia z wartości różnicy we wzorze lub nieco większe. 

Liczbę rozdzielam na iloczyn dwu liczb złozonych A*B. Sprawdzam reszty z dzielenia każdej przez nowy dzielnik, który chcę wprowadzić. Wtedy podmieniam ten czynnik nowo znalezioną liczbą złożoną, co wiąże się z przesunięciem do najbliższej liczby odpowiedniej gładkości, przy okazji wyznaczajac jej odległość od wspomnianej stałej wartości. 

Np. utworzyłem sobie ciąg takich liczb gładkich: 

(3*5*5*17)*(19*371), a ponieważ 19*371 = 7049 = 7061-12, oraz 7061 = 23*307, odległa o 12*(3*5*5*17) = 12*1275,

(3*5*5*17)*(23*307), teraz chcę mieć dzielnik 31 zamiast 23, dodaję 10*1275 = 12750 otrzymując 

(3*5*5*17)*(31*227), dla dzielnika 37 od tego odejmę 30*1275 = 38250 i mam 

(3*5*5*17)*(37*191), 

na razie reszty przeliczam dla drugiego z czynników (19*371), widać, że schodzą coraz blizej pełnego kwadratu: 

(3*5*5*17)*(73*97),
(3*5*5*17)*(79*89),
(3*5*5*17)*(5*17*83),
(3*5*5*17)*(79*89),

Od tego momentu trzymając się tego czynnika następuje powtarzanie się wartości, bo wykres funkcji f(x,y) xy=const jako hiperbola jest symetryczny względem prostej y=x. 

Nie jestem ograniczony do drugiego czynnika, oto kolejne liczby gładkie, które wyznaczałem przesuwając o parzystą wartość - chciałem mieć nieparzyste liczby p-gładkie: 

(13*101)*(3*23*103)
(13*101)*(67*107)
(13*101)*(3*3*7*113)
(11*127)*(3*3*7*113)

Odległości między tak wyznaczanymi liczbami gładkimi są ogromne, sięgają milionów przy wartości rzędu 10 milionów, gdyż liczby p-gładkie nie są zbyt częste. Jednak zdumiewa mnie łatwość, z jaką licząc tyko resztę z dzielenia przez fragment liczby znajduję dystans do najbliższej wielokrotnosci kolejnej chcianej przeze mnie wartości. 

Mogę też pokusić się o mocniejsze wygładzanie. 

Liczby gładkie służą do wyznaczania wzorców dla rozkładu sitem kwadratowym. Im więcej znanych liczb gładkich, tym więcej związków między nimi, i łatwiej znależć takie same reszty modulo N, co prowadzi do wykrycia dzielnika liczby N. Jednak wg mnie liczby p-gładkie z większym p są bardziej interesujace.
Jeśli chcieć rozkładu, gdy w uzyskanej różnicy odległość od wartości jest wielokrotnością jakiegoś dzielnika liczby gładkiej, to jest to zarazem dzielnik stałej wartości:
N = ABq - rq = (AB-r)q.

System Fibonacciego i jego związki z symbolami Newtona

 Symbole Newtona ułożone w trójkącie Pascala uzyskuje się wstawiając 1 na skrajne pozycje, zaś pozostałe są sumą dwu poziom wcześniej. Ta sama formuła niejawnie występuje przy rozpisywaniu liczby w systemie Fibonacciego. 

Klasycznie wybieramy jakąś maksymalnie dużą liczbę Fibonacciego i odejmujemy zamieniając 0 na 1 na pozycji tej liczby. Kiedyś tutaj opisałem przekształcenia, które 'płaszczą' liczbę wciśniętą na pozycję cyfry systemu Fibonacciego. Przypomnę te przekształcenia dla fragmentów [] zapisów systemu Fibonacciego: 

[0 0 3 0 0] na [1 0 0 0 1]
[0 0 4 0 0] na [1 0 1 0 1]

Kiedy zamiast wartości 3 lub 4 wciskamy potęgi tychże, możemy zastosować 'spłaszczanie' iteracyjnie, uzyskując w kolejnych krokach współczynniki symboli Newtona, np dla 3^2: 

[0 0 0 0 3^2 0 0 0 0] =
[0 0 3 0    0   0 3 0 0] =
[1 0 0 0    2   0 0 0 1]   druga potęga, rozdzielane współczynniki (1+1)^2

Zachowanie potęg 4 tak nie chce,  ale i tak dla 4^2 mozemy wymusić wystąpienie współczynników Newtona (1+1)^3:

[0 0 0 0 4^2 0 0 0 0] =
[0 0 4 0    4   0 4 0 0] =
[1 0 2 0    3   0 2 0 1] =
[1 0 3 0    0   0 3 0 1]     i co, nie da się?

Nie jest to jedyny związek. Niedawno odkryłem kolejny. 

Jeśli w kolejne 'cyfry' systemu Fibonacciego wciskamy kolejne wartości współczynników Nertona binom(n, k) dla kolejnych k od 0 do n, do uzyskanego wielomianu dopuścimy przeniesienia 'naprawiające', gdyż w klasycznym systemie Fibonacciego cyfry mają tylko dwie wartości: 0 oraz 1. W wyniku uzyskamy -- wartość Fibonacciego! Np. dla binom(4, k) mamy:

[0 0 0 0   1 4 6 4 1] =
[1 0 0 0   0 0 0 0 0]

Wśród zabaw z liczbami pamiętam o następującej cesze podzielności:
liczba jest podzielna przez k, gdy każda z wartości na pozycji cyfr jest całkowitą wielokrotnością k. 

Okazuje się, że skoro sąsiednie wartosci F[m]=p, F[m+1]=q w systemie Fibonacciego są względnie pierwsze, zaś liczbę N można przedstawić (na wiele sposobów) jako kombinację liniową tych dwu wartości N = xp+yq, to spoglądając na wspomnianą cechę dla wielu (zwłaszcza odpowiednio małych)  teoretycznie istnieją takie a, b całkowite, że dzielnik d|N spełnia własność,
N = adp + bdq = (ap+bq)*d
niezależnie od wyboru p, q. Przedstawienie nie jest jednoznaczne, bo każdy z dzielników ma wiele możliwości doboru a oraz b na przedstawienie siebie. 

Czasem własność ta przechodzi i na inne pary p, q, które niekoniecznie sąsiadują, ale lepiej, by były względnie pierwsze, aby mogły zaprezentować wartość dzielnika.

Ile jest liczb pierwszych bliźniaczych, czworaczych, i jak ich szukać

Skonstruujmy funkcję K(n,p) nad liczbami naturalnymi n in N, która dla kolejnych liczb przyjmuje następujące wartości zależne od parametru p będącego listą liczb pierwszych, domyślnie wszystkich nie większych od danej: 

K(n,p[]) = 1, gdy n jest pierwsza lub dzielniki n nie należą do listy liczb pierwszych p.
K(n,p[]) = \prod k, k pierwsze, k należy do listy p[]

Innymi słowy, z rozkładu kanonicznego liczby n wybieramy iloczyn po jednym z czynników listy p. Funkcja ta ma pewną własność:

- jest okresowa o okresie będącym jej maksimum równym \prod k, k pierwsze, k<=p, np. dla p=3 okres jest równy 2*3, a kolejne wartości odpowiadają ciągowi (1, 2, 3, 2, 1, 6). Można porównać z danymi podanymi na stronie kodu liczb pierwszych
liczby-pierwsze.pl
oraz z budową liczb pierwszych zwanych 'prinomial tprimes', czyli iloczynami kolejnych liczb pierwszych + 1. Andrzej Nowicki w "Podróżach po Imperium Liczb" tom 4.5.4 poświęcony liczbom pierwszym

- zmiana parametru wywołuje zmianę funkcji wtedy i tylko wtedy, gdy p jest kolejną liczbą pierwszą nie uwzględnioną w produkcie (iloczynie).
A wtedy wykonujemy następujacy proces: rozszerzamy o kolejną wartość pierwszą q. Tablicę wartości odkładamy q razy, oraz co q-tą wartość mnożymy przez q. Jest to proces liniowy w obrębie tablicy, nowy okres to iloczyn starej długości razy q. 

Do pewnych celów pozwolę sobie później na dodatkową własność - nie wszystkie kolejne liczby pierwsze mogą być użyte...  Ale na razie użyjemy wszystkich nie większych niż parametr, pisząc K(n,p).

Liczba pierwsza czworacza to czwórka (m-4,  m-2, m+2, m+4), w której wszystkie wartości są pierwsze. Liczba pierwsza bliźniacza to para (m-1, m+1), w której obie wartosci są pierwsze.
Najmniejszy czworaczek jest dla m=9: (5, 7, 11, 13), potrzebuje 9 sąsiednich wartości. Funkcja K(n,5) generuje miejsca na kolejnego czworaczka, oraz sposób lokalizowania kolejnych, jak zamierzam nieco nizej przybliżyć. 

Przeprowadźmy proces przedłużenia K(n,3) na K(n,5). Kopie tablicy
1, 2, 3, 2, 1, 6;  1, 2, 3, 2, 1, 6;  1, 2, 3, 2, 1, 6;  1, 2, 3, 2, 1, 6;  1, 2, 3, 2, 1, 6;
modyfikacja co 5-tej wartości:
1, 2, 3, 2, 5, 6,  1, 2, 3, 10, 1, 6,  1, 2, 15, 2, 1, 6,  1, 10, 3, 2, 1, 6,  5, 2, 3, 2, 1, 30;
Zmiany występują raz w każdej z części z wyjatkiem ostatniej, w której zmiana występuje dwukrotnie, w tym na pozycji z maksimum. Dodatkowo w w każdym początkowym okresie modyfikowana wartość jest na innej pozycji okresu. Dotyczy to także zwiększania przez inne liczby pierwsze mniejsze niż długość okresu, z małego twierdzenia Fermata.

Czy jest miejsce na czworaczka? Jest, w okolicy 15, i to jest kolejny czworaczek m=15: (11, 13, 17, 19). Nie ma miejsca na inne, oraz większość wartości 1 nie uległa modyfikacji! Zachowanie jedynek funkcji wskazuje, że to są miejsca na potencjalne występowanie liczb pierwszych, bliźniaczych, czworaczych. 

Pytanie, czy mamy wystarczajaco dużo liczb pierwszych, by nimi obsłużyć, czy też czworaczki będą likwidowane? 

Z szacowania liczności liczb pierwszych n/lgn dla okresu N oraz jego podwojenia 2N wynika, że
2N/lg (2N) - N/lg N = (2N lg N - N(lg 2 + lg N)) / ((lg 2 + lg N)*lg N)
Przyjmując lg jako logarytm binarny (lg 2 = 1), dostajemy
(2N lg N - N - N lg N) / ((1+ lg N)lg N) = N / lg N  (lg N - 1) /( lg N + 1) < N/ lg N -1
czyli przechodząc z N do nieskończonosci, mamy wystarczająco dużo liczb pierwszych, by obsadzić nimi jedynki... 

Zatem w kopiach okresu dla kolejnych wartości parametru p czworaczki mają szansę przeżyć, o ile nie zostaną znokautowane parametrem. Dla kolejnej liczby pierwszej 7 z teorii wystąpią miejsca na 6-1 = 5 nowych czworaczków (nie liczymy znanego), ale 7 niszczy cztery z nich. Każdy kolejny parametr niszczy jakieś 4 sztuki, może też wystąpić potęga. 

Sprawdzamy wystąpienie czworaczków: m=15 + 2*3*5*i, czyli
45 (41, 43, 47, 49) padł, bo 49=7*7, 
75 (71, 73, 77, 79) padł, bo 77=7*11,
105 (101, 103, 107, 109) przeżył!
135 (131, 133, 137, 139) padł, bo 133=7*19
165 (161, 163, 167, 169) padł, bo 161=7*23 oraz potęga 169=13*13

Ostał się jeden z czworaczków, który dla kolejnego parametru 11 ma szansę się nawet 'rozmnożyć'... To są już wartości z odległościami 2*3*5*7 = 210.

Przejście graniczne z parametrem p dążącym do nieskończoności: czworaczki przeżywają, mimo, że są rzadkie, liczb pierwszych jest wystarczająco dużo na obsadzenie miejsc, zatem jest ich nieskończenie wiele, z jednego można wskazać, gdzie mogą występować następne. 

Wniosek: liczb pierwszych bliźniaczych jest nieskończenie wiele, bo oprócz miejsca dla czworaczków, są dodatkowo obsługiwane na jedynkach przy krawędziach okresów.

Teraz hipoteza, którą spotkałem u Sierpińskiego w teorii liczb oraz na
liczbypierwsze.com/pl
Czy istnieje liczba pierwsza między n*n oraz (n+1)*(n+1)? 

Funkcja F(n,[3,5]) po usunięciu 2, zliczamy, ile jest możliwych jedynek dla aktualnego okresu 3*5 = 15:
1, 1, 3, 1, 5, 3, 1, 1, 3, 5, 1, 3, 1, 1, 15
Jest 8 jedynek oraz 7 wartości większych. Rozszerzając o kolejną liczbę pierwszą nieparzystą q, zagłada jedynek będzie dla połowy (q-1)/2, gdyż ostatnia zmiana nie niszczy maksimum. Pojawi się 8q jedynek oraz 7q innych wartości, oraz dołączając 2, statystycznie niszona będzie połowa zachowywanych jedynek modyfikowanych przez q, czyli 8q-(q-1)/2 do 7q+(q-1)/2. Różnica między tymi wartościami to q-2(q-1)/2 = 1, ocalała jedynka sugeruje istnienie liczby pierwszej. 

Odległość (n+1)*(n+1)-n*n = 2n+1. Funkcję F(n,[3,5,Q]), gdzie Q oznacza liczby pierwsze przedziału [3,q] liczymy w zakresie (q, 2q) \subset [n,2n+1), co zawiera się w odległościach między sąsiednimi kwadratami n dla różnych q. Im mniejsze n, tym mniejsze q. Ze wzrostem n powoli zwiększa się też q. I warunki początkowe: 1<3<4, 2<3,5,7,<9.

Traktuję hipotezę jako prawdziwą.
Pozostaje tylko skonsultować rozumowanie z matematykami, czy to już byłby kompletny dowód.

Po przerwie, mnożenie odwracalne

Gigantyczne kłopoty z dostępem do bloga.Przy moim ulubionym interfesie dużo rzeczy niewidocznych bądź nie działa. Ryzyko literówek, których nie jestem w stanie wykryć. 

 Mnożenie w niektórych systemach niedziesiątkowych jest łatwo odwracalne. Wystarczy korzystając od cyfr najmniej znaczących rozwiązać odpowiednie układy kongruencji. Liczba jest odwracalna, gdy w systemie mamy dla każdego iloczynu przez cyfry różne końcówki cyfr oraz cyfra najmniej znacząca nie jest pełnym kwadratem. Zatem w systemie dziesiętnym mnożenie nie jest odwracalne. Gdy podstawa jest liczbą pierwszą, mnożenie może stać się odwracalne, o ile najmniej znacząca cyfra ma rozkład na dwa różne czynniki (binarny nie spełnia tego warunku).

Na przykład, wszystkie liczby dziesiętne  zakończone na 3 lub 7 mają proste odwrócenie mnożenia w systemie piątkowym, najczęściej należy sprawdzać zaczynając od 3 = 1*3 equiv 4*2 albo 7 \equiv 1*2 \equiv 4*3.

A następnie znajdować kolejne cyfry bardziej znaczące z układu kombinacji liniowych jak z mnożenia pisemnego. Można też sprawdzać odwracając mnozenie Karatsuby, te też staje się odwracalne. 

Np liczby 

A = a[2]*5^2 +  a[1]*5 + a[0]

B = b[2]*5^2 +  b[1]*5 + b[0]

Mnożenie C = A*B polega na wypełnianiu pól: 

c[0] = a[0]*b[0]   // 1*3 lub 2*4 lub 1*2 lub 3*4

c[1] = a[1]*b[0] + a[0]*b[1] // kombinacja liniowa, jedna z wykorzystywanych kongruencji

c[2] = a[2]*b[0] + a[1]*b[1] + a[0]*b[2]  // kombinacja liniowa + wyraz już wyliczalny

c[3] = a[2]*b[1] + a[1]*b[2] + 0   // wyliczalne, bo nie a[3] = b[3] = 0 w przykładzie

c[4] = a[2]*b[2] 

A następnie dopasowujemy pożyczki między polami. Ogólnie c[k] = sum _{p+q=k}a[p]*b[q].

Drugi układ kongruencji wykorzystuje kombinacje liniowe oraz przeniesienia z pól o mniejszych indeksach. Mamy zależności między parami tych kongruencji zależne od a[0], b[0], np. (3,4) = (i,j) daje

(i, j) \equiv (i+1, j-2) mod 5

Znajomość przeniesień czyni mnożenie odwracalnym.  

Liczba 10002 w piątkowym. Podejrzewamy, że dzielniki przystają do 2 equiv 3*4 mod 5, bo 3*4 = 2*5+2, przeniesienie 1, bo 3+4 = 12. Pożyczamy tworząc postać liczby w niepoprawnym piątkowym 4 4 5 2 (wycofane zostały przeniesienia blokujące odwracanie).

Teraz sprawdzamy kongruecje kombinacji liniowych (i,j) \equiv (12 - 2)/5 = 0 mod 5. Są nimi (0,0), (1,3), (2,1), (3.4), (4,2); wybieramy tą o sumie i+j \equiv 5-1 \equiv 4 mod 5. Dzielniki dla pary (1,3) kończą się na _34 * _13. 

Następna iteracja to kombinacja liniowa z uwzględnienia wszystkich dotychczasowych przeniesień (i,j) equiv (2 + 3*3+1*4)/5 = 3 z rozwiązaniami (0,2), (1,0), (2,3), (3,1), (4,4) oraz sumie 4-3 = 1 mod 5.

Ta para uzgadnia pozostałe wartości do wyniku: 34*113 = 10002 w piątkowym, co w dziesiątkowym daje (3*5+4)*(25+5+3) = 19*33 = 627 = 5^4+2.

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