Wielomianowy algorytm faktoryzacji, jeden z wolniejszych

 W rodzinie faktoryzacji zwiazanych z rozwinięciem liczby N w szereg odkryłem sposób, który ma bardzo specyficzne wartości, i jest łatwy do wyznaczenia złożoności. 

Niech p[k] oznacza k-tą liczbę pierwszą. Współczynniki rozwinięcia w szereg są iloczynami początkowych kolejnych liczb pierwszych oraz 
2*3*5*...*p[k] <= N < 2*3*5*...*p[k]*p[k+1] .
Rozwinięcie w szereg polega na odejmowaniu kolejnych wielokrotności w[k] iloczynów początkowych liczb pierwszych, z których każdy kolejny powstaje przez mnożenie przez coraz mniej wartości, kolejne iloczyny powstają przy zmniejszaniu się k, przedostatni byłby 2*3=6, ostatni przez 2. 

Każdy taki iloczyn zabiera jak największą wartość nieujemną z N generując współczynniki w[i], i<k. Wtedy N miałoby przedstawienie:
N = 2*...*p[k]*w[k] + 2*...*p[k-1]*w[k-1] + ... + 2*3*w[2] + 2*w[1] ,
tylko - możemy zacząć od liczby pierwszej d=p[k+1], sprawdzamy, który z iloczynów 2*...*p[i] > d, oraz pozostałe łączymy w jedną wartość r zapisaną w systemie o podstawie p[k+1]. Podobnie iloczyn 2*...*p[i] zapisujemy w systemie o podstawie d=p[k+1], a pozostałe -- wystarczą tylko współczynniki w[i], ..., w[k] wyznaczane w tej kolejności. Wartości te będziemy wyliczali po drodze, każdy mnożony przez małą liczbę pierwszą p[k-j] dla j=k-i+1 malejące do 0. 

Szereg ma tę własność, że jeśli modyfikowane d będzie liczbą p[i]-gładką, to często począwszy od wyrazu i+1 uzyskamy 0 lub wielokrotność liczby pierwszej, które będzie sie propagowało w kierunku w[k]. Podzielność przez początkowe liczby pierwsze sprawdzimy np. bezpośrednio licząc największy wspólny dzielnik iloczynu 2*...*p[k] z N. 

Zatem pamiętamy: współczynniki w[k],...,w[i] rozwinięcia w szereg z przypisanymi im liczbami pierwszymi, liczby p[i] oraz r, zapisane w systemie o podstawie d, samo d.
Szukamy wartości d, dla której wartość szeregu przystaje do 0 modulo d. Wszystkie współczynniki są małymi liczbami, tylko p[i], d oraz r są większe. Aby znaleźć wartość reszty N modulo d, reszta z dzielenia przez 2*...*p[i] jest dana jawnie, zaś by uzyskać resztę z dzielenia przez 2*...*p[i]*p[i+1] mnożymy ją przez p[i+1] modulo d. Kontynujemy aż do p[k]. Wyznaczone reszty w kombinacji liniowej z w[j] liczone modulo d dają resztę N%d.
Jeśli iloczyn 2*...*p[i] = 1*d+1, na końcu iteracji przemieszczamy go do reszty r = r+w[i]*(d+1), oraz zaczynamy z wcześniejszym iloczynem
w[i+1] * (2*...*p[i] * p[i+1]) = w[i+1] * (p[i+1]*d + p[i+1])
pamiętając od teraz tę wartość. 

Przebieg iteracji: zwiększamy d+2, konwersje p[i] oraz r postaci
a*(d-2)+b = a*d+(b-2a)
z możliwym przeniesieniem a*d+b = (a-1)*d+(d+b), wyznaczamy współczynniki u[j]=2*...*p[j] modulo d dla i<j<=k, obliczamy kombinację liniową sum _{k>=j>=i} w[j]*u[j] i przyrównujemy ją do 0. wszystko na stosunkowo małych liczbach ograniczonych przez d, zatem złożoności maksymalnej obliczeń O(log n).
Wyrazów nie jest zbyt dużo. Dla RSA 200 okazało się, że wystarczy mniej niż 95 kolejnych liczb pierwszych, które powoli przemieszczają sie do r, czyli jakieś O(log log n) dla wyznaczenia wartości kombinacji liniowej. Tłumienie wartosci w r jest jak na modyfikacje wyrazów jest szybsze choć liniowe - staje się stałą wartością mniejszą od d.

Jeśli zauważymy, że musimy z d dla liczby N pierwszej dotrzeć do pierwiastka kwadratowego sqrt N, nasuwa się złozoność wykładnicza. Policzymy inaczej, kryterium stopu nie jest tutaj widoczne, powstaje, gdy suma szeregu rozbieżnego zaczynajacego się w p[i+1]^2 o wyrazie 4*d+4 staje sie większa niż N. Takich sumowań jest mniej niż N, zaś, jeśli N ma dzielniki (wszystkie większe niż p[i]), krotność iteracji jest zmniejszonym o p[i+1] rzędem najmniejszego z dzielników właściwych w grupie addytywnej, zatem O(n).
Podobnie jest w teście pierwszości AKS, gdzie w analogicznej grupie muliplikatywnej (małe twierdzenie Fermata) można czasem otrzymać rząd dzielnika równy N. Tu nawet nie docieramy to tak duzej wartości.

Łącznie szacuję złożoność na O(n * log n * log log n). Wielomianowe. 

Lecz algorytm jest jednym z wolniejszych, mimo że ma automatyczne ograniczenie stosowanych wielkości. Niewidoczne jest kryterium stopu. Propagowanie reszt powoduje, że niejako 'przy okazji' rozpoznajemy część wartości d jako złożonych, przy których kombinacja liniowa i tak nie będzie zerem choćby ze względu na dodatnie r.
Inną ciekawostką jest bardzo mało 'pamiętania', współczynniki w[] są wielkości liczb pierwszych, tylko dwie 'większe' wartości 'dwucyfrowe', z których używamy 'cyfr jedności' oraz podstawa systemu odpowiadająca dziesiątce d może osiągać wartość sqrt N -- wtedy lepiej jest stosować inny algorytm tej rodziny. Uzyska mniejszą złożoność dla tak dużych d, dokładniej już od d approx root[3] N inne algorytmy mają mniej prostszych obliczeń.  

Praktyczny zapis szeregu przy d=3:
7387= 3*[210*11] + 2*[30*7] + 1*[6*5] + 1*[2*3+0] + 1
w[] = [1, 1, 2, 3], r=1.

Problem komiwojażera z obwiedni wypukłych, szczególny przypadek

 W październiku 2022 roku napisałem tu, że korzystając z obwiedni wypukłych można wyznaczyć trasę komiwojażera (ang. Salesman problem). 

Rzecz dzieje się na płaszczyźnie, mamy n miast, należy wyznaczyć trasę między wszystkimi miastami o najmniejszym koszcie, Tutaj potrzebuję współrzędnych miast, nie tylko symetrycznej macierzy kosztów podróży. Te dodatkowe informacje są potrzebne do wyznaczenia obwiedni wypukłych.

Heurystyka wyznacza najpierw obwiednię wypukłą A, która finalnie przekształci się w trasę komiwojażera K. Następnie wyznacza z pozostałych miast obwiednię wypukłą B. Miasta z B będą przemieszczane do A i równocześnie do K jako nadzbioru A.
Drobny kłopot związany z pierwszą krawędzią, oraz posiłkując się kolejnymi miastami obwiedni, dwa z A oraz najbliższe kolejne dwa z obwiedni B siłowo wyznaczam (dodatkowo ustalone już jest miasto startowe), kończę na obwiedni na której przesuwam się o miasto według orientacji.
Cały czas korzystam z pary miast, dwa z obwiedni A oraz miast doń przyległych wyznaczonej trasy; drugie z obwiedni B. Zatem mam do czynienia z trzech do czterech miast ułożonych liniowo dla wyznaczenia kosztu podróży, by przesunąć miasto z B do A. Permutacja jest tylko między sposobami zazębiania grafów. Np. a,c in A; b,d in B, trasy: acbd, abdc, abcd, także przed/za miasto zca, cde gdzie z, e in K są sąsiadami odpowiednio a oraz c trasy K.
Kiedy zamknę cykl, obwiednie przekształcą się w cykliczny graf skierowany przechodzące trasą przez wszystkie uwzględnione miasta, myślałem, że o najmniejszej długości.
W październiku brałem do nowo generowanego w kolejnych iteracjach A miasta obwiedni B, oraz wyznaczałem nową obwiednię B z miast jeszcze nie odwiedzonych. I tu pojawia się kłopot. Ta trasa niekoniecznie jest optymalną. 

Potrafi wystąpić przypadek niezbyt intuicyjny, kiedy trasa biegnie miastami obwiedni zewnętrznej, oraz suma długości trasy jest MNIEJSZA od odległości sąsiednich miast obwiedni wewnętrznej. Oszacowałem trasę, i wydaje mi się, że w tym przypadku miasta takie nie mogą być usuwane z A podczas przechodzenia do kolejnej iteracji, nowa obwiednia A powinna składać się z miast obwiedni B oraz dodatkowo tych miast. 

Przy tej modyfikacji naprawia się przypadek, kiedy jakieś miasto z B leży daleko od miast październikowej obwiedni A, ale wystarczajaco blisko trasy K, by je połączyć w jedną trasę od miast K. 

Oczywiście, podobnie jak w pażdzierniku, kiedy zbiór nieodwiedzonych jeszcze miast staje sie pusty, wyznaczony graf cykliczny skierowany staje się bardziej optymalną trasą komiwojażera.

Labirynty, rodzaje i ich generowanie

W tym poście dla odmiany zaprezentuję kilka pseudokodów na tworzenie labiryntow. W założeniu wszystkie pola w prostokącie mają być dostępne, co najwyżej przedzielone ścianami. Zatem rozmiar tablicy na labirynt jest iloczynem dwu liczb dodatnich nieparzystych, a do każdego z pól o obu współrzędnych parzystych można dotrzeć -- indeksowanie pól od zera. Nie ma większych sal, oraz labirynt gęsto pokrywa dostępny obszar.

Klasycznie podaje się labirynt generowany za pomocą stosu -- jako przykład zastosowania stosu. Taki labirynt jest drzewem. I to jest najczęściej spotykana przeze mnie implementacja w wielu źródłach.
W takim labiryncie trudno o sekretne przejścia czy cykle. Trzeba je specjalnie tworzyć. 

Labirynt oparty na liście dostępnych pól ze ścianami już podczas generowania może wygenerować ściany mogące być sekretnymi przejsciami, a nawet cykle - korytarze po których obchodzimy w kółko jakiś filar. Listę inicjujemy tylko częścią pól -- tylko tam gdzie są ściany do wyburzenia, a przy odwiedzaniu usuwamy pole z listy. Ten sposób wymaga resetów przy tworzeniu. 

A pseudokody? Okazuje się, że modyfikacje są tak nieznaczne, że można opisywać je równocześnie... 

 

Założenia: Wypełniamy obszar labiryntu ścianami, które będziemy burzyć podczas odwiedzania. Potrzebna jest dodatkowa funkcja zwracająca wektor lub pole bitowe pól odległych o dwa, czyli dwa pola obok w pionie, poziomie jako następne do zwiedzania. Wektor zwraca, czy ściany występują (pola nieodwiedzone), czy też już wyburzone (pole odwiedzone).  Dlaczego nie sąsiednie? Ponieważ potrzebujemy miejsce na ewentualną ścianę, która też jest polem prostokąta. Inaczej z labiryntu utworzy się plac wypełniajacy cały obszar. 

Obszar to tablica wypełniona liczbami o interpretacji np. 0 ściana widoczna, 1 ściana niewidoczna ukryta w mgle, 2 przejście widoczne, 3 przeście niewidoczne, 4 sekret nieodkryty, 5 sekret niewidoczny nieodkryty, 6 sekret odkryty widoczny...
Przy rysowaniu mapy wyświetlane tylko pola z wartościami parzystymi, a zmniejszaniem o 1 zajmie się osoba wędrująca po labiryncie odkrywajac go równocześnie.

1) Start. dla stosu oraz podczas pierwszego resetu dla list wchodzimy na pole początkowe, które odwiedzamy

2) Jesteśmy na odwiedzonym polu, odkładamy je na stos albo, w przypadku listy tuż po resecie, szukamy na liście pola, które przylega (krokiem 2) do już odwiedzonego pola. Łączymy je korytarzem, któremu można nadać status ukrytego przejścia

3) Wywołujemy funkcję zwracajacą zabudowę okolicznych pól dystansu 2

4) Losujemy kierunek, w którym pójdziemy. W przypadku stosu ograniczamy się tylko do nieodwiedzonych pól, o ile istnieją, wtedy czasem wyboru nie ma -- ślepy zaułek;
W przypadku listy z możliwymi cyklami przebijamy korytarz w wylosowanym kierunku zanim sprawdzimy wartość funkcji z 3). W końcu programistyczny kilof w garści jest labirynt[pozycja]=dostęp... 
 

5) Gdy wylosowany kierunek wskazuje nieodwiedzone pole, odwiedzamy je niszcząc także ścianę je przedzielajacą;
gdy jednak jesteśmy na już odwiedzonym polu, w przypadku stosu zabieramy element ze szczytu by wrócić pole wcześniej; zaś w przypadku list następuje reset.
Sprawdzamy także warunek końca algorytmu: stos ma być opróżniony albo lista pól do odwiedzenia pusta, czyli albo punkt 6), albo 2) gdy coś jeszcze zostało do wyburzenia / sprawdzenia

6) Stos pusty albo lista pusta -- cały obszar jest wypełniony labiryntem.
Można dołożyć drobiazgi czyli mgła na polach (np. wartość+1), skarby, NPC, oponenci. 

Kiedy implementowałem labirynty listą, okazało się, że są generowane nieco szybciej niż stosem, gdyż ten po wypełnieniu całego obszaru zwykle zawiera dużo pól. Nieodwiedzone pola wyznaczane z list były podłączane znacznie wcześniej. I nawet resetów nie było zbyt dużo.
Zaś w jednym wylosowanym przypadku napotkałem korytarz, whodzę -- sekret, mijam, kolejny sekret, i tak powstał długi korytarz wypełniony sekretnymi przejściami, widocznych już wcześniej na mapie labiryntu, ale dostępnych dopiero po znalezieniu przejścia daleko w przeciwnej części obszaru. W sam raz na znalezienie NPCa lub ukrywajacego się bandyty. 

Miłego zwiedzania...

To nie heurystyka, działa bardziej ogólnie korzystając z cech podzielności

Wspomniałem o szybkiej heurystyce rozkładu liczb. 

 

Liczbę szacuję za pomocą potęg 4, oraz zapisuję N jako parabolę o równaniu
a*p*p + b*p + c = N = q*r,

gdzie początkowo a jest jedną z trzech wartości power(4,k). 2*power(4,k), 3*power(4,k), a<p, Podstawa p też poczatkowo jest potęgą 4 bliską a, współczynniki b i c nieujemne są bliskie p, najlepiej z przedziału (-p, 3p).

 

Będziemy to modyfikować pilnując, by p było jak największe. Przy b i c stosunkowo niewielkich małe dzielniki mogą być niewykrywalne - iloraz dzielników r/q, r>q jest zbyt dużą wartośc ią, zaś algorytm czynimy zbieżnym do tego ilorazu. W tym przypadku należy sprawdzić, czy można doprowadzić do istnienia wspólnego dzielnika wszystkich współczynników.

 

Przekształcenie niezmiennicze dla wartości N przesuwa podstawę

[a, b, c, p] = [a, b-2k, c-2k*b+k*k*a, p+k]  (jak np. (1, 4, 4, 8] = [1, 0, 0, 10]

dla dowolnego k całkowitego. Dla tego przekształcenia c ze wzrostem p jest malejace, oraz szukamy jednej z dwu wartości, gdzie a+b+c  albo a-b+c sa całkowitymi wielokrotnościami p-1, p+1. Warto poszukać zmian znaku c dla jednego, lub niezależnie obu funkcji liniowych. Nie zwracają jednej wartości.

Kolejne przekształcenia niezmiennicze wartości N:

[a, b, c, p] = [a, b+1, c-p, p]  np. [5, 3, -1, 10] = [5, 2, 9, 10] = 529

[4a, 2b, c, p] = [a, b, c, 2p] np. [12, 2, 3, 10] = [3, 1, 3, 20]

płaszczę nieco parabolę przesuwając znalezioną wartość. Wymaga znów szukania miejsca, gdzie c ze zmianą p zmienia znak.

Kiedy spłaszczymy parabolę na tyle, że a+b+c=(p-1)*const, dzielnikiem liczby N jest p-1; Gdy a-b+c=0 + p*const, dzielnikiem N jest p+1. Przypomina to cechy podzielności przez 9 oraz 11 w dziesiątkowym - wszak to jest uogólnienie tych przypadków. 

Jęsli dopasujemy wartości a+b+c=p-1 oraz a-b+c=0 odległe dokładnie o 2, między nimi jest postać [a,b,0,p], skąd odczytujemy rozkład N = p * (a*p+b).

Teoretycznie jest to bardzo szybkie. Dla wyboru a oraz jednej funkcji mamy nie więcej niż 3*220 płaszczeń i wyszukiwań liniowych w przypadku RSA 200.

 

Przykładowo 259 zwraca swój dzielnik dla [4, 0, 3, 8] (suma 4+0+3=8-1=7, suma naprzemienna o wspólnym dzielniku [7, 35, 7, 4]).
Niektóre dzielniki można wychwycić dla dwu różnych wartości a - funkcje wykażą je od 'przeciwnych' stron, mniejszej albo większej.

Przekształcenia, chybione podejście, ale w szczególnym przypadku...

Kiedyś pokazałem, że resztę z dzielenia można przetrzymywać nie na cyfrze najmniej znaczącej, lecz na najbardziej znaczącej podczas przekształceń liczby. 

Kolejne przekształcenie też znajduje dzielnik, w nim niezmiennikiem jest wartość
n = a*b + reszta
w którym a zwiększamy stale o 1, zaś b maleje, co wynika z odpowiedniego rozszerzenia wzoru
(a+1)*(b-1) = a*b + b-(a+1)
brane modulo (a+1), gdy a*b jest znane. Wartość b maleje o około b/a z dokładnością do plus minus jeden oraz tłumi się geometrycznie. Reszta się stale dopasowywuje -1< reszta < a.

Zatem można bezpośrednio przechodzić z a*b na wartość (a+1)*b' + reszta' też równe n, korzystając początkowo z dzielenia, potem to dzielenie degraduje się do odejmowania/dodawania odpowiedniej wielokrotności a+1. 

Czy można to zastosować do systemów niedziesiątkowych, szybko znajdując resztę (cecha podzielności przez odpowiednik 11)? Parę przykładów i odpowiedź: NIE.
Chodzi o to, że jeśli n nie jest wielokrotnością podstawy, to nie istnieją rozwiązania odpowiednich kongruencji, by dopasować cyfrę najmniej znaczącą. A dlaczego wspomniany na początku sposób zadziałał? 

Odpowiedź: wybrane n było nieparzyste, które zawsze modulo 2 daje resztę 1, co wystarczyło. Uzyskujemy postać binarną jednego z dzielników, który na najmniej znaczącej pozycji ma 1. I to było przyczyną powodzenia.

Iloczyny bez przeniesień

 Przypomniała mi się pewna własność. 

Mnożenie pisemne, Karatsuby i wiele innych składają sie z dwu części: obliczenie iloczynów cząstkowych oraz ich suma wygładzana za pomocą przeniesień. 

Jednak istnieją iloczyny, w których nie ma przeniesień, np. 11*131 = 1441.
Liczby te mają ciekawą własność: iloczyn sum cyfr dzielników jest równy sumie cyfr iloczynu: w tym przykładzie 1+1=2, 1+3+1=5, oraz iloczyn 2*5 = 10 = 1+4+4+1. 

Jak już kilkakrotnie wspominałem i korzystałem podczas rozkładów liczb, wyeliminowanie przeniesień pozwala na szybsze znajdywanie rozkładu. Ta własność ma predyspozycje do testowania przy odwracaniu mnożenia, czy pobraliśmy właściwe cyfry. Nie od razu, jak sądzę. Nie badałem jeszcze tego dokładnie, 

Aktualnie 'marnuję czas' na znajdywanie wszystkich liczb pierwszych ograniczonych z góry. Powinienem znać dopiero kilkaset, Rozpoznałem już tysiące różnej wielkości i kilkunastu kandydatów na pierwsze, których pierwszości na tym poziomie obliczeń jeszcze nie jestem w stanie zdiagnozować.

Bańka wyszukiwarki a testy pierwszości

 Długo nie zaglądałem na niektóre strony matematyczne. Kiedy spróbowałem tam dotrzeć, nie były mi proponowane w DuckDuckGo (odpowiednik google z interfejsem łatwo modyfikowanym na ciemny). Wyrzuciło mnie z tej bańki generowanej jako proponowane podpowiedzi przeglądarek. 

Potrzebowałem wpisać wiecej informacji, że strona była na Poznańskim Portalu Matematycznym uniwersytetu, by ponownie ją znaleźć.

A jest tam wyprowadzony bardzo ciekawy test pierwszości liczb związany z systemem Fibonaciego i dziesiątkowym. Pozwolę sobie go tu powtórzyć: 

Ciąg Fibonacciego jako test pierwszości
Jeśi p jest liczbą, obliczamy p-tę liczbę Fibonacciego jako F_{p}. Liczba złożona p nie spełnia poniższych warunków:
Jeśli p ma resztę plus minus 1 modulo 5, F_{p} przystaje do 1 oraz F_{p+1} przystaje do 1 modulo p, to jest możliwe, że liczba p jest pierwsza;
jeśli p ma resztę plus minus 2 modulo 5, F_{p}+1 przystaje do 0 modulo p oraz p dzieli F_{p+1}, to jest możliwe, że p jest pierwsza.

Wynika to z implikacji:
jeśli liczba p jest pierwsza, to spełniony jest zawsze jeden z trzech warunków:
p jest piątką p=5;
p jest dzielnikiem F_{p-1} oraz F_{p}-1; 
p jest dzielnikiem F_{p}+1 oraz F_{p+1}

Przypominam z logiki - odwracanie kolejności w implikacji nie zawsze jest prawdziwe. Warunki te zależą od cyfry jedności systemu dziesiątkowego. Niestety, liczby F_{p} są gigantyczne dla większych p... Można je jednak stosunkowo łatwo wyznaczyć, gdyż liczby Fibonacciego wyznacza się jako modułowe iloczyny macierzy. Na wspomnianej stronie są szczegóły. 

By wejść bliżej do bańki z fachowymi rezultatami, zajrzałem na stronę wielomianowego deteministycznego testu pierwszości AKS
aks [dot] bluhost [dot] pl
przejrzałem i nieco mnie zaskoczył opis implementacji. Nie chodzi o to, że algorytm nazywa się wielomianowym, ale tam występuje znajdowanie rzędu elementu w grupie multiplikatywnej. Zaś odwrócenia niektórych sit mają dokładnie tę samą liczność operacji, bo poszukują najmniejszego rzędu, ale w analogicznej grupie addytywnej. Dlaczego zatem dociera do mnie informacja, że 'nie ma  wielomianowego algorytmu rozkładu liczb na czynniki'? W literaturze podaje się ich złożoność jako zależną od bardzo dużej stałej, właśnie rzędu czynnika. A dokładnie to samo występuje przy wyznaczaniu stałej r w teście pierwszości AKS. Czyli jak dla mnie: wyznaczam odległość od czynnika niby niezależnie od rozkładanej liczby, a potem wykorzystuję go, by dowieść, że jest najmniejszy. Zapominam dokonanych obliczeń, by dowieść czegoś słabszego. A finalnie mam ogólną złożoność lepszą niż dla złożoność fragmentu wewnętrznego. Coś mi tu nie gra.
Wnioskuję, że te sita przegrywają z testem pierwszości, gdy mam bardzo duże wartości. A przekształcenia, które stosuję właśnie w tym obszarze są ignorowane, bo trudno jest zauważyć niesamowitą kompresję im towarzyszącą. Doświadczenia z małych wartości przenoszone są poza swój zakres występowania. Tak jak prawo Hooka, które działa tylko w stosunkowo wąskim zakresie, ktoś usiłuje stosować dla wszystkich przypadków.

Dodatkowo zauważam jeszcze jedną własność przyspieszajacą obliczenia w tych przedziałach, gdzie mój zapis korzysta z iloczynu dwu liczb dwucyfrowych, w których cyfry 'jedności' są znacznie większe niż 'cyfry dziesiątek'. Nie muszę obliczać za każdym razem tego iloczynu, bo mogę korzystać z wartości wyznaczonej iterację wcześniej, wtedy mnożenie dużych ;jedności' jest zastępowane stałym iloczynem znacznie mniejszych 'dziesiątek' oraz kombinacją liniową, która przedziałami maleje ze wzrostem podstawy systemów.

Specjalna postać liczby jako palindrom o współczynnikach nieujemnych, kandydat na test pierwszości

Z odpowiednio dużych liczb można tworzyć palindromy nad systemami pozycyjnymi. Tych, które mają wszystkie współczynniki niezerowe, jest mało. Najwięcej jest takich palindromów nad systemem binarnym. Im większa podstawa, tym jest ich mniej, aż w końcu przestaje się je spotykać. Niemniej nadal mogą się pojawiać. 

Jak wygląda palindrom długości trzy z dużej liczby N o największej możliwej podstawie i wszystkich wartościach nieujemnych? Okazuje się nim wartość
0 1 0 _ N,
bo to jest 1*N=N, a kolejny jest dla podstawy rzędu pierwiastka kwadratowego z N, bo wymagana nieujemność wyrazów skrajnych wymusza, by podstawa była mniejsza niż pierwiastek kwadratowy z N. Można sprawdzić tworząc palindrom z 37 nad postawą 6, to jest właśnie ten przypadek. Inazej wyraz środkowy staje się ujemny.

Zawsze? 

Nie, tylko dla liczb pierwszych.
Liczby złożone utworzą dodatkowy palindrom o współczynnikach nieujemnych nad podstawą będącą dzielnikiem N większym niż pierwiastek kwadratowy z N. Wynika to z cechy podzielności, gdyż największy z palindromów tego dzielnika jest mnożony przez mniejszy z dzielników. Czyli dla N=p*q, p<q uzyskamy
0 p 0 _q,
oraz sqrt N < q < N. 

Można potraktować jako (khm) test pierwszości:
Jeśli tworząc z liczby N palindromy długości 3, nie występuje palindrom o współczynnikach nieujemnych dla podstaw (sqrt N, N), liczba N jest pierwsza. 

Przedział do sprawddzenia jest gigantyczny,,, Nawet gdy ktoś wykorzysta, że w tym przedziale reszty z dzielenia przez kolejne wartości tworzą wykres piłokształtny przedziałami monotoniczny. Występuje obszar, w którym długość ząbka jest mniejsza niż 1 -- odległość między śasiednimi liczbami naturalnymi.

Liczby pierwsze najbliższe, albo wszystkie, nie większe niż dana wartość

- Mam dużą liczbę N. Wskażcie proszę najbliższą jej liczbę pierwszą. 

Albo nie, wypiszcie WSZYSTKIE liczby pierwsze ograniczone z góry przez N. 

Ci którzy posłużą się sitem Eratostenesa biegną zażyczyć sobie bardzo dużego dostępu do pamięci, w którym zamieszczą wszystkie liczby nie większe niż N. 

Osoby posługujące sie obliczeniami szykują sobie szybkie procesory, by sprawdzać pierwszość kolejnych liczb N minus k, gdzie k są kolejnymi liczbami naturalnymi. Sprawdzają też schematy występowania liczb złożonych dla przespieszenia obliczeń.

- A ty, który siedzisz w systemach niedziesiatkowych? Jak sobie poradzisz? 

Mogę skorzystać z początkowych liczb pierwszych? Z ich iloczynu? W takim razie sklecę sobie liczbę gładką najbliższą N z iloczynu kolejnych liczb pierwszych i jeszcze jednej, przybliżającej N. A potem odwrócę sito Eratostenesa do tych wartości, szukajac liczb p-kwadrat gładkich, gdzie p będzie mi podstawą systemu, rosnącym, aż znajdę rozkłady kanoniczne wartości najbliższych N. 

- Chcę liczby pierwsze, nie rozkłady kanoniczne. 

Rozkłady kanoniczne posłużą mi tylko po to, by dla liczby złożonej wskazać, o ile mam skoczyć, by znów trafiać na liczby złożone, oraz ją usunąć jak będzie za gładka. Będę używać zarówno czynnikow pierwszych, jak i ich potęg. To, co zostanie nie wskazane podczas zmian p, okaże się liczbami pierwszymi. Skoki zwiększajace odległość od N będą mi wskazywać liczby coraz mniej złożone, które w końcu staną sie pierwsze. 

- Pozostałe iloczyny mogą być złozone. Możesz też pominąć którąś z liczb pierwszych. Zresztą twoje podstawy mogą być liczbami złozonymi.

Początkowo iloczyny będą złozone. Dlatego potrzebuję tej liczby gładkiej. Zapiszę ją jako iloczyny liczb dwucyfrowych przy podstawie p. Zamiast liczyć resztę kolejnych wartości p przez N, najpierw przekonwertuję ją na system o podstawie p, po prostu odejmując od cyfry jedności cyfrę dziesiątek poszczególnych czynników, reszta z dzielenia przez N jest iloczynem cyfr jedności czynników, zmodyfikowanych odległością od N. Wskaże mi to odległość od N, gdzie występuje liczba podzielna przez p, czyli złożona. Dopisując w każdym kroku wartość o kolejnej odległosci p od N pokryję wszystkie wartosci. 
Jeśli w początkowej tablicy przy tej odległości jest zapamiętana jakaś wartość większa od p kwadrat, może okazać się albo pierwsza, albo złozona. Kiedy jest podzielna przez p, to p jest kolejną liczbą pierwszą gotową do odłożenia. W przeciwnym razie złozone p uzyska się rozkłądu kanonicznego dla tej odległości. I do tej reszty mogę już nie wracać, pamiętając tylko te wartości wraz z ich odległosciami od N, które podejrzewam o bycie pierwszymi. 

- Z początku masz iloczyny liczb jednocyfrowych.

Iloczyn dwu odpowiednio dużych liczb jednocyfrowych jest dwucyfrowy. Kwestia podstawy. Zmiejszać będzie mi się krotność czynników przy okazji. 

- Potrzebujesz pamięci na wszystkie liczby pierwsze nie wieksze niż N... 

Większej, być moze dwukrotnie - pamiętam też kolejne potęgi liczb pierwszych, zaś sumy tych potęg są mocno ograniczane, wszak suma odwrotności kwadratów jest skończona, co stanowi pułap górny dodatkowej pamięci. Ale tablica rozrasta mi sie w trakcie poszukiwań i sprawdzeń, czy p jest pierwsza, czy nie, kolejne wartości będą mi wypierane przez liczby pierwsze oraz ich potęgi. A potem pozostają tylko skoki na kolejne wielokrotnosci liczb pierwszych, między którymi szukam, gdyż już znam te liczby pierwsze, dla których wartości sa p-kwadrat gładkie.

- A dlaczego nie liczby p-głądkie? 

Jeśli mam liczbę dwucyfrową, o której wiem, że nie jest wielokrotnośćią żadnej liczby pierwszej mniejszej niż podstawa, to liczba ta jest pierwsza.

- To moze się udać... 

A tablica liczb pierwszych zaczyna się od największych rozpoznanych jako pierwsze. Potem schodzę jakby grzebieniem po kolejnych. Najdłużej potrwa szukanie tych, które się nieco większe niż połowa N, trzecia część N i tak dalej. Potem wystarczy posortować pozostałe, albo działać tak długo, aż same się posortują.
Jeśli chcę znać najbliższą, dopuszczam odległości od N ujemne, by móc sprawdzać także wartości wieksze niż N. I warto mieć lekki zapas odległości.

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.