Konkatenacje, czyli o sklejaniu liczb pierwszych

Wśród łamigłówek, polegających na uzupełnianiu ciągu liczbowego brakującym kolejnym wyrazem, za niemal klasyczną uchodzi następująca: 77, 49, 36, 18, ?. Ciągiem tym rządzi prosta, łatwa do zauważenia reguła: każdy następny wyraz jest iloczynem cyfr poprzedniego. Zatem zamiast znaku zapytania powinno pojawić się 8. Ciąg jest zaledwie 5-wyrazowy i wydłużyć go nie sposób, bo iloczyn cyfr żadnej liczby nie jest równy 77, a iloczyn cyfr 8 kojarzy się z klaskaniem jedną ręką. A jednak można sobie z tymi ograniczeniami poradzić – wystarczy ciąg odwrócić, czyli z malejącego uczynić rosnący: 8, 18, 36, 49, 77, … . Co dalej? Teraz trzeba wymyślić regułę, która pozwoli pokonać barierę. Reguła nie będzie jednak prosta; może brzmieć na przykład tak (1):

Każdy wyraz a_n stanowi konkatenację (zlepek) dwu liczb A i B (zapis: A||B), gdzie A<B, A lub B jest nieparzysta, różnica (B–A) jest minimalna oraz, co najważniejsze: A×B=a_n-1.

Zatem po 77 pojawi się dalszy ciąg ciągu: 711, 979, 1189, 2941, … . Gdyby nie wykluczenie równoczesnej parzystości obu dzielników, ciąg wyglądałby całkiem inaczej: 8, 24, 46, 223, 1223, 11223, 87 129, 189 461, … . Jeszcze inny, ale co do zasady podobny ciąg powstanie, gdy zamiast na dzielniki położymy nacisk na ich konkatenację, która powinna być teraz utworzona z dwu dzielników poprzedniego wyrazu tak, by była liczbą jak najmniejszą, ale oczywiście by iloczyn tych dzielników był, jak dotąd, poprzednim wyrazem: 8, 18, 29, 129, 343, 497, 717, 2393, … . Zauważmy, że jeśli w ciągu pojawia się liczba pierwsza, to następny wyraz różni się od poprzedniego tylko dopisaną na początku jedynką.

Ponieważ ciąg liczbowy w podstawowej formie zaczyna się od najmniejszej możliwej liczby, zwykle od zera lub jedynki, zatem dwa ostatnie ciągi w takiej postaci będą wyglądać następująco: gdy obowiązuje reguła (1) – 1, 11, 111, 337, 1337, 7191, 51141, …; gdy konkatenacja dzielników jest najmniejszą liczbą – 1, 11, 111, 337, 1337, 1917, 2771, 16317, … .

W roku 1933 student matematyki David Champernowne (po latach znany brytyjski ekonomista i informatyk) opublikował pracę dotyczącą nieskończonej liczby „zlepionej” z wszystkich kolejnych liczb naturalnych, zaczynając od zera. Dla zachowania jej postaci kanonicznej liczba była ułamkiem dziesiętnym z przecinkiem po początkowym zerze i z czasem przyjęło się nazywać ją stałą Champernowne’a: 0,1234567891011121314151617… Odkrywcze w tej pozornie trywialnej czynności łączenia wagoników w niekończący się pociąg było to, że powstały długas okazał się pierwszą tzw. liczbą normalną utworzoną sztucznie (naturalną liczbą normalną jest, ale hipotetycznie, np. liczba pi). Upraszczając nieco definicję: liczba normalna to taka, w której żadna cyfra ani żadna kombinacja cyfr nie występuje częściej niż jakakolwiek inna (zamiast „normalna” lepiej pasowałoby określenie „sprawiedliwa”). W pracy Champernowne’a także po raz pierwszy pojawiło się określenie „konkatenacja” w kontekście matematycznym – jako „zlepianie” większych liczb z mniejszych. Jednak w przypadku tworzenia takich i podobnych (po)ciągów – na przykład z kolejnych liczb nieparzystych, pierwszych, kwadratów itp. – konkatenacja jest czynnością czysto mechaniczną, w której cyfry traktowane są jak znaki, a liczby jak zbiory znaków, bez uwzględniania ich wartości. Przypomina to łamigłówkę sudoku, w której wartości jednocyfrowych liczb wpisywanych do diagramu nie mają znaczenia – cyfry można bez uszczerbku dla zadania zastąpić dowolnymi innymi znakami, np. literami, byleby różnym cyfrom odpowiadały różne znaki.

Pełnię znaczenia konkatenacja uzyskała dopiero wówczas, gdy uznano ją za szczególny rodzaj działania arytmetycznego, choć w gruncie rzeczy oficjalnie takie uznanie… nigdy nie nastąpiło. Konkatenacja jako działanie przycupnęła na granicy matematyki poważnej i rekreacyjnej, ośmielając się czasem pojawiać w zadaniach. Oto prosty przykład sprzed dwóch lat – z XVI Mistrzostw Polski w Grach Matematycznych i Logicznych.

Liczba 2019 jest iloczynem dwóch liczb pierwszych: 3 i 673. Jeżeli połączymy te dwa czynniki na dwa możliwe sposoby (takie połączenie nazywamy konkatenacją), otrzymamy dwie liczby pierwsze: 3673 i 6733. Jaka jest najmniejsza liczba, będąca iloczynem takich trzech liczb pierwszych (niekoniecznie różnych), których wszystkie możliwe konkatenacje także są liczbami pierwszymi?

Z zadania wynikają wprost dwie dość oczywiste cechy konkatenacji jako działania. Po pierwsze: jest to, podobnie jak odejmowanie i dzielenie, działanie nieprzemienne, czyli 3||673 ≠ 673||3; uogólniając: A||B≠B||A. Po drugie: pełny zapis konkatenacji dwóch liczb sprowadza się do wzoru: A||B=A×10c(B)+B, gdzie c(B) oznacza liczbę cyfr liczby B. Łatwo zmodyfikować ten wzór dla konkatenacji trzech i więcej liczb. Na przykład dla trzech ma on postać: A||B||C=A×10c(B+C)+B×10c(C)+C.

O tym, że konkatenacja jest działaniem niszowym, świadczy też to, że nie doczekała się różnych określeń dla czynności i efektu końcowego, jak dodawanie i suma, mnożenie i iloczyn itp. „Konkatenacja” to nazwa zarówno działania, jak i jego wyniku, choć wynik mógłby być na przykład „konkatenatem” – na podobieństwo potęgowania i potęgi.

Powyższe zadanie stanowi także spektakularny przykład tego, co decyduje o uroku i walorach rozrywkowych konkatenacji. Są to głównie związane z nią ciekawostki i osobliwości liczbowe – niektóre z nich można „odkrywać”, rozwiązując łamigłówki wymagające logicznego myślenia. Nie jest to trudne w przypadku zadania z Mistrzostw, które krócej i przejrzyściej da się sformułować tak:

Znajdź najmniejszy iloczyn takich trzech liczb pierwszych (niekoniecznie różnych), których wszystkie konkatenacje są liczbami pierwszymi.

Minimalny iloczyn dają najmniejsze liczby pierwsze, czyli 2, 3, 5, 7, 11, … , ale 2 i 5 trzeba odrzucić, bo kończące się nimi konkatenacje nie będą liczbami pierwszymi. Teraz wystarczy zacząć od sprawdzenia, czy jakaś kombinacja trójek i siódemek spełnia warunki zadania. Szybko okazuje się, że każdy tercet złożony z dwóch trójek i jednej siódemki to liczba pierwsza (337, 373, 733), więc rozwiązaniem jest 63.

Zadanie stanowi przyczynek do całej gamy osobliwości konkatenacyjnych związanych z rozkładem liczb złożonych na czynniki pierwsze albo ogólniej – z liczbami pierwszymi. Za zbiór wyjściowy można uznać liczby pierwsze, które są konkatenacjami liczb pierwszych. Tworzą one ciąg: 23, 37, 53, 73, 113, 137, 173, 193, 197, 211, 223, 227 … . Niewiele mniej liczny jest podciąg złożony z liczb pierwszych stanowiących konkatenacje tylko dwu liczb pierwszych i tylko na jeden sposób, więc także takie konkatenacje trudno uznać za osobliwe. Natomiast do rarytasów wypada zaliczyć liczby pierwsze, będące konkatenacjami dwu kolejnych liczb pierwszych. Najmniejsza to oczywiście 23, ale tuż za nią jest dopiero 3137, zaś dwudziesty ósmy wyraz ciągu przekracza dziesięć milionów (10 131 019). Jest też w tym gronie unikat wysokiej próby – jedyny (w zakresie do biliarda – 10¹⁵) złożony z nieparzystej liczby cyfr: 99 991 100 003. Ciągiem tym interesowali się także poważni teoretycy liczb, dowodząc, że różnica między liczbami pierwszymi, tworzącymi każdą konkatenację (oprócz 23), musi być wielokrotnością sześciu.

Wracając do zadania z Mistrzostw, dotyczy ono fragmentu szerszego i jakby odwrotnego zagadnienia – szukania takich zestawów (zbiorów) n liczb pierwszych, których wszystkie możliwe konkatenacje są liczbami pierwszymi. Praktycznie każdą taką n-tkę jednoznacznie określa iloczyn tworzących ją liczb.

Dla n=2 iloczyny są liczbami półpierwszymi. Średnio czynniki pierwsze co dwudziestej z wszystkich liczb półpierwszych załapują się, mówiąc kolokwialnie, na dwie konkatenacje, a załapane iloczyny tworzą ciąg: 21, 33, 51, 93, 111, 133, 177, 201, 219, 247, 253, 327, 411, 427, 573, … . Jest oczywiście w tym ciągu na miejscu 43. wspomniany w zadaniu rok 2019. Warto zauważyć, że na następny trzeba trochę poczekać – do 2047 (konkatenacje pierwsze: 2389 i 8923). Począwszy od n=3 o właściwe zbiory, a więc i o odpowiadające im iloczyny coraz trudniej i stają się one coraz bardziej schematyczne: niemal każdy zawiera tylko dwie różne liczby pierwsze, z których mniejsza powtarza się dwa lub więcej razy, co ogranicza liczbę różnych konkatenacji. Jak dla n=3 minimalnym iloczynem jest rozwiązanie zadania, czyli 63=3×3×7 oraz trzy konkatenacje (337, 373 i 733), tak dla n=5 minimalny iloczyn to 146 461=7×7×7×7×61, a konkatenacji jest pięć: 617 777, 761 777, 776 177, 777 617, 777 761. Aż trudno uwierzyć, że cały ten bliźniaczy kwintet tworzą liczby pierwsze. Zestaw sześciu lub więcej takich liczb pierwszych, których wszystkie konkatenacje byłyby liczbami pierwszymi – nie jest znany.

Zadanie z Mistrzostw byłoby znacznie trudniejsze, gdyby zastrzec, że trzy liczby pierwsze powinny być różne. Praktycznie bez komputerowego wsparcia nie miałoby wówczas sensu zmierzanie do celu, który stanowi liczba 3311=7×11×43 oraz sześć konkatenacji jej czynników, z których każdy to liczba pierwsza. Jest prawie pewne, choć dowodu brak, że nie ma czterech różnych liczb pierwszych, których wszystkie konkatenacje (24 permutacje) byłyby liczbami pierwszymi.

Bodaj najciekawszym tematem związanym z konkatenacją liczb pierwszych są liczby zwane domowymi. Na poziomie elementarnym liczby pierwsze traktuje się czasem jak cegiełki, z których przez mnożenie budowane są inne liczby. Podobną rolę pełnią liczby pierwsze domowe (w znaczeniu „macierzyste”) jako swego rodzaju „przodkowie” liczb złożonych. Jak każda liczba pierwsza-cegiełka jest gotową budowlą, tak każda taka liczba jest również swoim własnym przodkiem. Natomiast która liczba pierwsza jest przodkiem, czyli liczbą pierwszą domową (LPD) danej liczby złożonej (LZ), ustala się algorytmicznie, wykonując kolejno poniższe polecenia:

1. Rozłóż LZ na czynniki pierwsze (np. 14=2×7);

2. Połącz czynniki pierwsze, ustawione w kolejności rosnącej, czyli utwórz ich konkatenację (2||7=27);

3a. Jeśli konkatenacja jest liczbą złożoną, powtórz na niej – i na każdej następnej konkatenacji, która będzie liczbą złożoną – polecenia 1. i 2. (27=3×3×3 → 333=3×3×37 → 3337=47×71 → 4771=13×367);

3b. Jeśli konkatenacja jest liczbą pierwszą, algorytm się kończy, a otrzymana liczba pierwsza jest LPD początkowej LZ (13367=LPD₁₄).

Dla LZ=14 potrzeba więc pięciu etapów (iteracji), aby dotrzeć do przodka. Oczywiście 13367 jest także LPD₂₇, LPD₃₃₃ i wszystkich LZ zwanych wtórnymi (LZ_W), jakie pojawiają się w algorytmie zaczynającym się od LZ pierwotnej (LZ_P), czyli w tym przypadku od 14. Dla większości z 74 liczb złożonych nie większych niż 100 droga do LPD liczy mniej niż pięć etapów, ale nie brak też dróg dłuższych, bardzo długich i… nieskończonych. Już dla trzeciej liczby złożonej, czyli 8, droga jest pechowo długa, bo 13-etapowa, zakończona 19-cyfrową LPD (rys.1).

Między innymi takie „niespodzianki” sprawiły, że debiut LPD w roku 1990 na łamach pisma „Recreational and Educational Computing” zainteresował spore grono matematyków i informatyków. Odpowiedź na podstawowe pytanie, które się wówczas pojawiło – czy każda LZ ma swoją LPD? – do dziś nie jest znana. Pierwszymi sprawcami tej niejasności były nieoczekiwanie dwie początkowe liczby ciągu zaczynającego ten artykuł – 77 i 49. Pierwsza z nich jest LZ_W względem drugiej, bo pojawia się w algorytmie zaczynającym się od 49 (rys. 2):

Obecnie ten ciąg kończy się na 119 etapie liczbą 257-cyfrową, której faktoryzacji dotąd żaden komputer się nie podjął. Później okazało się, że choć 49 jest jedyną dwucyfrową LZ_P, stawiającą opór przed dotarciem do jej LPD, to nie jedyną w ogóle. Takich liczb trzycyfrowych jest 27, a czterocyfrowych grubo ponad 100. Niewykluczone jednak, że przy sprawniejszych komputerach udałoby się opór większości z nich – a może nawet wszystkich – przełamać.

Tylko nieliczne liczby pierwsze są LPD wywodzącymi się od LZ. Oczywiście dlatego, że w grę wchodzą wyłącznie konkatenacje liczb pierwszych uporządkowanych w kolejności rosnącej: dwucyfrowe są tylko dwie – 23 i 37, trzycyfrowych 35 – od 211 do 797. Choć zdarza się, że różne LZ_P prowadzą do tej samej LPD. Dzieje się tak wówczas, gdy LZ_W lub LPD może być konkatenacją liczb pierwszych na więcej niż jeden sposób. Na przykład LPD=379 może być poprzedzone przez LZ_W=237=2||3||7 lub 2||37, co z kolei poprzedzają dwie różne LZ_P – 2×3×7=42 lub 2×37=74. Z kolei do LPD=223 prowadzi na podobnej zasadzie zarówno LZ_P=12, jak i 46.

Prawdopodobieństwo, że wygenerowana losowo liczba całkowita złożona z bardzo wielu cyfr okaże się liczbą pierwszą, maleje, gdy liczby stają się coraz większe. Dodatkowo zmniejsza się ono, jeśli uwzględnimy warunek, aby liczba – jak w przypadku LPD – była konkatenacją rosnącego ciągu liczb pierwszych. Mimo to hipoteza LPD, że każda liczba złożona jest generatorem liczby pierwszej domowej, pozostaje niewzruszona z prostego powodu – liczb pierwszych jest nieskończenie wiele. To, czy zaczynając od 49 lub podobnych jej krnąbrnych liczb, uda się dotrzeć do jakiegoś LPD, zależy od rosnącej mocy komputerów i postępów w dziale matematyki zwanym obliczeniową lub algebraiczną teorią liczb.

Zadania

1. Uczeń zsumował wszystkie kolejne liczby naturalne od 1 do X, korzystając z wzoru na sumę wyrazów ciągu arytmetycznego. Po dokładnym przyjrzeniu się wynikowi zauważył, że zamiast zastosowanego wzoru wystarczyło, aby skorzystał z konkatenacji, doklejając do X dwie liczby – pewną jednocyfrową liczbę na początku oraz dziesięciokrotnie od niej większą liczbę na końcu – wynik byłby taki sam. Jaką liczbą był X?

2. Od 5-cyfrowego kwadratu odklejamy ostatnią cyfrę – zostaje 4-cyfrowa liczba pierwsza. Od tej liczby odklejamy pierwszą cyfrę – zostaje 3-cyfrowa potęga, ale nie kwadrat. Od tej potęgi odklejamy pierwszą cyfrę – zostaje 2-cyfrowa liczba pierwsza, od której na koniec odklejamy drugą cyfrę, pozostawiając 1-cyfrowy kwadrat. Jaki kwadrat był na starcie?

3. Wieloetapowy ciąg działań zaczynamy od liczby startowej. W pierwszym i każdym kolejnym etapie liczbę startową lub utworzoną w poprzednim etapie można zmienić w jeden z trzech następujących sposobów:

I) dopisać na końcu 0,

II) dopisać na końcu 4,

III) podzielić przez 2, jeśli jest parzysta.

Liczbą startową jest 4. Gdyby celem była dwucyfrowa liczba pierwsza, krótka droga do celu wymagałaby wykonania kolejno operacji III-II-II-III-III=61. Cel jest jednak bardziej konkretny i bieżący – 2021. Jak dotrzeć do tej liczby w minimalnej liczbie kroków?

4. Która najmniejsza liczba jest liczbą pierwszą domową (LPD) trzech różnych (jakich?) liczb złożonych pierwotnych (LZ_p)?

Rozwiązania prosimy nadsyłać do 30 czerwca br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 06/21. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Kwantowa rzeczywistość. W poszukiwaniu prawdziwego znaczenia mechaniki kwantowej Jima Baggotta ufundowaną przez wydawnictwo Prószyński Media. 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 kwietniowego

1. Najdłuższy ciąg kratek połączonych rogami tworzą 4 kratki z siódemką (rys. 3).

2. Kolejne cyfry na przekątnej, łączącej lewy dolny róg z prawym górnym: 0163650 (rys. 4).

3. Poziomo leży 12 kamieni (rys. 5)

4. Najlepszy wynik, czyli największa suma czynników – 205. Pełne rozwiązanie na rys. 6.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Niedokończona rewolucja Einsteina. W poszukiwaniu tego, co leży poza granicami teorii kwantowej Lee Smolina, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Wojciech Błachut z Gliwic, Przemysław Mielcarek z Pruszkowa, Tomasz Migdałek z Poznania, Janusz Niedźwiedzki z Zawiercia, Mikołaj Walicki z Warszawy.