Przez „dostawki” do pierwszości i z powrotem
Świat liczb naturalnych zdominowany jest przez liczby pierwsze. Jeśli wybierzemy dowolną liczbę większą od 1, na przykład 2024, to albo będzie ona liczbą pierwszą, albo iloczynem liczb pierwszych (2024=2×2×2×11×23), a równocześnie sumą liczb pierwszych: przynajmniej dwóch (2024=2017+7) lub – jeśli będzie nieparzysta – co najmniej trzech (większych od 2). Wprawdzie dominacja jest częściowo hipotetyczna, bo dotyczące sum hipotezy Goldbacha (mocna i słaba) nie doczekały się pełnych dowodów, ale wśród matematyków dominuje przekonanie o ich prawdziwości.
O ile rozkład liczby na czynniki pierwsze, z dokładnością do ich kolejności, jest zawsze jednoznaczny (podstawowe twierdzenie arytmetyki), o tyle partycja, czyli podział liczby parzystej na dwie liczby pierwsze (w skrócie podział PP) jest jednoznaczny tylko dla 4 (2+2), 6 (3+3), 8 (3+5) i 12 (5+7). Dla dziewięciu liczb (10, 14, 16, 18, 20, 28, 32, 38, 68) partycje PP są dokładnie dwie, a dla pozostałych liczb podziałów PP jest na ogół i na dłuższym dystansie tym więcej, im większe są liczby. Dla 2024 są 32 różne podziały – ostatni, z najmniejszą różnicą między liczbami, tworzą 991 i 1033.
Do rzadkości należą takie podziały PP, których pełny zapis zawiera tylko dwie różne cyfry. Dwa początkowe zapisy to 4=2+2 i 22=11+11, a następnym jest dopiero 89 988=89 899+89. Jeszcze większymi rarytasami są kolejne – także ósemkowo-dziewiątkowe – bo dotyczą jednej liczby, która ma dwie partycje PP, każdą tylko z dwiema różnymi cyframi: 98 988 = 89+98 899 = 8999+89 989.
Podane ciekawostki zwiastują temat tego artykułu, którym są osobliwe zależności z okolic liczb pierwszych – ale tylko takie, które wiążą się z pojedynczymi cyframi w roli „dostawek”. W większości są one typowe dla matematyki rekreacyjnej, ale pojawiają się także przy analizowaniu poważnych zagadnień dotyczących teorii liczb.
* * *
Przekształcanie liczb złożonych w pierwsze było już tematem artykułu zamieszczonego w tej rubryce przed ponad rokiem (nr 10/2022), ale sposób zmiany wiązał się wówczas z rozkładem na czynniki pierwsze, czyli wymagał wykonywania działań arytmetycznych. Tym razem zajmiemy się prostszym, mniej „inwazyjnym” sposobem, polegającym na dopisywaniu cyfry na początku lub na końcu liczby.
Czy takie cyfrowe dostawki zawsze są skuteczne, tzn. czy każdą liczbę złożoną z można wydłużyć o cyfrę 1≤x≤9 tak, że powstanie liczba pierwsza równa x10k+z (k – liczba cyfr liczby z) lub 10z+x. Generalnie łatwo zauważyć, że efektywność prefiksu będzie teoretycznie możliwa tylko dla z zakończonych cyfrą 1, 3, 7 lub 9, a sufiksu tylko dla x równych 1, 3, 7 lub 9.
Poszukajmy najmniejszej liczby złożonej, na którą żaden z takich sposobów zmiany nie zadziała dla żadnego x. Do wyeliminowania – jako łatwe do zmiany – w pierwszej kolejności kwalifikują się liczby jednocyfrowe, bo wśród 2-cyfrowych liczb pierwszych nie brak żadnej z cyfr od 1 do 9. Przyjmując z kolei analogiczne kryterium dla liczb 2-cyfrowych, zauważymy, że żadna 3-cyfrowa liczba pierwsza nie zaczyna się od 20, 32, 51, 62 i 84 (początkiem nie może być także 53 i 89, ale to nie są liczby złożone). 51 odpada ze względu na liczby pierwsze 151, 251, 451 i 751. Zatem ciąg liczb złożonych, których 1-cyfrowymi doczepkami nie da się na pierwsze przerobić, zaczyna się od kwartetu 20, 32, 62, 84, …, a dalej jest 130 liczb 3-cyfrowych – od 114 do 998, niemal wyłącznie parzystych lub zakończonych piątką. Jedynką kończą się tylko dwie – 891 i 921; najmniejszymi unikatami z finałową siódemką i trójką są 1037 i 1653.
Odwrotna zmiana w taki sam sposób – liczby pierwszej na złożoną – jest oczywiście zawsze możliwa i trywialna. Interesujące może być natomiast szukanie odpowiedzi na pytanie: na ile co najmniej sposobów można takiej zmiany dokonać? Teoretycznie wszystkich sposobów jest 19: dopisanie jednej z dziesięciu cyfr na końcu albo jednej z dziewięciu na początku. Jednak dla 2, 3, 5, 7 i 11 jest 18 sposobów (dlaczego?). Sześć z nich łatwo wskazać – to ulokowanie liczby parzystej lub piątki jako końcówki. Z trzynastu lub dwunastu pozostałych sposobów na pierwszy ogień idą te, które tworzą sumę cyfr nowej liczby, a więc i samą liczbę, podzielną przez 3. Kluczem do ustalenia, na ile sposobów uda się taką sumę zawsze utworzyć, jest to, że liczbę pierwszą, jako nieparzystą (oprócz 2) i niepodzielną przez 3 (oprócz 3), można zawsze zmienić w podzielną przez 3, dopisując do niej dowolną z trzech cyfr różniących się o 3:
– 1, 4 lub 7 – do liczby pierwszej o wzorze 6m–1
– 2, 5 lub 8 – do liczby pierwszej 6m+1.
To daje pięć nowych sposobów zmiany liczby pierwszej p=6m–1 w złożoną (1, 4 lub 7 na początku oraz 1 i 7 na końcu) i trzy nowe sposoby zmiany liczby p=6m+1 w złożoną (2, 5, 8 na początku; jako końcówki liczby te były uwzględnione wcześniej).
Ponieważ szukamy najmniejszej liczby sposobów zmiany, więc bardziej obiecujące wydają się liczby p=6m+1, bo pewnych sposobów mamy jak dotąd dziewięć, w porównaniu z jedenastoma dla p=6m–1. Można więc zapytać: czy znajdzie się taka liczba p=6m+1 (7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, …), którą będzie można zmienić w złożoną tylko na dziewięć sposobów? Niestety, takiej liczby pierwszej prawdopodobnie nie ma (nie znamy dowodu), ale są dwie, które można zmienić „metodą dostawek” w liczby złożone tylko dziesięcioma sposobami: to siódemka (27, 57, 77, 87, 70, 72, 74, 75, 76, 78) oraz wcześniej wykluczona ze względu na podzielność trójka (33, 63, 93, 30, 32, 34, 35, 36, 38, 39). Czy takich liczb pierwszych – przekształcanych dostawkami tylko w dziesięć złożonych – jest więcej? W zakresie do stu milionów upolowano jeszcze zaledwie jedną – 29 587; jej obustronnymi dostawkami są 2, 5, 6 i 8, a końcową 0 i 4. Chętnych do kontynuowania łowów brak, więc nie wiadomo, czy jakiś większy okaz jeszcze się gdzieś w gąszczu liczb gigantów ukrywa.
Aby asortyment zmian był kompletny, należałoby go jeszcze uzupełnić o zmienianie liczb pierwszych c-cyfrowych w (c+1)-cyfrowe także pierwsze – oczywiście tak, jak dotychczas, czyli dopisując cyfrę w kolejnych krokach na jeden z trzech sposobów:
a) zawsze tylko jako ostatnią,
b) zawsze tylko jako pierwszą,
c) jako pierwszą lub ostatnią.
Określenie „w kolejnych krokach” oznacza, że w tym przypadku nie chodzi tylko o jedną zmianę, która zawsze jest albo nie jest możliwa, ale o ciąg zmian, zaczynający się od liczby pierwszej i mający określoną maksymalną długość.
Ciągi tworzone zgodnie ze sposobem (c) są zbyt zawiłe i zwykle bardzo długie, więc niezbyt ciekawe. Z tym sposobem wiąże się jednak zbiór osobliwych liczb pierwszych – takich, których nie sposób zmienić w dłuższe liczby pierwsze, dopisując do nich na początku lub na końcu dowolną cyfrę. Najmniejszą taką liczbą jest 773 – każdy uzupełniający ją jednocyfrowy prefiks lub sufiks daje liczbę złożoną. Niezwykłe jest też to, że dwie następne liczby pierwsze o takiej własności są względem siebie anagramami – 1103 i 1301, a kilkanaście kroków dalej jest spokrewniona z tą parą liczba pierwsza 10 303.
* * *
Sposób (a) zaczyna się od dopisania na końcu wybranej liczby pierwszej cyfry 1, 3, 7, lub 9 – takiej, aby powstała nowa liczba pierwsza. Zwykle jest więcej niż jedna możliwość, więc pojawiają się rozgałęzienia. W taki sam sposób wydłużana jest każda kolejna liczba. Celem jest ustalenie maksymalnej długości takiego procesu. Jeśli zaczniemy od najmniejszej liczby, czyli dwójki, to w drugim etapie pojawi się 23 lub 29. Cały proces, uwzględniający wszystkie możliwości, przedstawiony jest na rys. 1. Czerwone liczby pierwsze kończą ciągi, bo ich wszystkie możliwe wydłużenia są liczbami złożonymi. Plejada trójek i dziewiątek w tym przypadku wynika z wyeliminowania przez startową dwójkę końcówek 1 i 7, których obecność skutkowałaby podzielnością nowo tworzonej liczby przez 3. Układ współciągów nierzadko bywa bardziej rozgałęziony, jak choćby dla startowej liczby pierwszej 19 (rys. 2).
Największa liczba liczb w jednym z etapów zmian (pionowa kolumna) zwana jest szerokością zmian, a maksymalna liczba etapów to długość zmian, czyli praktycznie liczba wyrazów najdłuższego ciągu. Zatem zmiany zaczynające się dwójką mają szerokość 5 i długość 8, a zaczynające się od 19 odpowiednio – 10 i 9. W obu tych przykładach długości zmian są maksymalne dla liczb pierwszych 1- i 2-cyfrowych. Dla liczb 3-cyfrowych zmiana jest najdłuższa przy liczbie startowej 409 – odpowiada jej 11-wyrazowy ciąg kończący się 13-cyfrową liczbą 4 099 339 193 933. Amerykański informatyk Michael Branicky znalazł przed 2 laty najdłuższą znaną obecnie zmianę: 15-wyrazowy ciąg zakończony 26-cyfrową liczbą pierwszą 13 302 806 296 379 339 933 399 333, który zaczyna się 12-cyfrowym początkowym fragmentem tego giganta.
Przeciwieństwem tworzonych sposobem (a) długich ciągów są liczby pierwsze p, od których nie da się „wystartować”, bo żadna z liczb 10p+x (1≤x≤9) nie jest liczb pierwszą. Dwie najmniejsze, 53 i 89, były już wspomniane przy okazji przekształcania liczb złożonych w pierwsze. Po nich zaczynają się 3-cyfrowe: 107, 113, 167, 179, 251, 317, 347, 389, 397, … . Ciąg jest nieskończony, a rodzynkami są w nim liczby bliźniacze, czyli różniące się o 2; najmniejszą taką niewydłużalną parę tworzą 641 i 643.
Wydłużanie liczb pierwszych sposobem (b), czyli w lewo, zostaje ograniczone już na początku, bo odpadają 2 i 5. Dwie pozostałe liczby jednocyfrowe (3 i 7) wynagradzają jednak ten ubytek z dużą nawiązką znaczną liczbą współciągów, pojawiających w trakcie zmian o szerokości sięgającej kilkuset. Długość zmian dla 1-cyfrowych początków jest największa dla siódemki – kończy się 24-cyfrową liczbą 357 686 312 646 216 567 629 137. Prawdopodobnie wśród dwucyfrowych i dłuższych liczb pierwszych, zakończonych jedynką lub dziewiątką, nie ma takich, które byłyby początkiem ciągu zmian dłuższego niż 24-wyrazowy (wykluczamy oczywiście wydłużanie ciągu przez dopisywanie na początku zer nieznaczących, bo wówczas ciągi zmian byłyby nieskończone). Liczb pierwszych niewydłużalnych sposobem (b) jest znacznie mniej niż w przypadku sposobu (a). Następna po 2 i 5 to 149, a dalej są cztery 3-cyfrowe (401, 509, 773, 809) i 66 4-cyfrowych; w sposobie (a) mamy 31 3-cyfrowych i 208 4-cyfrowych. Ponadto znacznie trudniej trafić tu na rodzynki w postaci liczb bliźniaczych: pierwszą parę tworzą dopiero 15 581 i 15 583, czyli żadna cyfra dopisana przed tymi liczbami nie daje 6-cyfrowej liczby pierwszej.
* * *
Powstające metodą dostawek liczby pierwsze zwane są obcinalnymi (truncatable), ale określenie to dotyczy tylko takich liczb, od których można odcinać po jednej cyfrze aż do pozostawienia liczby pierwszej 1-cyfrowej. 10-cyfrowe liczby kończące ciąg na rys. 2 nie są więc obcinalnymi, bo odcinanie kończy się na 19.
Dłuższe liczby można skracać, usuwając z nich nie tylko skrajne cyfry, ale także wewnętrzne. To typowo rozrywkowe „działanie” bywa czasem bliskie poważnej matematyce. Na przykład w kontekście liczb pierwszych wiąże się z oryginalnym 26-wyrazowym ciągiem odkrytym przez amerykańskiego informatyka i teoretyka liczb Jeffreya Shallita: 2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469 , 6949, 9001, 9049, 9649, 9949, 60 649, 666 649, 946 669, 600 00 049, 66 000 049, 66 600 049. Ciąg ten jest swego rodzaju negatywnym testem pierwszości. Gdybyśmy chcieli sprawdzić, czy jakaś długa liczba może być liczbą pierwszą, należałoby spróbować usunąć z niej niektóre cyfry tak, aby pozostałe, zbliżone do siebie, utworzyły którąś liczbę z ciągu Shallita. Jeśli okazałoby się to niemożliwe, sprawdzana liczba na pewno nie byłaby pierwszą. Na przykład, żadne wykreślanie cyfr z liczby 44659 nie prowadzi do liczby z ciągu i nic dziwnego, bo 44659=17×37×71. Jeśli jednak zmienimy ostatnią cyfrę na jedynkę, to z liczby 44651 będzie można wykreślić trzy cyfry, pozostawiając 41, więc 44651 będzie kandydatką do pierwszości i – jak się okazuje – jest to kandydatura w pełni uzasadniona.
Zadania
1. Zakładamy następującą hipotezę: zmieniając jedną cyfrę w dowolnej liczbie naturalnej, można zmienić ją w liczbę pierwszą. Która najmniejsza liczba jest sprzeczna z tą hipotezą?
2. Suma ilu najwięcej kolejnych liczb naturalnych może być liczbą pierwszą?
3. Która najmniejsza liczba (niekoniecznie naturalna) pomnożona przez 10 lub pomnożona przez 25 daje w obu przypadkach liczbę o 1 większą od liczby pierwszej?
4. Nauczyciel napisał na tablicy pięć kolejnych liczb naturalnych. Jeden z uczniów zauważył, że tylko jedna z tych liczb jest pierwsza, ale równocześnie sumy cyfr czterech liczb są liczbami pierwszymi. Jaka była wartość najmniejszej liczby?
5. W trzycyfrowej liczbie pierwszej A oraz w trzech liczbach pierwszych X, Y, Z – jedno-, dwu- i trzycyfrowej – występują tylko trzy różne cyfry. A=X+Y+Z. B jest sumą cyfr liczby A; C jest sumą cyfr liczby B. B i C także są liczbami pierwszymi i B≠C. Jakie są wartości liczb X, Y, Z?
Rozwiązania prosimy nadsyłać do 31 marca 2024 roku pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 03/24. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Kate Crawford Atlas sztucznej inteligencji. Władza, pieniądze i środowisko naturalne ufundowaną przez Wydawnictwo Uniwersytetu Jagiellońskiego i Bo.wiem. 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.
***
Sprzężenie Zwrotne
W numerze lutowym zamieszczone były rozwiązania zadań z numeru grudniowego. Dwa z nich wymagają uzupełnienia w związku z nadesłanymi przez Pana Waldemara Karpińskiego z Nowego Miasta Lubawskiego rozwiązaniami, które wcześniej uszły mojej uwadze.
Zadanie 1 polegało na podziale tarczy zegara trzema liniami na 4 części tak, aby sumy liczb w tych częściach tworzyły ciąg arytmetyczny, a jedna z sum była równa różnicy ciągu. Linie dzielące nie mogły przebiegać między liczbami a brzegiem tarczy.
Oprócz podziału na rys. 4a (i jego wariantu z wydzieloną cyfrą 6 zamiast sumy 1+2+3) jest jeszcze sprytny i elegancki podział dający ciąg 0, 10, 20, 30 (rys. 4b).
W zadaniu 3 chodziło o uzupełnienie „szkieletu” działania [1 2 3 4 5 6 7 8 9 10 11=12] umieszczanymi między liczbami znakami (+, –, ×, :) i nawiasami, a także przez łączenie krótszych liczb w dłuższe – tak, aby powstała poprawna równość. Ponadto znaków (wliczając w to nawiasy) powinno być jak najmniej.
Jako najlepsze podane było jedno z rozwiązań z 15 znakami: 1–234*5/6+7+89+10*11=12. Tymczasem Panu Karpińskiemu udało się ograniczyć ten wynik do 13 znaków: 12+34×(56-7×8):91011=12. Kluczem do znalezienia tego rekordu było oczywiście ubogie w znaki wyzerowanie fragmentu „szkieletu” od 3 do 11.
***
Rozwiązania zadań z numeru styczniowego
1. Jeśli w kolejce przed n-miejscowym parkingiem czeka na wjazd n aut i kierowcy żadnych dwu kolejnych nie zamierzają parkować na tym samym stanowisku, to liczba różnych możliwych dobrych kolejek równa jest nn-1.
2. Gdy do m=7-miejscowego parkingu zmierza a=5 aut, to przed wjazdem mogą one utworzyć (m+1–a)(m+1)a–1=12288 dobrych kolejek.
3. Na parkingu 7×7 można umieścić najwięcej 28 aut tak, aby każde auto miało możliwość wyjazdu z parkingu. Przykładowe rozmieszczenie aut na rys. 3.
Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Sary Manning Peskin Zbuntowany mózg ufundowaną przez Wydawnictwo REBIS, otrzymują: Aleksandra Gądek z Przezmarku, Elżbieta Jakubowska z Warszawy, Waldemar Karpiński z Nowego Miasta Lubawskiego, Rafał Woźniakowski z Niepołomic.
***
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”.