Po iteracjach, czyli drogi ku pierwszości

„Wszystko jest liczbą” – tę przypisywaną Pitagorasowi maksymę można rozwinąć: „wszystko jest liczbą pierwszą”. Takie uzupełnienie ma sens, bo każda liczba albo jest liczbą pierwszą, albo nietrudno ją do liczb pierwszych sprowadzić na co najmniej dwa sposoby: rozkładając na czynniki pierwsze lub zapisując w postaci sumy dwóch lub trzech liczb pierwszych. Rozkład na czynniki wiąże się z podstawowym twierdzeniem arytmetyki, dotyczącym jednoznaczności takiego rozkładu, zaś sumy dotyczy pośrednio hipoteza Goldbacha (każda liczba parzysta większa od 2 jest sumą dwóch liczb pierwszych).

Oto kilka przykładów iloczynów i sum dla pięciu kolejnych liczb naturalnych:

113 – liczba pierwsza

114 = 2×3×19 = 53+61

115 = 5×23 = 2+113 = 3+5+107

116 = 2×2×29 = 43+73

117 = 3×3×13 = 29+41+47

Sprowadzanie liczb złożonych do liczb pierwszych jest nadawaniem im formy najprostszej w tym sensie, że nierozkładalnej na czynniki pierwsze. Dwie powyższe metody takiego przekształcania są najbardziej znane, ale nie jedyne. W teorii liczb, a ściślej na jej styku z matematyką rekreacyjną, znanych jest jeszcze kilka innych modyfikacji opartych na różnych zależnościach. Przyjrzymy się kilku takim, z którymi wiążą się jakieś wyróżniające je, bo ciekawe i wymagające ruszania głową, zagadnienia.

Wybieramy dowolną liczbę złożoną i dodajemy do niej sumę jej cyfr. Z otrzymaną sumą i z każdą następną postępujemy tak samo dopóty, dopóki jako suma nie pojawi się liczba pierwsza. Czy taka iteracja zawsze zakończy się happy endem?

Łatwo zauważyć, że nie: zaczynając od wielokrotności trzech, nigdy nie dotrzemy do liczby pierwszej, bo w kolejnych sumach podzielność przez 3 będzie zachowana. Jest na to sposób: jeśli zamiast dodawania do jakiejś kolejnej liczby sumy jej cyfr dodamy iloczyn cyfr i w rezultacie otrzymamy liczbę pierwszą, to jedno takie działanie, kończące iterację, jest dopuszczalne. Wydaje się, że finalna suma z iloczynem gwarantuje sprowadzenie do liczby pierwszej każdej wielokrotności trzech (a bez iloczynu każdej innej liczby złożonej). Wiele iteracji jest jednak zaskakująco długich. Na przykład od 18 i 21 do celu jest bardzo blisko:

18 → (+9) → 27 → (+14) → 41

21 → (+2) → 23

ale dla 24 potrzebnych jest aż 106 kroków, aby sięgnąć liczby pierwszej (1297):

24 → (+6) → 30 → (+3) → 33 → … → 1266 → (+15) → 1281 → (+16) → 1297

Ogólnie, konieczne jest pojawienie się w przedostatnim kroku takiej wielokrotności trzech, która po dodaniu iloczynu tworzących ją cyfr da liczbę pierwszą. Takich wielokrotności jest jednak niewiele – na przykład w zakresie do 5000 zaledwie 27: 21, 27, 81, 441, 471, 741, 1257, 1281, 1287, 1521, 1527, 1581, 1587, 1857, 2151, 2277, 2421, 2427, 2511, 2577, 2721, 2787, 4227, 4521, 4551, 4851, 4887, … . Czy każda iteracja wielokrotności trzech „wpada” w ten ciąg? Pewności nie ma.

Prostsza iteracja, wiodąca ku liczbom pierwszym, zaczyna się od dodania do startowej liczby złożonej dowolnej znajdującej się w niej cyfry (liczby jednocyfrowej) i powtarzaniu takiej czynności dla kolejnych liczb-sum aż do utworzenia liczby pierwszej. Jeśli więc zaczniemy od 24, to najszybciej, bo w czterech krokach, dotrzemy do liczby pierwszej 37:

24 → (+2) → 26 → (+6) → 32 → (+2) → 34 → (+3) → 37

Większość iteracji, nawet zaczynających się od bardzo dużych liczb, można zakończyć po co najwyżej kilku krokach. Jednak w miarę jak liczby rosną, pojawiają się wśród nich, niczym rodzynki w cieście, okazy, wymagające coraz dłuższych iteracji, co wynika z faktu coraz rzadszego występowania liczb pierwszych w miarę oddalania się od początku osi liczbowej, czyli od zera.

Istotne są dwa pytania: czy takim sposobem iteracji uda się dotrzeć do każdej liczby pierwszej oraz czy każda iteracja osiągnie liczbę pierwszą?

Oczywistym jest, że do 3, 5 i 7 dotrzeć nie sposób, bo w tych przypadkach nie ma od czego zacząć. Osiągalne jest dopiero 11: 10 → (+1) → 11.

W przypadku drugiego pytania nietrudno dowieść, że każda iteracja dotrze do liczby pierwszej, choć niekoniecznie w minimalnej liczbie kroków. Wystarczy zauważyć, że jeśli iteracja nie zakończy się wcześniej, to doprowadzi do co najmniej 3-cyfrowej liczby n, zaczynającej się od 2-cyfrowego fragmentu 10… Odtąd, dodając w kolejnych krokach jedynkę, na pewno dotrzemy do liczby pierwszej, zanim początkowe 1 zastąpi 2, bowiem skądinąd wiadomo, że między n a (3/2)n (dla n>3) musi znajdować się przynajmniej jedna liczba pierwsza .

Wydaje się, że najciekawszym z zagadnień, dotyczących wędrówki od liczb złożonych do pierwszych, jest docieranie do celu na różne sposoby za pośrednictwem… czynników pierwszych i – tak jak poprzednio – w procesie iteracji. Rozkład liczby złożonej na czynniki pierwsze zawsze stanowi początek, a dalej bywa różnie.

Najprościej dodać do siebie wszystkie czynniki i otrzymaną sumę (jeśli nie jest liczbą pierwszą) ponownie rozłożyć na czynniki pierwsze, po czym znowu obliczyć ich sumę itd. Taka iteracja kontynuowana jest, dopóki to możliwe, czyli do pojawienia się jako sumy liczby pierwszej. Nierzadko już pierwsza suma jest liczbą pierwszą, zaś warunkiem koniecznym, aby tak było, jest nieparzysta liczba nieparzystych czynników pierwszych. Na przykład:

6 = 2×3 → 5

385 = 5×7×11 → 23

420 = 2×2×3×5×7 → 19

1302 = 2×3×7×31 → 43

Nie jest to oczywiście warunek dostateczny, bo na przykład 20 = 2×2×5 → 9 lub 105 = 3×5×7 → 15. Nietrudno też dowieść, że ciąg liczb złożonych – których efektem rozkładu na czynniki pierwsze, a następnie zsumowania tych czynników jest liczba pierwsza – to ciąg nieskończony. Jeśli bowiem liczba złożona z₁=2w, znajdująca się w ciągu, jest różnicą dwu liczb pierwszych p₁ i p₂ (p₁>p₂>2), czyli p₁–p₂=2w, to liczba 2^w×p₂=z₂>z₁ także tkwi w ciągu, ponieważ 2w+p₂=p₁ jest liczbą pierwszą.

Na przykład:

z₁=2w=10=23–13; w=5,

2⁵×13=416=z₂ (liczba w ciągu)

2×5+13=23 (suma czynników pierwszych liczby z₂ – liczba pierwsza).

Ciąg liczb złożonych – taki, że dotarcie od każdej sumą jej czynników pierwszych do liczby pierwszej wymaga przynajmniej dwóch kroków iteracji – poprzedza niespodzianka: 4 to jedyna liczba odporna na iterację, czyli niezmienna, bo równa sumie swoich czynników pierwszych: 2+2=4 (to jakby odpowiednik liczby doskonałej, ale z pominięciem dzielnika właściwego równego 1). Efekty iteracji 21 następnych liczb złożonych (z) podane są w tabeli 1 – druga kolumna zawiera liczby pierwsze (p) kończące iterację, a trzecia liczbę kroków iteracji (k). W tabeli są widoczne cechy charakterystyczne tego procesu: zdecydowana dominacja p równych 5 i 7 z „wyskokami” przy k=1 oraz bardzo wolny, skokowy wzrost k; k=5 debiutuje przy z=62, k=10 dla z=9314, a k=15 pojawia się dopiero przy ponad 14-milionowym z. Zagadką pozostaje, czy w ciągu liczb p, dla których k>1, występują wszystkie liczby pierwsze większe od 3. Najmniejszą podejrzaną o nieobecność jest p=479 (przy k=1 liczba p=479 jest oczywiście obecna, np. gdy z = 16345 = 5×7×467 → 479).

Teoretycznie nieco dłuższa droga do liczb pierwszych przez czynniki pierwsze polega na sumowaniu w kolejnych krokach nie tylko samych czynników, ale wraz z nimi także rozkładanej liczby. Wówczas już zaczynając od czwórki, dociera się w trzech krokach do 23: 4 = 2×2 → 8 = 2×2×2 → 14 = 2×7 → 23. Finały (p) i liczby kroków (k) iteracji 21 następnych liczb złożonych (z) znajdują się w tabeli 2. Istotna różnica między ciągami, których początkowe fragmenty są w kolumnach tabel 1 i 2, dotyczy liczb p: ciąg zapoczątkowany w tabeli 1 zawiera prawdopodobnie wszystkie liczby pierwsze większe od 3, natomiast ten zainicjowany w tabeli 2 przeciwnie – są w nim tylko „wybrańcy”.

Liczbami pierwszymi tworzonymi w procesie iteracji, którym poświęcono najwięcej miejsca w publikacjach matematycznych – nie tylko związanych z matematyką rekreacyjną – są tzw. liczby pierwsze domowe albo rodzinne. Iteracja w tym przypadku także zawiera rozkład na czynniki pierwsze, ale poza tym istotny jest inny proces – łączenie zwane w matematyce konkatenacją. Chodzi o to, że czynniki pierwsze, otrzymane w wyniku rozkładu liczby złożonej, są „sklejane” w kolejności od najmniejszego do największego, tworząc w ten sposób większą liczbę, która poddawana jest ponownie dwu takim samym zabiegom (rozkład na czynniki pierwsze plus konkatenacja „według wzrostu”) i proces ten jest kontynuowany aż do utworzenia liczby pierwszej. Oto przykład zaczynającego się od czternastki 5-etapowego procesu: 14 = 2×7 → 27 = 3×3×3 → 333 = 3×3×37 → 3337 = 47×71 → 4771 = 13×367 → 13 367. Końcowa liczba pierwsza, czyli właśnie domowa (13367), zwykle zwana jest „matką”, a złożona początkowa (15) – „dzieckiem”. Starszymi dziećmi (większe liczby, choć pojawiające się później), są także wszystkie liczby złożone w kolejnych etapach iteracji (27, 333, 3337, 4771) – stąd podział na dzieci pierworodne D₀ i powijane w następnych etapach – D₁, D₂, D₃, … – wszystkie one tworzą „rodzeństwo”. Między innymi wspomniana wielodzietność zadecydowała o zainteresowaniu liczbami domowymi, co wiąże się z algorytmami i techniką obliczeniową oraz z aspektem edukacyjnym, bowiem analizowanie liczb domowych stanowi prosty model badań matematycznych, które sprowadzają się do stawiania pytań i szukania odpowiedzi. W tym przypadku pojawiają się m.in. następujące pytania:

1. Czy każda liczba-dziecko ma liczbę-matkę?

2. Jakie warunki musi spełniać liczba pierwsza, aby była matką?

3. Czy dwoje lub więcej dzieci pierworodnych D₀ może mieć tę samą matkę?

4. Czy istnieją zależności, które można określić wzorem, np. na liczebność rodzeństwa?

Szukanie odpowiedzi na pierwsze pytanie sprawiło, że w ruch poszły komputery i pracują z przerwami do dziś, bowiem wciąż nie znaleziono matki pierworodnego równego 49 i jego rodzeństwa, które obecnie liczy 119 osobników. Ostatni składa się z 257 cyfr i od kwietnia br. wiadomo, że nie jest liczbą pierwszą, ale pełny rozkład na czynniki pierwsze podobno trwa, choć nie ma pewności, czy zostanie zakończony za życia najmłodszej osoby czytającej niniejszy tekst. 49 jest najmniejszą, ale nie jedyną liczbą D₀, której matki pozostają nieznane. Do tysiąca jest 28 ukrywających się matek. Ostatnią w tym zakresie znaleziono w roku 2014 – pojawiła się na 88 etapie jako 166-cyfrowa liczba pierwsza z pierworodnym równym 495 (oto początek rodzeństwa: 495 = 3×3×5×11 → 33511 = 23×31×47 → 233147 = 53×53×83 → 535383 …).

Jeśli chodzi o pytanie 2, czyli o warunki macierzyństwa, to ogólnym wymogiem jest, aby matka była „zlepkiem” co najmniej dwu liczb pierwszych ustawionych w kolejności niemalejącej sąsiednich par. Taki warunek pozbawia macierzyństwa liczby 1-cyfrowe, prawie wszystkie 2-cyfrowe i większość 3-cyfrowych. Tabela 3 obejmuje wszystkie liczby pierwsze do 1000. Matkami są te w kolorowych polach, ale warto zauważyć, że tylko bardzo nieliczne (niebieskie i czerwona) doczekają się, a właściwie są poprzedzone więcej niż jednym dzieckiem, a zaledwie jedna (czerwona) więcej niż dwojgiem.

Korzystając z wyróżnionych w tabeli 3 ponadjednodzietnych matek, można utworzyć 9 przypisanych im rodzeństw. Wszystkie podane są w tabeli 4 obok ich matek (lewa kolumna). Wyróżnione w tej tabeli dwa rodzeństwa prowadzą do odpowiedzi na trzecie pytanie. Dzieci 12 i 46 tworzą rodzeństwo przyrodnie w tym sensie, że nie należą do jednego ciągu działań, jak na przykład 4 i 22 (4 = 2×2 → 22 = 2×11 → 211). 12 zmierza do celu samodzielnie: 12 = 2×2×3 → 223 i do tego samego celu dąży niezależnie 46: 46 = 2×23 → 223. Obie liczby są więc dziećmi pierworodnymi D₀ tej samej matki. Podobnie przyrodnie rodzeństwo tworzą 42 i 74, bo oba zaczynają różne ciągi działań, choć częściowo (od 237) jednakowe: 42 = 2×3×7 → 237 = 3×79 → 379; 74 = 2×37 → 237 = 3×79 → 379.

Odpowiedzi na czwarte pytanie nie znamy, choć wszystko wskazuje na to, że z liczbami domowymi nie wiążą się na razie żadne wzory.

Można by jeszcze zapytać, dlaczego na tapecie jest wariant liczb domowych, w którym czynniki pierwsze „sklejane” są w kolejności rosnącej, a nie uwzględnia się kolejności malejącej. Iteracja na przykład 45 wyglądałaby wówczas tak: 45 = 5×3×3 → 533 = 41×13 → 4113 = 457×3×3 → 45733 = 83×29×19 → 832919 (liczba pierwsza). Wydaje się, że wynika to ze znacznie mniejszej liczby dzieci – odpadają wszystkie liczby parzyste, bo żadna z nich nie dociera do liczby pierwszej ze względu na utrzymującą się w trakcie iteracji parzystość. Można oczywiście tworzyć i analizować iterację złożonych liczb nieparzystych, zwłaszcza że niektóre są, podobnie jak dziecko 49 w przypadku „rosnącej” konkatenacji, wyjątkowo odporne na pierwszość. Łatwo się o tym przekonać, zaczynając na przykład od dziecka 85.

ZADANIA

1. Do kratek diagramu 3×3 (rys. 1) należy wpisać cyfry tak, aby w trzech rzędach i trzech kolumnach pojawiło się, jak w krzyżówce liczbowej, sześć trzycyfrowych liczb pierwszych, wśród których powinno być jak najwięcej spośród dziewięciu matek z dwojgiem lub trojgiem dzieci (z lewej kolumny tabeli 4).

2. W zapisie mnożenia dwu liczb 3-cyfrowych (rys. 2) ujawniono trzy cyfry. Należy rozszyfrować mnożenie, wiedząc, że mnożna i mnożnik są liczbami domowymi, czyli matkami.

3. Do której dwucyfrowej liczby pierwszej nie sposób dotrzeć w procesie iteracji, polegającym na dodawaniu w każdym etapie do liczby złożonej utworzonej w poprzednim etapie dowolnej z cyfr tej liczby. Gwoli wyjaśnienia sposobu iteracji przykład, rozpoczynający się liczbą 16 i docierający do 61: 16 → (+1) → 17 → (+7) → 24 → (+2) → 26 → (+2) → 28 → (+8) → 36 → (+3) → 39 → (+9) → 48 → (+8) → 56 → (+5) → 61.

4. Najmniejszą liczbą złożoną, prowadzącą do liczby pierwszej w wyniku rodzaju iteracji opisanego w zadaniu 3 i wymagającą 10 kroków, jest 22 194. Które dziesięć liczb tworzy tę iterację, jeśli jej ostatnią, dziesiątą, czyli docelową liczbą pierwszą jest 22 229?

Rozwiązania prosimy nadsyłać do 31 października br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 10/22. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką W zakamarkach mózgu pod redakcją Davida J. Lindena ufundowaną przez Wydawnictwo REBIS. Warunkiem udziału w konkursie jest zamieszczenie w e-mailu z odpowiedzią oświadczenia:

Zapoznałam/em się z regulaminem konkursu i akceptuję jego treść oraz wyrażam zgodę na przetwarzanie danych osobowych na potrzeby realizacji konkursu.

Regulamin konkursu jest dostępny na stronie www.swiatnauki.pl.

***

Rozwiązania zadań z numeru sierpniowego

1. Ciąg cyfr na „opadającej” przekątnej: 1-9-1-6-9-8-5-7-1; pełne rozwiązanie na rys. 3.

2. Liczby poziome w krzyżówce: 216, 7788, 4993, 395, 23; pełne rozwiązanie na rys. 4.

3. Największą liczbą z zerem w środku, która staje się swoim własnym dzielnikiem po wykreśleniu tego zera,jest 70875 = 7875×9.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Jak pachnie deszcz? Simona Kinga i Claire Nasir ufundowaną przez Wydawnictwo REBIS otrzymują: Janusz Komorowski z Warszawy, Tomasz Kowalczyk z Krakowa, Krzysztof Szeruga z Wrocławia, Janusz Włodarczyk z Będzina, Rafał Zorychta z Janowic.

***

Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla „Polityki”.