Możliwe własności dzielników liczb w palindromach

 Zastanawiałem się, czy można uzyskać palindrom nad systemem o podstawie o jeden mniejszej niż któryś z dzielników d liczby n. 

Palindrom wyglądałby tak:  a  a+b  a+b  a, wykorzystując fakt, że przy tej podstawie dzielnik wygląda następująco d = 1 1 _{d-1}. 

Lecz dla większych wartości pozostały n/d musiałby być przedstawiony jako palindrom nad tym systemem. Możliwe, ale bardzo kłopotliwe. 

 

Zaś dzielniki w palindromach nad systemem binarnym długości 3 mogą mieć postacie następujące 

ad   bd   ad _2

gdzie d jest dzielnikiem, oraz n/d = 4a+2b+a = 5a+2b. Nieskończenie wiele możliwości, lecz jeśli chcieć znaleźć któryś, trzeba znać d lub n/d. Niknie w tłumie.

W tym szczególnym przypadku iloraz wyrazu skrajnego do środkowego wynosi

(ad)/(bd) = a/b. 

Kolejna wersja przeglądu zupełnego sitem

Wspominałem już o możliwościach przeglądu zupełnego za pomocą sita. Wtenczas potrzebowałem jako lemat tablicę liczb pierwszych nie większych niż pierwiastek czwartego stopnia z liczby rozkładanej. 

W tej wersji nadal pozostanie struktura stogu, w której odkładam parę: 

[podstawa systemu p, lista jej znanych dzielników pierwszych d_i] 

struktura działa tak samo ja opisałem wcześniej: po pobraniu wartości, zanim ulegnie skasowaniu, odkłada na stóg wartości [p - d_i, d_i] dla wszystkich znanych dzielników p. 

Wówczas należało odróżnić dzielniki wykryte od już przetestowanych. Teraz w strukturze tej odkładane są tylko znane liczby pierwsze, sprawdzone pod kątem podzielności. 

 

Potrzebuję drugiej struktury: listy par, w której trzymam duże wartości będące iloczynami liczb pierwszych lub takimi liczbami, oraz albo ich wartość początkową, albo odległość (dystans) od miejsca startowego algorytmu. Jest to niezbędne, gdy przy wyznaczaniu odległości znajdujemy liczbę pierwszą, aby ją właściwie umieścić w strukturze stogu. Wygodniej jest użyć odległości, chociażby z uwagi na mniejszą wartość choć bardziej skomplikowane jest wtedy znalezienie wielokrotności aktualnego dystansu.

 

Jak to wygląda w praktyce -  na początku. 

Liczbę rozkładaną n przedstawiam w postaci 

n = (a*p+b)*p+c

np. n = (1 * 38 8878 4050 9055 + 2)* 38 8878 4050 9055 - 21 1614 4142 3728

Wartością początkową będzie bliska pierwiastkowi kwadratowemu b= 38 8878 4050 955, którą w każdej iteracji zmniejszamy o 1 do połowy jej wartosci, lub przez odpowiednio dużą potęge 2^i ( 2^i < sqrt n < 2*2*i ). Równie dobrze możemy przesunąć do najbliższej potęgi 2 większej niż pierwiastek kwadratowy z n, przyjąć a=1 oraz b ujemne.

Liczbę możemy równoważnie zapisywać na inne sposoby:

n = (1 * 38 8878 4050 9055 + 1)* 38 8878 4050 9055 + 17 7263 9908 5327

n = (1 * 38 8878 4050 9060 - 9)* 38 8878 4050 9060 + 17 7263 9908 5347

n = (1 * 70 3687 4417 7655 - 48 8781 7820 0808) * 70 3687 4417 7655 - 7 3130 0816 6378

Dobór, według wielkości wartości, wartości początkowych itp. 

 

W poprzednim algorytmie znajdowałem, że 

38 8878 4050 9055  ma dzielniki:  5, 19, 41, 239, 177 4231, i dzieliłem c = 17 7263 9908 5327 przez każdy z nich. 

Teraz nie znam tych dzielników, zatem w strukturze listy par odkładam np. wartość 38 8878 4050 9055 i tą samą wartość (odległość 0). Po czym obliczam największy wspólny dzielnik 

gcd( 38 8878 4050 9055 , 17 7263 9908 5327 ) 

zatrzymując, gdy wartość gcd() zmniejszy się poniżej odległości. W strukturze stogu nic na razie nie odkładam. W ten sposób wiem, że dzielniki tej liczby są względnie pierwsze z liczbą rozkładaną, nie znając jeszcze tych dzielników. No chyba że znajdę dzielnik całej liczby, zwrócony przez gcd()!

Biorę następną wartość z podstawą mniejszą o 1, ze zwiększoną odległością o 1, w której modyfikuję konwersją: b=b+2, c = c+b-a, wartość n jest niezmiennikiem: 

n = (1 * 38 8878 4050 9054 + 4)* 38 8878 4050 9054 - 21 1614 4142 3725

Wśród obu wartości p, p-1 dokładnie jedna jest parzysta, zatem w strukturze par dzielę przez odpowiednie potęgi 2 zmniejszając wartość pierwszego elementu pary, i znajduję pierwszą liczbę pierwszą, która zaznacza pozycje parzyste w strukturze stogu: 

[38 8878 4050 9054-2 ;  2]

W drugiej strukturze wyeliminowane są zarazem wszystkie wystąpienia 2. Jest ona tylko w stogu, i ta liczba pierwsza zmniejsza podstawę p dla liczenia wspólnego dzielnika. 

Przyjmując następną wartość, wiem, że spośród wszystkich odłożonych w strukturze par i pobranej, co najwyżej jedna jest podzielna przez aktualną odległość. Jeśli jej nie znajdę, odległość jest liczbą złożoną, z już uwzględnionymi czynnikami pierwszymi. 

Myślałem, by sprawdzać kolejno wszystkie wartości struktury par w poszukiwaniu właciwej, a po jej znalezieniu, podzieleniu przezeń. Ale widzę szybszy sposób, mam dwa wskaźniki, jeden na wartość największą struktury, drugi na najmniejszą, zaś wartości z jedynką usuwamy ze struktury.  Jest to potrzebne z dwu powodów: wartość największa wskazuje resztę z dzielenia wskazywanej podstawy przez aktualny dystans, co w prosty sposób wskazuje właściwą wartość, którą normalnie dzielimy. Jest podzielna, uzyskujemy nową liczbę pierwszą do wyeliminowania ze struktury par i przeniesienia do stofu (zarazem już sprawdzona, że nie jest dzielnikiem n).

Jeśli po wyrugowaniu znalezionej liczby pierwszej ze struktury par uzyskamy wartość 1, kasujemy parę. Sprawdzamy, która jest najmniejsza, jeśli okaże się, że najmniejsza jest tylko dwucyfrowa w systemie o podstawie dystansu, jest to kolejna liczba pierwsza do wyrugowania, tzn. przeniesienia do stogu.    

Np. 

struktura par ma wartości (punkt startowy 70 3687 4417 7664 - potęga 2)

dystans 2   wartość 35 1843 7208 8831
dystans 3   wartość 70 3687 4417 7661 (największa)

Po kilku iteracjach znajdziemy się w odległości 7 od punktu startowego, czyli podstawą jest 70 3687 4417 7657. Sprawdzamy liczbę 7, szukając reszty z dzielenia przez 7 wartości z dystansu 3. Znajdujemy resztę 6, czyli przez 7 podzielna jest liczba z dystansu 3-(7-6)=2.
Mamy nową wartość dla tego dystansu po wyrugowaniu liczby pierwszej 7
dystans 2   wartość 5 0263 3886 9833

I wiemy, że liczba nie dzieli się przez 7, co sprawdziliśmy kilka iteracji wcześniej. Po kolejnych dwu iteracjach dystans wrazsta do 9. Reszta sugeruje, ze liczba ta znajduje się dla dystansu 7, ale mamy tam wartość 7 8187 4935 3073, która nie jest podzielna przez 9, zatem dystans 9 = 3*3 jest liczbą zlożoną z uwzględnionymi już czynnikami.  Ta ogromna wartość jest liczbą pierwszą, która rozpoznana jako pierwsza przejdzie do stogu dopiero przy dystansie 2796203.

I ten sposób sprawdza początkowo dosyć szybko małe liczby pierwsze i giganty. Z biegiem czasu mniejsze liczby pierwsze rozkładają podstawę  systemu stogu, tak że wspólny dzielnik od razu jest widoczny, A po jeszcze dłuższym okresie zostają do sprawdzenia tylko liczby pierwsze, często większe niż podstawa systemu.
Są one wyłapywane przez ich nieobecność w strukturze stogu podczas pobierania kolejnej wartości o 1 mniejszej, lub przechodzą ze struktury par przy dużym dystansie.

Możliwość dalszej modyfikacji znajdowania największego wspólnego dzielnika

Miotam się ostatnio między programowaniem w stylu gier paragrafowych, a kontynuacją wymyślania sposobów rozkładu. 

Można jeszcze bardziej zmodyfikować sposób obliczania wspólnego dzielnika. Wiem już, że mogę dzielić argumenty przez małe liczby, które są podzielne przez dokładnie jeden z argumentów, oraz zatrzymać algorytm, kiedy osiągnie odpowiednio małą wartość przy narastajacej wiedzy o braku dzielników w tym zakresie. 

Można to robić mniej zachłannie, co o dziwo jest w stanie zwiększyć szybkość zmniejszania się argumentów.
Jeśli oba argumenty są nieparzyste, i wiem, że wspólnym dzielnikiem nie jest wielokrostość 2 lub 5, mnożę jeden z argumentów przez małą stałą, by uzyskać taką samą cyfrę najmniej znaczącą. Następnie odejmuję. Uzyskana różnica jest podzielna przez 10, dzielę przezeń, potem jeszcze przez ewentualne dwójki. W ten sposób w jednej iteracji mogę zmniejszyć wartość o rząd wielkości. 

Zobaczmy na przykładzie liczb Fibonacciego, które tworzą najdłuższy ciąg zbieżny do wspólnego dzielnika: 

nwd(377, 233) 

Ponieważ 3*9 = 27 mają tę samą cyfrę najmniej znaczącą, liczę nwd( 377, 9*233) = nwd( 377, 2097), Odejmuję je 2097-377 i dzielę przez 10 i jeszcze kilka 2. Uzyskuję: 

nwd( 233, 43 )

Postępując jak wcześniej (tym razem cyfra 3 taka sama, bez mnożenia), dostaję

233-43 = 19*10

czyli nwd(233, 43) = nwd( 43, 19). 

Można kontynuować, uzyskując w kolejnym kroku nwd (3*43, 19), lecz rozsądek podaje, by wrócić do standardu i uzyskać parę nwd(19, 5). Kolejna operacja (ze zmianą znaku) zwraca nwd (19,4*5) = nwd (19,20) = 1. 

Łącznie 4 iteracje, a standardowym odejmowaniem algorytmu Euklidesa byłoby 13.  

Stosuję to do sprawdzania kolejnego algorytmu rozkładu przeglądem zupełnym z sita, w którym potrzebowałem znać tablicę liczb pierwszych nie większych niż co najwyżej pierwiastek czwartego stopnia z liczby rozkładanej. Chyba nie potrzebuję znać tej tablicy kosztem dodatkowej struktury.

Właności związane z dzieleniem wstecz a wstępnym przybliżaniem dzielników

Kontynuując prace nad podejściem, który może okazać się wielomianowym (tzn. jedna iteracja znajduje dokładnie jedną cyfrę dzielników), przyglądam się blizej dzieleniu wstacz. 

Jeśli liczba złożona kończy się np. na 3, cyframi najmniej znaczącymi dzielników są pary (1,3) lub (7,9), bo 7*9 = 63. Inne iloczyny dają inne reszty. 

Cyfry dziesiątek, jeśli liczba kończy się na .53, oraz zakładamy, że cyfry najmniej znaczące dzielników to 9*7, to na cyfrze dziesiątek dzielników może wystąpić jedna z następujących kombinacji (kropka oznacza wcześniejsze cyfry):

(9,4):  .97* .49

(8,1):  .87* .19

(7,7):  .77* .89

(6,5): .67* .59

(5,2): .57* .29

(4,9): .47* .99

(3,6): .37* .69

(2,3): .27* .39

(1,0): .17* .09

(0,7): .07* .79

Zwróćmy uwagę, że zmianie o 1 cyfrze pierwszego z dzielników towarzyszy zmiana o 3 modulo 10 cyfry drugiego dzielnika. Jest to związane z parą cyfr najmniej znaczących. Wyraźny schemat, który będzie się powtarzał przy doborze kolejnych cyfr. 

Jeśli szukamy cyfry na pozycji n,  mocno zmienia ona tylko najbliższych n cyfr (bez uwzględniania przeniesień),  a na wcześniejsze działa tylko proporcjonalnie. Zmiana pary cyfr na danej pozycji wymaga ponownego sprawdzenie uzyskanych par cyfr bardziej znaczących. Modyfikują się one.

Weźmijmy zachłannie pary o największym poprzedniku na kolejnych pozycjach i przybliżmy rozkładaną wartość. 

Dla liczby 893 4053 są to 9997*8649 = 8649 4053, która ma ostatnie 4 cyfry identyczne z rozkładaną. Zmieniajac pary na pozycji tysięcy wartość nieco uscylując zmniejsza się do 1997*4649 = 928 4053, która jest lepszym przybliżeniem. 

Jeśli teraz zmienimy parę na pozycji setek, należy na nowo uzgadniać cyfry tysięcy, np do 1897*6349 = 1204 4053. Para tysięcy (1,4) przekształciła się tą zmianą na (1,6). I zmieniajac pary setek uzyskujemy najlepsze przyblizenie dla par setek (2,5), iloczyn 1297*6549 = 849 4053, oraz 1197*8249 = 987 4053. Przybliżenie straciło nieco na wartości, ale jest najlepsze dla zmian, kiedy modyfikujemy cyfry setek, a koregujemy cyfry tysięcy. Nie trafiamy dokładnie w rozwiązanie. Lecz dalej trzymamy się blisko wartości liczby rozkładanej. Zmiany sięgają tylko trzech cyfr, więc można założyć, że cyfry stojace na pozycjach tysięcy są już dobrym przyblizeniem cyfr dzielników. Prawidłowa para cyfr tysięcy to (1,8). Zmiany w dopasowaniu cyfrach setek przy znajomości cyfr tysięcy okazały się przedziałami monotoniczne.

Następna zmiana cyfr dziesiątek już wygeneruje wartość rozkładaną. O ile będziemy starać się za bardzo nie oddalać  od par (1,7) tysięcy i (1,2) setek.

W ten sposób przeszukiwanie 9*10^{2} możliwości (cyfry jedności uważamy za znane, dzielniki mają po 4 cyfry) sprowadza się do przeszukiwania wartości lepiej przyblizających rozkładaną wartość. Zamiast kolejno - skaczemy nad oscylacjami.

Wstępne informacje o bardzo szybkim znajdowaniu dzielników

Poprosiłem pewną osobę, by przetestować sposób rozkładu liczb. I udało się. Osoba ta znalazła dzielniki mojej 'ulubionej' wartości 8934053 w czterech krokach. Czyli tylu, ile cyfr liczą sobie dzielniki. 

Sposób polega na zastosowaniu dzielenia wstecz, w którym znajduję najmniej znaczące cyfry potencjalnych dzielników. Np. cyfra jedności to 3, to dzielniki mają cyfrę jedności 1 oraz 3, albo druga ewentualność 7 i 9. 

Każdy krok ma dwie fazy. W założeniu znamy już najmniej znaczące cyfry liczby a*b.

Pierwsza faza generuje wszystkie możliwe iloczyny (xa)*(yb), gdzie x,y to wszystkie potencjalne możliwości cyfr. Jest ich w systemie dziesiątkowym 100. Ale z porównania z cyfrą na zadanej pozycji okazuje się, że łatwo wyeliminuję 90 z nich. pozostaje tylko 10. 

Zrobiłem szablon w Escelu, mnożę (0a), (1a), ... (9a) przez (0b), (1b),... (9b). 

Od liczby rozkładanej odejmuję tę wartość i dzielę przez potęgę 10 taką, że tylko 10 liczb pozostaje całkowite - to są kandydatki przechodzące do drugiej fazy. 

Np. w drugim kroku wychodząc od 7*9 badam pary, wśród których przewija się między innymi 87*19.  

Druga faza to eliminacja tych kilkunastu wartości. Rozszerzam aktualny system trzykrotnie dla tych już zmniejszonych wartości. I tu napotykaliśmy na silne związki odpowiedzi (xa)*(yb) z cyfrą liczby npozycji obliczanej w danym kroku  oraz samym a*b. Reszty rozszerzonego trzykrotnie systemu po uwzględnieniu cyfry liczby n były całkowitymi wielokrotnościami a*b dla dokładnie tych cyfr, które miały dzielniki. Dla pozostałych iloczynów pojawiały się reszty. I w ten sposób dochodziliśmy do jednej pary, która okazywała się kolejnymi bardziej znaczącymi cyframi dzielników.

W jednym kroku pojawiła się nawet szansa na uzyskanie gotowego wzoru. Zapomnieliśmy niestety o szczegółach przygotowania liczb przechodząc dalej.

Wiem, że jeśli z liczby n zabiorę resztę modulo p, podzielę przez 10p i przedstawię w systemie o podstawie 3p, to reszta będzie specyficznie większa, jeśli od n odejmę a*b, podzielę przez 10p i dopiero teraz przekonwertuję na system o podstawie 3p. 

Oraz, im wiecej znanych cyfr dostawały dzielniki, tym obliczenia stawały się prostsze i łatwiej było wskazać kolejną parę prawidłowych cyfr dzielników (x,y). W ostatniej fazie nawet nie musieliśmy rozszerzać, bo kolejna para prawdłowych cyfr sama się nasuwała.

Przegląd zupełny iloczynami liczb jako faktoryzacja

 Jeśli każda z cyfr liczby jest podzielna przez d, cała liczba też jest podzielna przez d.
Stwierdziłem ten fakt w poprzednim poście. I chciałem zastosować do liczb w systemie Fibonacciego. Same przeksztalcenie są trudne dla człowieka, nie z racji obliczeń, ale tego, że zmiany występują równocześie w trzech różnych miejscach, kiedy używam schematu nad liczbami Fibonacciego: 
[00300] = [10001]
Zapominam ciągle o tych zmianach na wszystkich trzech pozycjach [x0x0x].
Zatem zaczynam przekształcenia, i myśląc nad zapisem powoli dochodzę do wniosku, że wystarczy iloczyn liczby Fibonacciego i jakiejś duzej wartości, zmniejszanej ze wzrostem długości liczby. A potem okazało się, że i liczby Fibonacciego nie są konieczne.
Powstał nowy przegląd zupełny: liczbę n aproksymujemy iloczynami a*b+r, w którym a rośnie od 3 po kolejnych liczbach nieparzystych, zaś r jest jak najmniejszą resztą.Zapis

n = 3*(n/3) + (n%3) = a*b+r

to początek. O ile należy teraz zmniejszyć b, by uzyskać jak najlepsze oszacowanie dla zwiększonego a? Z pomocą przychodzi równanie (znalezione gdy 'rozprasowywałem' wartości cyfr Fibonacciego):
2(b-k) = ak ,
skąd
k = 2b/(a+2) ,
o którą zmniejszam b. Reszta powstająca przy znajdowaniu k wpływa na odległość iloczynu od n. Właściwie, możemy od razu odjąć tę wartość b-k otrzymując
b = ab/(a+2) .
Doświadczenie mówi mi, że znów możemy użyć konwersji, by uniknąć zarówno dzielenia, jak i mnożenia, gdyż przekształcenia wydają się parować. Ale tak nie jest, wzmacniają swoje działanie na liczbę. Mamy po prostu nieco zmodyfikowane współczynniki, zmienione podwojoną cyfrą poprzedzającą.

I znów mamy przegląd zupełny trójek (a,b,r), gdzie n = a*b+r.
(a,b,r) = (m, n/m, n%m), gdzie n = m*(n/m) + (n%m) . 
Dzielniki uzyskamy gdy r=0. Kończymy gdy a przekroczy b. Wartość a rośnie liniowo, wartość b jest tłumiona jak przy odwrotnej proporcjonalności.

 Praktycznie: nieco większa liczba;
a = [179, 253, 134, 259, 181, 270, 41, 172, 277, 83] _ {311}
mnożone przez 309 z resztą +26, czyli n = 309*a+26.
Odejmujemy podwojoną cyfrę poprzednią (równoważne mnożeniu przez 311/313):
a'=[179, -105, -372, -9, -337, -92, -499, 90, -67, -471]
oraz modyfikujemy resztę podwojoną cyfrą najmniej znaczącą r = 26-2*83 = -140.
Możemy poprawić (przenosząc 311 jako jedynkę do cyfry bardziej znaczącej), w szczególności cyfrą najmniej znaczącą staje się -472[+311], zaś reszta uzyskuje wartość -140+311 = 171. Konwertujemy a' na system 313 uzyskując
n = 311 * [168, 201, 77, 172, 61, 137, 256, 193, 123, 56]_{313} + 171
I tak dalej aż reszta będzie 0 (dzielniki), lub liczby się zrównają  a <= n/a (pierwsza).

Widać zmniejszenie najbardziej znaczącej cyfry a mimo zachowania stałej wartości n.

liczby jako palindromy a rozkład

Każdą liczbę można przedstawić jako palindrom nad jakimś systemem, np. binarnym. Jest to wielomian o współćzynnikach całkowitych, którego współczynniki po odpowiednim przesunięciu są izomorficzne z cyframi tego systemu pozycyjnego.
Jest nieskończenie wiele możliwości zapisu, np.
51 = 5 13 5, bo 5*4+13*2+5*1 = 20+26+5 = 51
albo
51 = 7 8 7, 7*4+8*2+7*1 = 51
ale także
51 = 3 4 4 3

Ta ostatnia postać może mieć zastosowanie w szukaniu rozkładów liczb, gdyż jest iloczynem
a b b a = c d c * e e
a = ce, b=de+ce = (c+d)e.
Okazało się jednak, że podobną postać uzyskuje się nie tylko dla wartości związanych z dzielnikami.

Okazuje się także, że tylko niektóre liczby można przestawić jako (e e), zależy to od postawy systemu, i w binarnym podobnie jak w dziesiętnym liczba (cała) musi mieć dzielnik 3.
Aby szukać dzielnika liczby, mnożymy ją najpierw przez 3, a następnie zapisujemy jako palindrom (równoważne dzieleniu przez 8+4+2+1= 15), zaś trzykrotność reszty leciutko wpływa na współczynniki, np. reszta 1 modyfikuje a=3n/15 do palindromu: 
(a-1) (a+2) (a+2) (a-1)
reszta 2 daje po prostu
a  (a+1)  (a+1) a

To punkt startowy, następnie modyfikacje: a-=2, b+=3 nie zmieniają wartości całości palindromu (a b b a), choć zmieniają wygląd:
51 = 1 7 7 1 = 3 4 4 3 = 5 1 1 5

I teraz przegląd w szukaniu dzielników. Weżmy 3*143, które można zapisać
3*143 = 29 28 28 29
Przeglądając ciągle modyfikujemy różnie zapisane 143, aż natrafimy na:
3*143 = 13 52 52 13
Wszystkie wartości są podzielne przez 13, znaleziony dzielnik. Podobnie jest z
3*143 = 11 55 55 11
czyli  11* (1 5 5 1).
I mamy cechę charakterystyczną dzielników: w palindromie a b b a wartość a dzieli b bez reszty, wtedy dzielnikiem całości jest a.
Jest to najbardziej narzucający się zapis wielokrotności, znany mi z niemal wszystkich systemów o podstawach zależnych od liczb całkowitych.

Myślałem jeszcze nad przypadkiem iloczynu
(a b a) * (c d a) = (ac) (ad+bc) (2ac+bd) (ad+bc) (ac)
w którym jedną wartość traktujemy jako stałą, drugiej modyfikujemy postać, ale jest tu pewien kłopot - należy rozdzielić wartość na sumę sumy czynników i ich iloczynu.

Sto Eratostenesa, pamięć tylko dla jednej wielokrotności liczb pierwszych

Sito Eratostenesa w najczęściej podawanej formie zaczyna się:
weźmy tablicę wszystkich liczb naturalnych począwszy od 2...
a potem skreślane są kolejne wielokrotności znalezionych liczb pierwszych.

A przecież liczb pierwszych jest mniej, dlatego proponuję modyfikację obliczeniową tego sita.
Mamy strukturę [liczba, {dzielnik_iczby} ]. Liczby złożone mają wskazane w zbiorze dzielnik_liczby namiary na liczby pierwsze dzielące daną wartość.
Przechodzimy po liczbach naturalnych jednorazowo (w oryginalnym sicie przy każdej napotknej liczbie pierwszej).
Jeśli dla wartości n taka struktura jeszcze nie występuje, jest liczbą pierwszą. Tworzymy z niej strukturę
  [n+n,{n}],
która wskazuje kolejną wielokrotność n. 
Dla każdej napotkanej liczby złożonej o dzielniku k tworzymy struktury
  [n+k, {k}] 
dla wszystkich możliwych dzielników k.
Użytą podczas przechodzenia strukturę można już skasować. 

W ten sposób podczas przechodzenia po kolejnych liczbach naturalnych mamy zaznaczone wartości złożone istnieniem struktury dla nich, tracimy pamięć tylko na aktualną liczbę oraz najbliższe liczby złożone dla znanych liczb pierwszych. Nie musimy pamiętać pozostałych.

Dodatkowo struktury mogą tworzyć kopiec sortowany po wartości liczba, by mozna było szybciej sprawdzić, czy struktura dla danej wartości istnieje.


Przykład, już dotarliśmy do liczby 10, mającej dwie struktury  z dwu dzielników:
[10, {2,5}]]
w strukturach mamy:
[12, {3}]
[14, {7}]
Tworzymy dwie nowe struktury, dla 2 i 5, jedna doczepia się do utworzonej już 12, druga generuje nową wartość:
[12, {2,3}]
[15, {5}]
i możemy skasować strukturę dla liczby złożonej 10.
Następna wartość to 11, struktura nie istnieje, jest to liczba pierwsza. Tworzymy dla niej strukturę
[22, {11}]
Zaś następna wartość 12 jest znów złożona, jak 10.
I pamiętamy raptem na tym etapie 4 struktury (jedna ma dwa dzielniki) dla liczb pierwszych 2, 3, 5, 7, 11 i wartość aktualną 12...


Podejście można odwrócić,  by szukać jak największej liczby pierwszej mniejszej niż zadana. W tym przypadku można narzucić dodatkowe ograniczenie na powstawanie struktury - dzielnik nie jest większy niż pierwiastek kwadratowy danej liczby, zaś formułą jest [n-k, {k}].

Modyfikacja zmiennej pętli for

Wyczytałem chyba na wazniak.mimuw.edu.pl, że zmiana zmiennej sterującej pętli for świadczy o nieumiejętności programowania.
I tak pętla:
for( int k=0; k<liczba; k++ ) {
   ...
   k++; 
}
może być traktowana jak napisana przez bardzo niedoświadczonego, gdyż można użyć
for( int k=0; k<liczba; k=k+2 ) {
   ...
}

A teraz podam przykład, w którym jednak taka konstrukcja się przydaje.
Mam tablicę do 8 różnych obiektów. Należy ją zainicjować. Obiekty są różne, nie mogą się powtarzać. Ich krotność jest losowa od 1 do 8.
Np. sud szpitalny. Pacjent ma do 8 różnych chorób, które należy zainicjować. Każda choroba ma moc będącą liczbą losową od 1 do 100.
Losujemy chorobę, wstawiamy ją do tablicy, o ile się nie powtarza. Kiedy się powtórzy, powtarzamy losowanie. Ale niedoświadczony lekarz zna zaledwie dwie choroby. Czyli i tak musimy siłowo zmniejszyć krotność chorób z 8 do co najwyżej 2!
Zastosowane rozwiązanie: illnes = tablica chorób, jest ich ILLNESES, pacjent ma wylosowane możliwych k różnych chorób
1. for( int i=0; i<k; i++ ) {
2.   illnes[i] = 1+rand()% (ILLNESES-1); // losowana choroba z puli
3.   for( int j=0; j<i; j++ )
4.      if( illnes[j] == illnes[i] ) {  // choroba juz wystapila
5.         i--;
6.         k--;
7,      }
8.   ... // ustawienie parametrow chorob
9. }
10. for( int i=k; i<8; i++) illnes[i]=-1;  // nie ma dalszych chorob

Warunek w linii 4 sprawdza, czy choroba została już wylosowana, gdy tak, ignoruje ten wybór pozwalając nadpisać powtarzajacą się chorobę, zmniejszając zarazem ich krotność. Nadpisanie to następuje albo w linii 8, albo w 10.

Nie wyobrażam sobie, jak bardzo skomplikowany byłby kod sprawdzania możliwych dostępnych chorób bez tej modyfikacji...

Stała w złożoności przeglądu zupełnego

Przegląd zupełny do wartości pierwiastka sześciennego z rozkładanej liczby odbywa się po wszystkich nieparzystych wartościach. Nawet dalej, ale niekoniecznie do pierwiastka kwadratowego.
Można przyspieszyć przegląd przy małych a, gdyż
niech n = (a*p+b)*p+c.
dla ustalonego a wartość b tworzy funkcję monotoniczną od zmian podstawy p.

Jeśli dla podstawy parzystej mamy sumę a+b bliską p przy ustalonym a (a tak jest blisko dzielnika), zmienia się głównie b, c jest szumem. Zatem wystarczy tylko sprawdzać wartości z różnym a. Tych zaś jest też nie więcej niż pierwiastek sześcienny. Dodatkowo dla postaw bliskich pierwiastkowi sześciennemu a zmienia się o 2, nie o 1. Oszacowanie jest zawyżone.

Zatem stałą złożoności przeglądu zupełnego można związać nie tyle z pierwiastkiem kwadratowym, co sześciennym rozkładanej liczby.
Szczegóły tej ostatniej fazy z małymi a nie są jednak jednoznacznie wyznaczone. Warunek a+b=p nie wskazuje dokłądnie dzielnika, lecz wartość przybliżoną. Należy zastosować drugie kryterium, które działa dla przesuniętej wartości p o 2: naprzemienna suma jest równa zero, ale nie mamy jednak tutaj zbieżności, lecz skok. Zbieżność możemy uzyskać, gdy zapiszemy b oraz c w bardzo specyficznej postaci, zmieniając p z odpowiedniej strony:
a*p^2 + (a+b)*p + (b-c) = n
c dąży do b, a jest ustalone. 


    Jeszcze jeden przebieg konwersji dla gigantycznych a, małych p.
Można spakować wszystkie cyfry większe niż cyfra setek do cyfry setek bez utraty danych. Konwersję o r=2 jest wtedy wygodnie przedstawić: 
ap^2 + bp + c,
gdzie a jest gigantyczne, pozostałe zwykłe cyfry systemu o podstawie p. Przekształcenie rekursywne, najpierw tylko dla a:
a'= a-floor( 2a/(p+2) ), b'=b-remainder(2a/(p+2))
i naprawa, potem powtórzyć jeszcze raz dla wszystkich cyfr.
Wartość z pozycji setek jest szybko tłumiona przy wzroście p.

Kilka spostrzeżeń dotyczących własności podstawa vs dzielniki liczby

Tak podglądam sobie zachowanie liczb podczas konwersji.  Chcę teraz podsumować główne spostrzeżenia.

Jeśli natrafimy na miejsce, gdzie dla podstawy nieparzystej mamy na pozycji jedności zero, mamy dzielnik. Z kolei, gdy dla podstawy parzystej mamy sumę cyfr równą dzielnikowi, albo naprzemienną sumę cyfr równą 0, mamy dzielnik na sąsiedniej pozycji.
Krotność obliczeń jest nie większa niż ta potęga dwójki i = 2^k, gdy i<=sqrt n < 2i.
Zatem przegląd zupełny może biec tylko po liczbach trój- oraz dwycyfrowych. Konwersja o 1. Cyfra setek przyjmuje wtedy jedną z czterech wartości: 0, 1, 2, 3. Małe liczby pierwsze mają silne ślady w tym przedziale.
Znalezienie dzielnika zamiast rozkładu całej liczby, sprowadza się do rozkładu podstaw systemów oraz obliczanie największego wspólnego dzielnika podstawy z cyfrą jedności. Podstawa nieparzysta odsiewa duże liczby, podstawa parzysta (można wyłączyć dwójki) odsiewa mniejsze liczby, m. in. pierwsze. Można zastosować sito modyfikując podstawę systemu, by sprawdzać kandydatów nie więcej niż raz.

Jeśli chcemy zmniejszać krotność sprawdzanych przypadków, dla podstaw parzystych zapis liczby jest w postaci:
[a, b+a, b+r] _p
przy podstawie p jest nieliniowy, ale zachowuje się na tyle gładko, że r jest przedziałami monotoniczne. Dzielnik towarzyszy jednej z dużych zmian wartości r.

I zapraszam na łowy! Dla jakiej podstawy dzielnik jednocyfrowy liczby staje się dwucyfrowy?

Inne spojrzenie na konwersję

Mamy dwa sposoby podejścia do konwersji, rekursywny, który najczęściej stosuję, oraz iteratywny, korzystający pośrednio z wzorów skróconego mnożenia typu (a+kb)^i.
Szukanie rozkładu to dla mnie jest już szukanie systemu, w którym cyfra najmniej znacząca, cyfra jedności jest zerem, albo suma cyfr jest wielokrotnością podstawy systemu. W obu przypadkach zmienia się krotność cyfr zapisu dzielników liczby.
Zapis może zmienić sposób patrzenia, oraz ujawnić nowe możliwości. I tak się stało niedawno.

Skoro liczbę złożoną można przedstawić jako [a, a]_p, to będę odejmował stałą wartość takiej postaci od liczby. Po drobnych kłopotach z zapisem, okazało się, że jest to przekształcenie iteracyjne konwersji.

Najpierw sposób. Mam liczbę w postaci ciągu cyfr w systemie pozycyjnym o podstawie p. Chcę zabrać równowartość cyfry najbardziej znaczącej.
Tworzę wielomian współczynników Newtona mnożonych przez kolejne potęgi dwójki, np.
[1, 12=2*6, 60=4*15, 160=8*20, 240=16*15, 192=32*6, 64]
oraz w liczbie n za pomocą przeniesień nadaję poszczególnym cyfrom wartości większe niż w wielomianie, np.  z liczby n = [5, 0, 5, 2, 3, 1, 7] _p=11 tworzę:
[1, 36, 71, 163, 246, 192, 66]_11
Po odjęciu wielomianu po pozycjach mam wartość o mniejszej krotnosci cyfr (początkowe zero do zignorowania):
[0, 24, 11, 3, 6, 0, 2]
z którą postępujemy analogicznie. Kończymy gdy uzyskamy jedną cyfrę.
Odjęcie wartości wielomianu jest odjęciem wielokrotności potęgi 13. Początkowe cyfry (odejmowane) tworzą zapis cyfr systemu trynastkowego właśnie dzięki wielomianowi (11+2)^6  .

I tak powstał nowy zapis sposóbu konwersji, mający więcej obliczeń niż wersja rekursywna.

Jako wniosek, zauważam, że skoro suma cyfr ma być wielokrotnością podstawy, to dla liczby zapisanej w postaci potęg dwójki w miejscu cyfr poza cyfrą jedności, np. [8, 4, 2, 7]_ 31 nia ma szans na dzielniki bliskie 31, 62, 124 itd. przy podwajaniu podstawy. Bo przy konwersji p*2 suma cyfr maleje. Zaś dla dzielnika ma sięgać podstawy.  Suma cyfr może wzrosnąć tylko podczas przeniesienia jedynki do cyfry mniej znaczącej, tu o połowę podstawy. Stąd dwa przeniesienia, i suma cyfr wzrasta powyżej podstawy systemu (podwojonemu).
Możemy nawet wzmocnić ograniczenie, by było tylko jedno przeniesienie i suma odpowiednio mała, by zigrorować szukanie dzielników w okolicy.
Uwaga - przeniesienia mogą się propagować, jak przy [7, 4, 4, 1]_p = [3, n+p/2, 2, 1]_2p.

Przegląd zupełny w faktoryzacji mogący być stosowany współbieżnie

Łączę ostatnie pomysły, uzyskując działającą metodę rozkładu. Własności powodują, że przegląd zupełny zachowuje się jak współbieżny (wielowątkowy). Dlatego nie podam dokładnego algorytmu, lecz warunki.

Niech i będzie taką potęgą 2, by
2i <= sqrt n < 4i
Dzielników szukamy przeglądem zupełnym po potęgach dwójki 1<k<i w przedziale [2i, 4i). Każda taka potęga, np. k=2^3 wyznacza warstwę, która jest niezależna od pozostałych.
Co więcej, w tym przedziale występuje dokładnie jedna wartość 3*2^k, gdzie k=i/2, dwie wartości 5*2^k, 7*2^k, gdzie k=i/4 i tak dalej. W metodzie chodzimy po tych niezależnych warstwach, komunikując je wątkiem liczb pierwszych.


Opis ogólny metody
Liczba złożona n jest rozłożona na sumę dwu składników. Jeden ze składników stanowi warstwę związaną z nieujemną potęgą 2, czyli k.
n = k*a*p + c.
Sprawdzamy, kiedy p jest liczbą pierwszą, wtedy pytamy, czy reszta c jest też podzielna przez p, c=d*p. W takim przypadku mamy  rozkład:
n = k*a*p + d*p = (k*a+d)*p
Wartość a jest ograniczona bardzo specyficznie, zmniejsza się ze wzrostem p w zakresie swojej warstwy przy stałym k do swojej połowy. Np. dla pewnej wartości przy inicjacji wartości a oraz c są stałe, np:
k * 21 490 565  976 844 * p + 10 378 130 574 991
koniec warstwy następuje, gdy a osiągnie 10 745 282 988 422. Równocześnie p osiąga potęgę 2.
Wartość p jest związana z k w ten sposób, że przy inicjacji jest potęgą 2 oraz p*k=2i, następnie jest zwiększana o 1, przebiega liczby nieparzyste do najbliższej potęgi 2, czyli jest ograniczenie p*k<4i, zaś całość k*a*p oscyluje wokół pierwiastka kwadratowego z n. Oznacza to, że c może przyjmować wartości dowolnego znaku, staramy się, by oscylowało wokół a, gdyż w szczególnym przypadku a=c też możemy natrafić na dzielnik n = k*a*p+a = (k*p+1)*a. Wartości k*p bywają bardzo duże, wprowadzone oscylacje dają nam pewność, że jesteśmy najbliżej potencjalnego dzielnika jak się da przy tym znaku c.

Możemy wykonywać obliczenia niemal równocześnie po warstwach z różnymi k.
W obrębie warstwy myślę stosować sito Eratostenesa oraz kopiec na trzymanie par (liczba, jej dzielnik), posortowany według liczb.

Wątek liczb pierwszych
Wątek ten komunikuje się z dowolną z warstw dla danego k, niszcząc je po wykorzystaniu. 
Jego zadaniem jest wstawienie świeżo znalezionej (przysłanej z jakiejś warstwy) nowej liczby pierwszej do kopców w odpowiednich warstwach, podawanie zakresu minimalnej liczby pierwszej oraz zatrzymanie w przypadku znalezienia dzielnika albo wykrycia, że liczba n jest pierwsza.

Jeśli warstwa przyśle nowo wykrytą liczbę pierwszą q, stosujemy następujacą procedurę, szukamy wątku o największym k, w którym któraś z wartości p jest równa q, oraz dodajemy do kopca parę (q,q). Teraz szukamy warstwy zawierajacej iloczyn 3q, wstawiajac parę (3q, q). To nie musi być wątek z połową k, lecz z czwartą częścią k.
Teraz modyfikujemy wielokrotność q tak, by była nie większa niż p w inicjacji. W tym celu powinniśmy czasem dodać q. Dla wątku wielokrotność ta ma być nieparzysta, dodajemy mu parę ((s+1[+1])*q,q), jedna suma opcjonalnie, dla nieparzystości. Staramy się trzymać wielokrotność s*q za małą do umieszczenia w wątku.
Przykład, q=11:
Pierwsza odpowiednia warstwa powstała z p=8, odkładamy jej (11,11), następna warstwa z wartością nieparzystą to (33,11), a to jest warstwa z p=32. Pamiętamy jednak q=22. Mnożymy to przez 2 i dodajemy 11, uzyskując s*q=55, jest to ta sama warstwa z p=32. Dodajemy 11 uzyskując wartość większą niż 64, zatem warstwie z p=64 dodajemy ponownie 11 dodając do kopca parę (55+22, 11). Znów podwajamy s 2*55=110, ale 110+11 = 121 jest mniejsze niż p=128, to jest nasza nowa wartość s. Warstwie dla p=128 dokładamy element (121+22, 11). I tak dalej.

Jeśli warstwa przekaże, że skończyły się jej elementy, wątek liczb pierwszych podwaja zakres najmniejszej możliwej liczby pierwszej i każe warstwom sprawdzić swoje wartości. Wykorzystaną warstwę kasuje.
Jeśli skończą się elementy ostatniej, najdłuższej warstwy, z k=2, liczba jest pierwsza.

Działania na warstwach przy stałym k
Pierwszym działaniem po inicjacji jest przejscie na p nieparzyste. Wystarczy konwersja o 1: k*a'*(2p)+c' = k*a*(2p+1)+c. Uzyskamy  p = 1+2^t dla pewnego t. Zapamiętujemy całe ostatnio obrabiane wyrażenie.

Wartość p jest albo liczbą pierwszą, albo złożoną. Sprawdzamy, czy ta wartość jest na szczycie kopca. Należy to powtarzać, gdyz jedna wartość może wystąpić tyle razy, ile ma różnych dzielników. Jeśli jej nie ma, lub jest to para (p,p), mamy duże szanse przypuszczać, że p jest liczbą pierwszą. Zwiększamy ją do najbliższej potęgi 2, z której wyciągamy pierwiastek kwadratowy i porównujemy z zakresem minimalnej liczby pierwszej wątku liczb pierwszych. I tak jeśli zakresem tym jest 8, a my mamy wartość p nieparzystą mniejszą niż 64, mamy do czynienia z liczbą pierwszą. Innym sposobem jest spierwiastkowanie, ale nie  znajdujemy liczb pierwszych w porządku liniowym. Ta wartość wtedy czeka, a my możemy spokojnie zająć się kolejną, korzystając z kopii jej współczynników. 

Jeśli wartość jest poza zakresem minimalnej liczby pierwszej, musimy poczekać, aż wątek liczb pierwszych go zwiększy. Wtedy moze okazać się, że liczba jest pierwsza, wtedy zwracamy ją wątkowi liczb pierwszych jako liczbę pierwszą.
Zarazem uruchamiamy procedurę sprawdzajacą, czy wartość c jest wielokrotnoscią liczby p. Jeżeli trzymam c w systemie o podstawie p, jest to po prostu porównanie najmniej znaczącej cyfry c z p w warstwie o największym k. W pozostałych warstwach należy sprawdzać podzielność bardziej standardowo. 

Ale wąŧek liczb pierwszych może wprowadzić nową wartość większą niż aktualnie obsługiwana. Oznacza to, że oczekująca wartość m jest złożona, znamy jej dzielnik, więc wprowadzamy ją do obróbki jak liczbę złożoną.
Liczbę złożoną m o znanych dzielnikach rozkładamy. Może wtedy pojawić się dodatkowy dzielnik, który jest przesyłany jako nowy wątkowi liczb pierwszych.
Odkładamy na kopiec kolejne liczby podzielne przez q, (m-2q, q).


Mamy liczbę pierwszą p oraz przyrost w, jaki nas dzieli od ostatnio obrabianego wyrażenia p'. Liczba w jest parzystą.
Przystępujemy do konwersji:
k*a'*(p-w)+c' = k*a*p+c
gdzie najczęściej w=2. W później jednak możemy mieć często przyrost będący różnicą między kolejnymi liczbami pierwszymi.
Najpierw należy obliczyć przyrosty Delta a oraz Delta c
k*a*w = k* Delta a * p + Delta c
a następnie odjąć te przyrosty od zapamiętanego wyrażenia. Z Delta a nie ma kłopotu, jest to zwykłe a'*w z wyzerowaną cyfrę najmniej znaczącą.
Jednak Delta c wymaga nieco zachodu. Jeśli a'<c', odejmiemy iloczyn k oraz cyfry najmniej znaczącej a'*w od c'. Jeśli jednak a'>c', skorzystamy z własności systemu niedziesiątkowego, oraz dodamy dodatkowo k*p, zabierając jedynkę z a. W ten sposób zamiast zmniejszać c', zwiększamy je.

Przykłady
Możemy liczyć dziesiętnie, jak w tym przykładzie z p'=17 na p=19:
k*a'*(p-2) + c' = 
n = 4 398 046 511 104  *  20 226 415 037 029  *  17  + 58 756 642 197 135
przyrosty:
4 398 046 511 104  *  20 226 415 037 029  * 2 =
4 398 046 511 104  *  (2 129 096  319 686 * 19 + 5) =
4 398 046 511 104  *  2 129 096  319 686 * 19 + 105 553 116 266 496 =
k * Delta a * p + Delta c
oraz ich odejmowanie od a', c', gdyż a'<c' (20... < 58...):
20 226 415 037 029  - 2 129 096  319 686 = 18 097 318 717 343
58 756 642 197 135 - 105 553 116 266 496 = - 46 796  474 069  361
nowa postać
n = 4 398 046 511 104  *  18 097 318 717 343  *  19  - 46 796  474 069  361
stąd wyznaczamy, że 19 nie dzieli n, bo 46 796  474 069  361 = 1 (mod 19)

Jednak wolę systemy niedziesiątkowe, gdyż dla większych wartości mamy lepiej widoczne działania (separator 'cyfr' to przecinek, dopuszczam 'ujemne'). Najpierw zapisuję wszystkie współczynniki przy podstawie p (3 dodatkowe proste konwersje:
k * a' * (p-2) + c' = 
n = 1022, 2056, 1018  *  311, 3962, 172, 1680  * 4097 +  874, 1430, 3799, 918
przyrosty (wartość 1022, 2056, 1018 to duża potega 2): 
1022, 2056, 1018  *  (311, 3962, 172, 1680 * 2) =
1022, 2056, 1018  *  622, 7924, 344  *  1,0  +  1022, 2056, 1018 * 3360 =
1022, 2056, 1018  *  622, 7924, 344  *  1,0  +  838, 643, 2179, 1914
nowa postać (znów a'<c'):
n = 1022, 2056, 1018  *  311, 3340,  -7752, 1336 * 1, 0  +  36, 787, 1620, -996
oraz sprawdzamy podzielność -996 = 3103 (mod 4099) z 4099. Od razu widać, że liczba n jest niepodzielna przez liczbę pierwszą 4099.
Ale przechodząc na 4101 mamy a'>c', czyli oprócz odejmowania wyznaczonych przyrostów dodamy przekonwertowaną na system 4101 liczbę 1022, 2056, 1018 z systemu o podstawie 4099 pomnożoną przez 4101, by zwiększyć c.

już dla p=4099 działamy na liczbach co najwyżej czterocyfrowych, a dalej mamy jeszcze mniej cyfr, przez co mamy coraz mniej działań. I konwersje są coraz prostsze. Najwięcej przypadków jest dla małych k, najwiecej obliczeń dla dużych.


Inne własności, badajac 65 = 5 * 13 i znając zakres od warstwy k=2^45 (czyli liczbę pierwszą 3 i minimalny zakres 4) wnioskujemy, że 13 < 4^2 też jest pierwsza. Wartość 13 jest jedną z ostatnich sprawdzanych w swojej warstwie (9, 11, 13, 15).

Można przechodzić szybciej, np. z p'=263 na 267, szukając przyrostów iloczynem k*a'*4.

Przebieg.
Inicjacja, mamy w każdej warstwie wyrażenie na n, w którym p jest postaci p=1+2^t dla odpowiedniego t, czyli: 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025,...
kopce puste. Liczymy po jednym elemencie każdej warstwy.

Sprawdzamy liczbę pierwszą 3, do kopca każdej warstwy odkładamy najmniejszą parę liczby podzielnej przez 3 większą niż potęga 2^t. Kasujemy pierwszą warstwę.
Wartości 9, 33, 129, 513 są w kopcu. Liczby mniejsze niż 4^2 nie będące w kopcach są pierwsze. Wartość złożona 15 jeszcze nie jest w kopcu, ale pojawi się tam podczas obsługi wątku p=9.

Wartość 5 nie jest w kopcu, jest pierwsza, kopce powiększają się o tę wartość.

Wartość 9, byłaby zignorowana, ale mamy wyrażenie dla niej z inicjacji. Dalej w takim przypadku tylko zwiększamy przyrost w o 2. Ale do kopca odkładamy wartość (9+6,3) czyli (15,3). Teraz wszystkie liczby złożone nieparzyste mniejsze niz 16 są w kopcach.

Wartości 17, 257 czekają, na tym etapie nie wiemy, czy są pierwsze. Sprawdzamy, czy ich potrojenie mieści się w ograniczeniu warstwy i ewentualnie odkładamy do kopca.

Wartości 33=3*11, 65=5*13 wyznaczają nowe liczby pierwsze. Wartość 513 = 3^3*57 czeka na możliwość stwierdzenia, czy 57 jest pierwsza (wymaga skasowania warstwy z p=4). Sprawdzana podzielność c przez 11, 13.
Podobnie 1025.

Nowy przebieg po warstwach.

Wartość 5+2=7 nie jest w kopcu, jest pierwsza. Warstwa kasowana, zakres minimalnej liczby pierwszej zwiększa się do 8^2=64.

Wartość 9+2=11 pierwsza, bo w kopcu jest (11,11). Podzielność jest sprawdzana w wartwie 33, tu można zignorować.

Wartość 17+2 = 19. Wynik z warstwy 7 wskazuje, że 17 jest pierwsza. Ale rozpatrywana 19 też jest pierwsza. Odkładamy ich nieparzyste wielokrotnosci do kopców w obrębie ograniczeń warstwy, czyli w tej warstwie już nic.

Wartość 35 = 5*7 ignorujemy tylko wstawiając do kopca pary (45,5), (49,7), Są w tej warstwie. Mamy w kopcu dwie pary (45,3) oraz (45,5). Może zrobić listę (45, [3,5])? 

Wartość 67 jest pierwsza. Wiadomo, co... Dla kolejnych dwu wartości 131,  259 podobnie.

Wartość 515. Teraz już wiemy, co z 57 z 513 (pierwsza). Testujemy podzielność. W przypadku liczby złożonej czekamy na dalsze informacje. Obrabiamy 515.

... I tak dalej...

Faktoryzacja z podstawy systemu, kolejna własność

Przyglądając się uzyskanym wartościom widzę, że nie muszę się ograniczać do nieujemnych b, c w niezmienniku
(d+b)*d+c = n
Liczba n jest wtedy dwucyfrowa, ale dzięki ujemnemu b jest zapisywana jako trójcyfrowa.
Przesunięcie to pozwala wyeliminować obliczanie kolejnych pierwiastków z liczby rozkładanej. Wystarczy jeden, zaś rozpatrywany przedział to potęga dwójki
2^k <= sqrt n < 3*2^k
W tym przedziale mozemy posługiwać się potęgami dwójki, by wyznaczyć tablicę małych liczb pierwszych, by je wyeliminować.Po prostu przechodzimy po wartościach a*2^j, gdzie j>=k/2 szukając liczb pierwszych jak w sicie Eratostenesa. Liczby te łączymy z ich wielokrotnościami jak najbliższymi skrajnej potęgi 2^k, a potem przegląd zupełny.

Reszta jak poprzednio. Znając dzielniki d mniejsze niż sqrt d, wyłączamy je uzyskując 1 lub liczbę pierwszą. Tą prównujemy z c. Jeśli wspólny dzielnik c i którejś z liczb pierwszych jest większy niż 1, jest to dzielnik liczby rozkładanej.