22 października 2026

Inne podejście rozkładu sitem Eratostenesa, zmniejszenie zapotrzebowania na pamięć

W wielu algorytmach poświęconych situ Eratostenesa zakłada się tablicę zawierającą kolejbe liczby naturalne, do rozkładanej włącznie. Uważam do za duży narzut. Za duży.

Przy podejściu zaczynającym od liczby rozkładanej do coraz mniejszych zakończymy działanie sita przy liczbie pierwszej będącej dzielnikiem, a mniejsze są tylko kolejne wielokrotności liczb pierwszych mniejszych niż dzielnik. Podstawową wadą jest nieznajomość tych liczb pierwszych. Można je sprawdzać na co najmniej dwa sposoby:
- mając już rozkład cząstkowy jakiejś liczby mniejszej niż n, obliczamy jej resztę z dzielenia przez kolejną wartość, co sprowadza się do algorytmu, w którym wyrażenie algebraiczne generuje reszty przez kolejne liczby. Asymptotycznie operujemy na wartościach z zakresu [d, d^2), gdzie d jest stale rosnącą wartością, zaś obliczenia są wykonywane modulo d. No, może jeszcze wystąpić stała mniejsza niż d, która doczepiona do któregokolwiek z czynników zwiększa ją powyżej d^2.
- przy kolejnej wartości d sprawdzamy, czy jest pierwsza, a wtedy liczymy resztę d%p jak przy dzieleniu przez kolejne wartości p jak w standardowym trial division. 

W obu przypadkach znalezione wartości pierwsze d propagują się do coraz mniejszych wartości: n-r, n-r-d, n-r-2*d, itd. dla n = k*d+r, 0<=r<d. Warto też dołączać potęgi liczb pierwszych, a do każdej kolejnej wartości n-d stosujemy trial division przez zapamiętane i przypisane liczby pierwsze. Tych dzieleń jest skonczona krotność, i często wiemy z góry, że wielokrotność jest daną potęgą liczby pierwszej, np. sześcianem. Nie trzeba wtedy dzielić przezeń dalej, kiedy w sicie napotkana została jej potęga czwarta lub większa. I od pewnego momentu kolejne większe liczby pierwsze same zaczynają się ujawniać i przedstawiać.


I teraz modyfikacje, choć dalej z tą luką dotyczącą nieznajomości małych liczb pierwszych. Jeśli ich odległość pierwszego wystąpienia jest mniejsza niż d, możemy je zignorować, na pewno nie są dzielnikami. Ale nie daje to pewności, że przy kolejnym ich wystąpieniu je rozpoznamy. Koniecznie należy je wyłapać zanim wystąpią drugi raz przy rozkładzie, albo skakać na ogromne odległości przy ich rozpoznawaniu, co grozi pominięciem dzielnika blisko n -- kryterium podzielności staje się: dystans jest wielokrotnością liczby pierwszej.

Zamiast zapamiętywania kolejnych wartości, zapamiętujemy odległość (dystans d) od liczby rozkładanej. A to można przekształcić w listę par (p,d[]), gdzie p jest liczbą pierwszą, a na liście rosnącej d zamieszczane są odległości występowania kolejnych potęg k>0 od liczby.  I tak liczba n-d z pozycji d[2] zawiera jako dzielnik kwadrat liczby p (liczenie od 1). Jeśli nie istnieje d[3], należy sprawdzać możliwość wystąpienia trzeciego dzielnika p, ale jeśli istnieje, to wystarczy jedno mnożenie/dzielenie przez p^2 podczas trial division tej wartości. 

Przebieg sita od n:
- początek: wyłączamy potęgę 2 uzyskując nieparzyste n, na stóg para (2, [n-3]), d=2
- pętla, zwiększamy d++;
- szukamy w stogu liczb pierwszych p par (p,d[1]) o tym dystansie (p,d), jeśli nie znajdziemy, bardzo mozliwe, że n-d jest pierwsza, na pewno ma dzielnik większy niż d; jeśli istnieje, przesuwamy się po liście do największego dzielnika będącego potęgą p;
jeśli istnieje liczba pierwsza równa d, to d jest dzielnikiem n;
- wykonujemy mnożenia albo dzielenia rozpoznanych dzielników w poszukiwaniu kolejnych wartości, które są albo równe n-d (mnożenie, przy dzieleniu 1), albo liczbami złożonymi o dzielnikach większych niż d, albo liczbami pierwszymi; ostatni przypadek jest dla wartości a zakresu 1<a<d^2 przy dzieleniu;
- odkładamy na stóg pary (p, [d+p, d+p^2, ..., d+p^k]), gdzie p^k są potęgami liczby pierwszej p, dla wszystkich dzielników n-d; sortowanie po dystansie d[1] =d+p;
- usunięcie luki związanej z nieznajomością liczb pierwszych: sprawdzenie, czy d jest pierwsza, jeśli tak, odkładamy nową parę (d,d+r) na stóg, gdzie r wyznacza się np. jako (d-(n%d))+d, chodzi o to, by d|(n-d-r); w tym kroku też możemy uzyskać, że d jest dzielnikiem n;
- kryterium stopu d*d>n, lub powrót na początek pętli. 

Takie tablice mają interpretacje np. dystans d=259, liczba pierwsza 7:
(7, [264, 264, 411, 2469])
7 | (n-264), 7^2 | (n-264), 7^3 | (n-411), zaś n-2469 ma jako dzielnik 7^4 z możliwością wysŧąpienia kolejnych potęg 7. 

 

Pamiętamy tylko liczby pierwsze, co znacząco zmniejsza zapotrzebowanie na pamięć, o ile poradzimy sobie ze wspomnianą luką. Sprawdzone wartości n-d można spokojnie zapominać, modyfikując kolejne odległości.
Dodatkowo, odległości są znacznie mniejsze niż wartości n-d, co ma kolejne znaczenie dla większych wartości.


04 października 2026

Problem Goldbacha, spostrzeżenia

Goldbach pyta Eulera w liście: Czy każda liczba parzysta jest sumą dwu liczb pierwszych? 

Euler nie potrafił odpowiedzieć. Problem trafił na sumę problemów do rozwiązania. 

A oto kilka moich spostrzeżeń: suma liczb pierwszych większych niż 2 jest zawsze parzysta. A czy liczba parzysta jest sumą liczb pierwszych? Wiele prób, choć już pojawił się dowód słabszej wersji, wspomniany w Wikipedii pod hasłem 'hipoteza Goldbacha'. 

Każdą liczbę nieparzystą, w tym liczby pierwsze różne od 2 także, można przedstawić jako różnicę kolejnych kwadratów:
f(p) = a*a - (a-1)*(a-1)
I tak f(1) = 1*1 - 0*0 = 1 (dla Golbacha -- u niego 1 była liczbą pierwszą)
f(2) = 2*2 - 1*1 = 4-1 = 3
f(3) = 3*3 - 2*2 = 5
f(4) = 4*4 - 3*3 = 7
f(5) = 5*5 - 4*4 = 9
i tak dalej... 

Dodajmy do siebie:
f(a) + f(b) = a*a - (a-1)*(a-1) + b*b - (b-1)*(b-1) =
(a-b+1)*(a+b-1) + (b-a+1)*(a+b-1) =
2*(a+b-1)
Parzysta... Według oczekiwań, lecz jest postać tej liczby parzystej.

Poszukajmy okresu, czyli orbit jednego dzielnika:
jeśli k dzieli f(a), to k dzieli f(a+k):
f(a+k) + f(a) = 2*(a+k+a-1) \equiv 2*(2*a-1) = f(a)+f(a) \equiv 0 modulo k. 

Kiedy f(a) jest liczbą pierwszą; może lepiej spytać: kiedy f(a) NIE JEST liczbą pierwszą:
dla 3 = f(2): f(5) = 9, f(8) = 15, f(11) = 21, ...
Pierwsza wartość jest, powstała orbita f(5+3N) to liczby złożone.
Dla 5 = f(3): f(8), f(13), f(18), ogółem f(8+5N) to liczby złożone.
Szybko: f(4+7+7N) = f(11+7N) to liczby złożone..., kwadrat 7 to f(25).
Podobnie dla kolejnych liczb pierwszych, kwadrat jakiejś liczby generuje orbitę liczb złożonych, nawet z kilkoma wartościami wcześniej, te dodatkowo wpadają w orbitę mniejszej liczby pierwszej. 

Niezwykle przypomina to sito Eratostenesa, chociaż mamy więcej liczb pierwszych niż w sicie, zatem własności sita Eratostanesa są ograniczeniem górnym. Liczb pierwszych wyznaczonych przez f() jest nieskończenie wiele, nawet więcej niż oszacowanie górne n/(lg n), ale w granicy... Interesują nas liczby spoza orbit, czyli pierwsze.

Przejdżmy do pytania Golbacha w mocnej wersji. Mam liczbę parzystą 2n, czy jest ona sumą dwu liczb pierwszych?
Wystarczy dopasować takie a oraz b, by a+b=n+1 oraz by ani f(a), ani f(b) nie znalazło się na żadnej z orbit wyznaczonych przez liczby pierwsze przez f(). Orbity są na tyle 'dziurawe', że raczej znajdzie się miejsce na parkę, a może nawet więcej możliwości. 

Jakie jest prawdopodobieństwo, że jedna z ostatnich wartości, np. n-1, jest liczbą pierwszą? Oszacujmy prawdopodobieństwo, że nie jest pierwszą, że jest liczbą złożoną.
Po pierwsze, przesunięcie dla liczby pierwszej p. Orbity zaczynają się od pozycji f^{-1}(p)+p, czyli około p/2+p = 3/2 p. W szukaniu prawdopodobieństwa możemy pominąć 1/3 największych liczb pierwszych mniejszych niż n.
Po drugie, liczby pierwsze a, b są względnie pierwsze, oraz sumę prawdopodobieństw z ich orbit można łatwo wyznaczyć: 1/a + 1/b - 1/(a*b) = (b+a-1)/(a*b) dla wartości podzielnych przez obie. Dotyczy to także wartości względnie pierwszych. Orbity od liczb złożonych zawierają się w orbitach generowanych przez dzielniki liczb -- są już uwzględnione. Tak począwszy od k=8 mamy 1/3 + 1/5 - 1/15 = 7/15, że liczba n-1 jest podzielna przez 3 lub 5. Dołączając orbitę z 7 mamy 7/15 + 1/7 - 1/105 = 63/105. Dołączymy orbitę z kolejnej liczby pierwszej, i znowu... i kolejną...
Ciąg prawdopodobieństw uzyskiwany z kolejnych orbit jest rosnący, lecz ograniczony, bo liczb pierwszych w granicy jest nieskończenie wiele, i musi się dla nich znaleźć pozycja. Prawdopodobieństwo trafienia w liczbę pierwszą pozostaje dodatnie.

Suma odwrotności liczb pierwszych jest szeregiem rozbieżnym (Delta wrzesień 1999), chociaż tu mamy ograniczenie wielkości składników do mniej niż 2/3 n oraz dodatkowe zmniejszanie. Zatem wszystko się może zdarzyć... I dlatego problem stawia opór.

Np. 2n = 156: a+b=78+1, suma liczb pierwszych 156 = 17+139 czyli f(9)+f(70), zaś f(a) dla a<9 niemal zawsze wpada we wspomniane orbity. Wyjątkowe jest 13: dzielnik 156, które mi namieszało w poszukiwaniach sugerując siebie.