Tab. 1 Tab. 1 Marek Penszko
Strona główna

Od półpierwszych do gładkich czyli z perspektywy faktoryzacji

Tab.2Marek Penszko Tab.2
Rys. 1Marek Penszko Rys. 1
Rys. 2Marek Penszko Rys. 2
Rys. 3Marek Penszko Rys. 3
materiały prasowe
Rys. 4Marek Penszko Rys. 4
Rys. 5Marek Penszko Rys. 5
Zagadka numeru.

Czy możliwy jest rozkład liczby pierwszej na czynniki pierwsze? Pytanie o tyle ma sens, że dawniej jedynkę uznawano za liczbę pierwszą, więc na przykład 13 rozkładano na 1 i 13. Tylko że taki rozkład był niejednoznaczny, bo mógł obejmować więcej niż jedną jedynkę, czyli był sprzeczny z zasadniczym twierdzeniem arytmetyki o jednoznaczności rozkładu. Ponadto wskazane twierdzenie dotyczy liczb złożonych, więc rozkład trzynastki oznaczałby, że jest to liczba złożona.

Z tymi paradoksami rozprawiono się w XIX wieku, eliminując jedynkę z grona liczb pierwszych, choć trudno dokładnie określić, kiedy to nastąpiło. Nie było tak, jak w przypadku Plutona, któremu Międzynarodowa Unia Astronomiczna 24 sierpnia 2006 roku odebrała status normalnej planety i mianowała karłowatą. Wiadomo, że jeszcze w 1899 roku matematyk francuski Henri Lebesgue akceptował pierwszość jedynki (później zmienił zdanie).

Chociaż trudno mówić o rozkładzie liczb pierwszych na czynniki pierwsze, to z ich definicji wynika, że każda jest podzielna tylko przez 1 i samą siebie, więc w jej „wirtualnym” rozkładzie występuje dokładnie jeden czynnik pierwszy – równy jej samej. Wszystkie pozostałe liczby całkowite większe od 1 są złożone, a więc rozkładalne na co najmniej dwa czynniki pierwsze. Jeśli czynniki są tylko dwa, to liczby noszą nazwę półpierwszych, jeśli trzy – liczb sfenicznych. Żadne liczby rozkładane na więcej czynników pierwszych nie zasłużyły sobie dotąd na odrębne określenia, ale próbowano wprowadzić ogólną terminologię, uwzględniającą liczbę czynników. Przyjęła się zaproponowana przez norweskiego matematyka Viggo Bruna w 1920 roku nazwa „prawie-pierwsze” poprzedzona liczbą. Zatem na przykład 2025 jest liczbą 6-prawie-pierwszą (w skrócie 6pp), bo zawiera w rozkładzie 6 czynników pierwszych (2025=3×3×3×3×5×5); natomiast 13 jest 1pp, czyli po prostu pierwsza.

* * *

Różne cechy rozkładu na czynniki pierwsze stały się podstawą kilku klasyfikacji liczb naturalnych według różnych kryteriów. W związku z „prawie-pierwszością” naturalny jest podział na zbiory, z których każdy obejmuje liczby z taką samą liczbą czynników w rozkładzie. Właściwie zbiory te tworzą nieskończone ciągi, których początkowe fragmenty znajdują się w tabeli.

We wszystkich ciągach panuje – podobnie jak wśród liczb pierwszych (1pp) – „chaos”, tzn. że żaden nie jest zdyscyplinowany wzorem, pozwalającym określić wartość n-tego wyrazu. Z tabeli widać też, że ciągi są (począwszy od 2pp) tym rzadsze – czyli w danym zakresie mniej zasobne w wyrazy – im więcej czynników pierwszych mają w rozkładzie. Na przykład do tysiąca jest 299 liczb 2pp oraz 149 4pp, ale już tylko 14 7pp i dwie 9pp. Od 10pp mniejszych od tysiąca nie ma żadnych, bo najmniejsza to 1024=210.

Równie naturalny wydaje się podział liczb złożonych na bezkwadratowe i subkwadratowe.

Rozkład tych pierwszych składa się z różnych czynników, natomiast w rozkładzie tych drugich przynajmniej jeden czynnik występuje co najmniej dwukrotnie, czyli w co najmniej drugiej potędze, więc liczba jest podzielna przez kwadrat tego czynnika. Intuicja podpowiada, że subkwadratowych jest wśród złożonych na określonym „dystansie” znacznie więcej niż bezkwadratowych. Istotnie – i różnica ta rośnie wraz z długością liczb. Choć dla 1-cyfrowych wynosi 2 (jedna 6 bez- kontra trzy [4, 8, 9] sub-), a dla 2-cyfrowych tylko 1 (34 bez-, 35 sub-), to 3-cyfrowych sub- jest już o 112 więcej niż bez-.

Wśród liczb złożonych bezkwadratowych pojawiają się tercety, których obecność przypomina występowanie liczb bliźniaczych w ciągu liczb pierwszych (tercet oznacza trzy kolejne liczby naturalne, kwartet – cztery, kwintet – pięć itd). Pierwszy tercet tworzą [33 (3×11), 34 (2×17) i 35 (5×7)]. Kolejne tercety zaczynają się od 85, 93, 141, 185, 201, … . Dominują w nich liczby półpierwsze (2pp). Pierwszym utworzonym z trzech liczb sfenicznych (3pp) jest [1309 (7×11×17), 1310 (2×5×131), 1311 (3×19×23)]. Teoretycznie możliwe są tercety złożone z trzech liczb bezkwadratowych xpp dla dowolnego x, ale praktycznie komputery dotarły do x=11 – liczby w tercecie są wówczas 18-cyfrowe. Bezkwadratowych kwartetów liczb złożonych oczywiście być nie może, bo jedna z tych liczb musi być wielokrotnością czterech, czyli 22.

Dla odmiany wśród liczb subkwadatowych „ansamble” mogą być dowolnie liczne, zaczynając od duetu [8 (22), 9 (32)] i tercetu [48 (24×3), 49 (72), 50 (2×52)]. Liczby w kolejnych zespołach szybko rosną i na przykład w najmniejszym oktecie są już 7-cyfrowe – od 1 092 747 (3×192×1009) do 1 092 754 (2×132×53×61).

Swego rodzaju spoiwem liczb bez- i subkwadratowych są ważne w teorii liczb trzy funkcje – dwie funkcje omega i funkcja Möbiusa, dotyczące czynników pierwszych w rozkładzie liczb naturalnych. Funkcje omega określają liczby tych czynników: duża omega (Ω) – wszystkich, mała omega (ω) – różnych. Stąd wniosek, że Ω≥ω, a Ω=ω tylko dla liczb bezkwadratowych. Ponadto dla 1 i liczb pierwszych przyjęte jest Ω=ω=1. Przykład: 360=23×32×5, zatem Ω360=3+2+1=6, a ω360=3. Łatwo zauważyć, że dla wszystkich potęg – niezależnie od podstawy i wykładnika – ω=1, podczas gdy Ω może przybierać dowolnie duże wartości.

Natomiast funkcja Möbiusa przyjmuje tylko trzy wartości: 0, 1 i minus 1. Równa jest 0 dla liczb subkwadratowych, zaś 1 i minus 1 dla bezkwadratowych: 1 jest wtedy, gdy liczba czynników pierwszych w rozkładzie jest parzysta, a minus 1, gdy jest nieparzysta, czyli także w przypadku liczb pierwszych.

Czy w ciągu liczb naturalnych mogą być tercety z funkcją Möbiusa równą minus 1 (kwartety są oczywiście wykluczone z tego samego powodu, jak podany wyżej dla kwartetów liczb złożonych bezkwadratowych)? Takie tercety tworzą choćby liczby pierwsze bliźniacze i rozdzielająca je liczba bezkwadratowa z nieparzystą liczbą czynników pierwszych. Nie są one rzadkością, poczynając od [29, 30 (2×3×5), 31]. Druga możliwość to odpowiednie spośród wspomnianych wyżej tercetów liczb bezkwadratowych; tu także nietrudno o przykłady – pierwszy to [229 (liczba pierwsza), 230 (2×5×23), 231 (3×7×11)]. A czy może być tak, by żadna liczba w tercecie nie była liczbą pierwszą, czyli aby liczba czynników pierwszych w rozkładzie każdej była nieparzysta i większa od 1? Takie tercety także nie są rzadkością, ale zaczynają się od [1309 (7×11×17), 1310 (2×5×131), 1311 (3×19×23)] i w dużym zakresie obejmują wyłącznie liczby sfeniczne (3pp). Dopiero przy liczbach 5-cyfrowych pojawia się bezkwadratowy tercet z liczbą 5pp: [50609 (13×17×229), 50610 (2×3×5×7×241), 50611 (11×43×107)].

* * *

Temat rozkładu na czynniki pierwsze gości w tej rubryce w następstwie wypadu autora w Tatry i wejścia na szczyt, którego wysokość wyraża się pewną szczególną liczbą. To jedyny szczyt polskich Tatr na szlaku turystycznym o takiej osobliwej wysokości. Chodzi o Zadni Granat, liczący 2240 m. Łatwo sprawdzić, na czym polega osobliwość, rozkładając tę liczbę na czynniki pierwsze – wszystkie są jednocyfrowe (26×5×7). Liczba jest oczywiście niezwykła jako unikalna wysokość dostępnego turystycznie tatrzańskiego szczytu, a nie w kontekście wyłącznie matematycznym, gdyż iloczynów liczb jednocyfrowych jest bardzo dużo. W matematyce noszą nazwę 7-gładkich, bowiem z ich rozkładu nie „wystają” żadne czynniki pierwsze większe od 7, czyli większe niż jednocyfrowe.

Uogólniając, liczba jest k-gładka (k≥2), jeśli nie zawiera czynników pierwszych większych niż k. Inaczej mówiąc, do liczb k-gładkich należą wszystkie, które są wynikami potęgowania (wykładnik potęgi w≥0) i mnożenia liczb pierwszych 2≤pk. Liczby 2-gładkie są więc potęgami 2; 3-gładkie – potęgami 2, 3 oraz iloczynami tych potęg (1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, …); 5-gładkie – analogicznie (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, …) itd. Warto zauważyć, co zresztą widać z przykładów, że każda liczba k-gładka jest także k’ gładką, gdzie k’>k. Natomiast liczba k’-gładka może być k-gładką, gdy nie jest podzielna przez k’, a jest zawsze k-gładką, gdy k i k’ są kolejnymi w ciągu liczb pierwszych.

Wbrew pozorom liczby gładkie znacznie mocniej niż z matematyką rekreacyjną wiążą się z informatyką i matematyką poważną, a ściślej z algorytmami faktoryzacji oraz z kryptografią. Wprawdzie może być zabawą liczbową zadanie polegające na ustalaniu, czy na przykład różnocyfrowa liczba 49 218 750 należy do 7-gładkich, ale to zabawa raczej dla odpowiednio zaprogramowanego komputera, a właściwie programisty lub zasobnego w funkcje kalkulatora. Nie ma prostszego, a zwłaszcza logicznego sposobu na sprawdzenie, że podana wyżej duża liczba istotnie jest 7-gładka niż rozłożenie jej na czynniki pierwsze – przybierze wówczas postać 2×32×58×7. Jednym z nielicznych przykładów „gładkiej” rozrywki jest wariant popularnej przed laty gry komputerowej 2048, w której zamiast potęg dwójki – tworzonych w trakcie przesuwania płytek podczas rozgrywki – powstają na identycznej zasadzie liczby 3-gładkie. Inny przykład znajduje się wśród poniższych zadań.

Zadania

1. Zapis rozkładania liczby na czynniki pierwsze wygląda zwykle tak, jak na rys. 1. Rozkładana liczba i kolejne (powstające w wyniku działań) znajdują się po lewej stronie. Po prawej jest zawsze najmniejszy dzielnik (większy od 1) sąsiedniej liczby, przez który jest ona dzielona, a iloraz pojawia się po lewej piętro niżej – i etap dzielenia się powtarza. Cały proces kończy się jedynką u dołu lewego słupka.

Zadanie polega na rekonstrukcji rozkładania, w którym ujawnione są oprócz jedynki tylko dwie dwójki (rys. 2). Końcowym rozwiązaniem jest oczywiście liczba startowa.

2. Z piętnastu liczb pierwszych mniejszych od 50 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47) można wybrać dziewięć, z których uda się utworzyć kwadrat półmagiczny 3×3, czyli taki, w którym suma trzech liczb w każdym wierszu i w każdej kolumnie będzie jednakowa. Przykład z sumą równą 59 (także liczba pierwsza) na rys. 3. Kwadrat byłby w pełni magiczny, gdyby sumy liczb na przekątnych również były takie, jak w rzędach, choć na rys. 3 te dwie sumy – mimo, że są inne – zachowują pierwszość (37 i 109).

Zadanie polega na utworzeniu kwadratu półmagicznego z dziewięciu liczb wybranych z 15 mniejszych od 50 liczb złożonych bezkwadratowych (6, 10, 14, 15, 21, 22, 26, 30, 33, 34, 35, 38, 39, 42, 46).

3. Oto dłuższy początkowy fragment ciągu liczb 3-gładkich, obejmujący wszystkie liczby 1-, 2- i 3-cyfrowe oraz trzy 4-cyfrowe.

1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972, 1024, 1152, 1296, … .

Z tego fragmentu wyjęto zgodnie z pewną zasadą poniższy podciąg złożony z tuzina wyrazów, w którym pominięto jeden wyraz, zastępując go znakiem zapytania.

27, 54, 72, 108, 256, ?, 576, 729, 768, 972, 1024, 1152.

Który wyraz został pominięty i jaka dodatkowa zasada rządzi tym podciągiem?

Rozwiązania prosimy nadsyłać do 31 stycznia 2025 roku pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 01/25. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Radość z abstrakcji. O matematyce, teorii kategorii i... życiu Eugenii Cheng ufundowaną przez wydawnictwo Helion. 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 listopadowego

1. 18 jest najmniejszą z 11 kolejnych liczb całkowitych (od 18 do 28), których suma kwadratów jest kwadratem i wynosi 5929=772.

2. 43 – to suma liczb w prostokątach niedotykających brzegu. Pełne rozwiązanie na rys. 4.

3. Podział diagramu z oznaczonymi kwadratami na rys. 5.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Biologia. Opowieść o życiu Lindsay Turnbull, ufundowaną przez wydawnictwo REBIS, otrzymują: Zbigniew Kapusta z Banina, Paweł Konopa z Piaseczna, Mateusz Kostanek z Krakowa, Mariusz Trzyna z Hyżnego i Andrzej Żołyński z Zielonej Góry.

***

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”.

Świat Nauki 1.2025 (300401) z dnia 01.01.2025; Umysł giętki; s. 75

Ta strona do poprawnego działania wymaga włączenia mechanizmu "ciasteczek" w przeglądarce.

Powrót na stronę główną