Parada dzielników, czyli śladami problemu 25

Jeden z rozdziałów wydanej w ubiegłym roku książki Ciekawostki matematyczne…* nosi tytuł Interesujące problemy i ich równie interesujące rozwiązania. Problemów, a właściwie zadań, jest w tym rozdziale 90. Czy wszystkie są interesujące – to sprawa subiektywna. Podobnie ich rozwiązania – nie każde i nie dla każdego będzie równie ciekawe, ale o jednym trudno wyrobić sobie zdanie, bo go po prostu nie ma – zapewne zostało przeoczone przez autorów lub podczas tłumaczenia. Chodzi o rozwiązanie problemu 25, sformułowanego w jednym krótkim zdaniu:

Jaka jest najmniejsza liczba mająca dokładnie 28 dzielników?

Problem jest (moim zdaniem) interesujący, więc jego brakującemu rozwiązaniu warto poświęcić nieco miejsca w kontekście szerszym niż 28.

Każda liczba naturalna większa od 1 ma co najmniej dwa dzielniki. Jeśli ma tylko dwa – jeden i samą siebie – jest z definicji liczbą pierwszą (np. 3, 59, 821, 6047). Pytanie „jaka jest najmniejsza liczba mająca dokładnie dwa dzielniki?” sprowadza się więc do pytania o najmniejszą liczbę pierwszą. Odpowiedzią jest oczywiście 2, ale warto zauważyć, że 100 lat temu nie byłoby to tak oczywiste. Niektórzy matematycy (np. Henri Lebesgue i Godfrey Hardy) wówczas jeszcze za liczbę pierwszą uznawali 1. Z czasem i oni zmienili zdanie, m.in. ze względu na sprzeczność takiego poglądu z podstawowym twierdzeniem arytmetyki: każdą liczbę naturalną większą od 1, niebędącą liczbą pierwszą, można jednoznacznie przedstawić w postaci mnożenia liczb pierwszych. Gdyby 1 było liczbą pierwszą, trudno byłoby mówić o jednoznaczności. Ponadto 1 nie odpowiada przyjętej definicji liczby pierwszej, której oba dzielniki powinny być różne.

Od dwudzielnikowych liczb pierwszych blisko do mających tylko trzy dzielniki. W pierwszej chwili może się wydawać, że każdą otrzymamy, mnożąc dwie dowolne liczby pierwsze. Rozumowanie jest takie: skoro każda liczba pierwsza ma dwa dzielniki, więc ich iloczyn będzie miał cztery, ale jeden (1) jest wspólny, zatem zostaną trzy. Błąd polega, rzecz prosta, na pominięciu pojawiającego się iloczynu jako nowego dzielnika – w sumie będą więc cztery. Co zrobić, aby były trzy? Nietrudno odgadnąć – trzeba pomnożyć liczbę pierwszą przez samą siebie, czyli podnieść do kwadratu. Pytanie o najmniejszą liczbę z dokładnie trzema dzielnikami sprowadza się zatem do pytania o najmniejszy kwadrat liczby pierwszej, a odpowiedzią jest 2²=4. Z kolei przedstawione powyżej błędne rozumowanie prowadzi do rozwiązania zadania, które gości czasem w podręcznikach arytmetyki: Znajdź najmniejszą liczbę z dokładnie czterema dzielnikami. Zapewne nauczyciele potwierdzą, że niejeden uczeń radzi sobie z tym problemem, wykonując bez zastanowienia mnożenie 1×2×3×4=24 albo 1×2×3×5=30, podczas gdy powinien szukać najmniejszej liczby półpierwszej, czyli będącej iloczynem dwu najmniejszych liczb pierwszych – 2×3=6.

Podane przykłady dla dwóch, trzech i czterech dzielników prowadzą do wniosku, że trudno podać ogólny wzór na najmniejszą liczbę d_min mającą τ dzielników, choć można wskazać pewne ogólne własności tych liczb lub niektórych z nich. Na przykład taką, że dla nieparzystej liczby dzielników d_min jest kwadratem liczby parzystej. Nie jest to jednak specyficzna własność, bowiem kwadratem jest każda liczba z nieparzystą liczbą dzielników. Dzieje się tak, ponieważ dzielniki każdej liczby tworzą pary dzielnik-iloraz, ale w przypadku kwadratów pojawia się para, w której dzielnik równa się ilorazowi, co powoduje, że ogólna pula różnych dzielników staje się liczbą nieparzystą. Z kolei parzystość d_min nie wiąże się tylko z nieparzystą liczbą dzielników, o czym będzie mowa dalej.

Brak wzoru nie oznacza braku metody. Przeciwnie, rozgryzienie problemu 25 nie jest trudne. Podstawowy klucz stanowi rozkład liczby d na czynniki pierwsze, czyli przedstawienie jej w postaci mnożenia liczb pierwszych p:

(1) d = p₁^w1×p₂^w2×…×p_k^wk

Dzielnikami liczby d są liczby p oraz ich wszystkie różne iloczyny, w których każda liczba p występuje co najwyżej tyle razy, ile wynosi wykładnik potęgi (w) umieszczony przy danej liczbie w powyższym zapisie. Inaczej mówiąc, dzielnikiem jest każda liczba postaci p₁^z1×p₂^z2×…×p_k^zk, gdzie 0≤z_i≤w_i (i=1, 2, …, k). Jeśli więc np. wszystkie z_i=0, to dzielnik równa się 1, a jeśli wszystkie z_i=w_i to dzielnikiem jest d. Wykładnik z₁ przyjmuje dokładnie w₁+1 wartości (0, 1, 2, …, w₁), wykładnik z₂ – w₂+1 wartości itd. Dzielników postaci p₁^z1×p₂^z2 będzie więc (w₁+1)×(w₂+1), zaś liczba wszystkich dzielników wyniesie:

(2) τ(d) = (w₁+1)×(w₂+1)×…×(w_k+1).

Na przykład, jeśli d=35 640, to rozkładając tę liczbę na czynniki pierwsze, otrzymamy: 35 640=2³×3⁴×5×11. Dzielników 35 640 jest więc (3+1)×(4+1)×(1+1)×(1+1)=80.

Odwróćmy teraz sytuację, pytając o najmniejszą liczbę, która ma 80 dzielników. Czy będzie nią właśnie 35 640? Aby to ustalić, należy zacząć od rozłożenia 80 na czynniki pierwsze (80=2⁴×5), a następnie przedstawić liczbę 80 w postaci mnożenia (faktoryzacji) na wszystkie możliwe sposoby, które w tym przypadku obejmują od dwóch do pięciu czynników:

Każde mnożenie odpowiada wzorowi (2), a więc czynniki są o 1 większe od wykładników potęg w rozkładzie szukanej liczby na czynniki pierwsze. Skoro ta liczba powinna być minimalna, to:

– podstawy potęg powinny być jak najmniejsze;

– większe wykładniki powinny występować przy mniejszych podstawach.

Zatem największy wykładnik pojawi się przy dwójce, kolejny mniejszy przy trójce, następny przy piątce itd. W taki sposób należałoby tworzyć wszystkie jedenaście liczb, korzystając z pomniejszonych o 1 czynników z tabeli oraz wzoru (1), w celu znalezienia najmniejszego iloczynu. Skoro jednak szukamy liczby minimalnej i być może mniejszej od 35 640, to większość działań można od razu pominąć – te mianowicie, w których suma wykładników jest zbyt duża i liczba d byłaby na pewno większa od 35 640. W związku z tym wystarczy wykonać obliczenia dla wykładników odpowiadających czynnikom z mnożeń (a), (b), (c) i (d) w tabeli.

(a) 2⁴×3³×5³=54 000

(b) 2⁹×3×5×7=53 760

(c) 2⁴×3³×5×7=15 120

(d) 2⁴×3×5×7×11=18 480

Okazuje się więc, że jeśli τ=80, to d_min jest znacznie mniejsze od 35 640 i wynosi 15 120.

Rozwiązanie problemu 25 wydaje się prostsze, bo sposoby faktoryzacji τ=28 są tylko trzy – 14×2, 7×4, 7×2×2 – a ponieważ 3³>3×5 zatem nie ma wątpliwości, że mniejszą liczbę dają wykładniki odpowiadające czynnikom trzeciego iloczynu: d_min=2⁶×3×5=960.

Teraz jest oczywiste, dlaczego d_min musi być zawsze liczbą parzystą. Dzieje się tak za sprawą rozpoczynającej każde mnożenie dwójki w podstawie największej potęgi.

W ogólnym przypadku szukanie najmniejszej liczby d_min mającej τ dzielników jest więc czynnością dwuetapową, która najczęściej polega na:

I) rozłożeniu liczby τ na czynniki pierwsze:

(3) τ= p₁×p₂×…×p_n, gdzie p₁≥p₂≥…≥p_n

II) obliczeniu najmniejszej liczby ze wzoru:

(4) d_min=2^p₁^–1×3^p₂^–1×…×q_n^p_n^-1, gdzie q_n jest n-tą liczbą pierwszą.

Skorzystanie z podanych wzorów umożliwia rozwiązanie problemu 25 i jest skuteczne dla większości liczb τ, zwanych w takim przypadku zwyczajnymi. Jednak dla niektórych τ ten sposób zawodzi, prowadzi bowiem do liczby większej niż d_min. Tak właśnie jest w podanym wyżej przykładzie z τ=80 – zastosowanie wzorów (3) i (4) kończy się mnożeniem (d) i liczbą 18 480, podczas gdy właściwym jest wynik mnożenia (c). Takich τ, określanych jako wyjątkowe, mniejszych od 80 jest siedem (8, 16, 24, 32, 48, 64, 72), a do tysiąca są 62.

Metodę znajdywania najmniejszych liczb z daną liczbą dzielników pierwszy przedstawił rosyjski matematyk Aleksander Minin na wykładzie wygłoszonym w Moskiewskim Towarzystwie Matematycznym w roku 1882. W późniejszej publikacji tego wykładu znalazły się także konkretne wzory na d_min dla τ wyrażającego się liczbą pierwszą, jej potęgą albo iloczynem dwóch lub trzech różnych liczb pierwszych. Temat zależności między d_min a τ długo pozostawał zapomniany; powrócił dopiero w latach 60. XX wieku, a teoretycy liczb zajęli się głównie zwyczajnymi i wyjątkowymi liczbami τ. Udowodniono m.in., że wyjątkowe są liczby τ równe 16p, gdzie p jest liczbą pierwszą większą od 3, a także równe p^k wtedy i tylko wtedy, gdy 2^p≤p_k, gdzie p_k jest k-tą liczbą pierwszą. Na przykład τ=3⁴=81 jest zwyczajne, bo 2³>p₄=7, natomiast każde τ=3^k, gdzie k≥5, jest wyjątkowe, ponieważ 2³<p_k. Obecność p we wzorach uzasadnia zainteresowanie tematem, czyli jego związek z odwieczną i wciąż nierozwiązaną zagadką rozmieszczenia liczb pierwszych wśród liczb naturalnych.

Zadania

1. Jaka jest najmniejsza liczba mająca dokładnie 28 dzielników, podzielna przez 28 i kończąca się liczbą 28?

2. Jeżeli liczba N jest potęgą, czyli N=a^m (m=2, 3, 4,…), to prawie zawsze można znaleźć liczbę mniejszą od N, która ma więcej dzielników niż N. Prawie, ponieważ są trzy wyjątki. Nie znajdziemy takiej liczby, gdy N=4, 8 lub… Jaka jest ta trzecia wyjątkowa liczba, jeśli wiadomo, że jest ona mniejsza od 100?

3. Liczba dzielników liczby A wyraża się liczbą oznaczającą pewien miniony rok XXI wieku. Który to rok i o jaką liczbę A chodzi, jeśli jest ona najmniejszą z możliwych?

Rozwiązania prosimy nadsyłać do 30 kwietnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 04/18, lub listownie: Świat Nauki, ul. Gintrowskiego 28, 02–697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką To, czego się nie dowiemy. Badanie granic nauki Marcusa du Sautoy ufundowaną przez wydawnictwo Prószyński Media.

*Ciekawostki matematyczne. Skarbnica zadziwiających rozrywek. Alfred Posamentier, Ingmar Lehmann. Prószyński Media Sp. z o.o., Warszawa, 2017.

***

Rozwiązania zadań z numeru lutowego

Rozwiązanie na rysunku.

2. Ułamek 2/5 w ciągu Fareya F1000 poprzedzony jest bezpośrednio ułamkiem 399/998.

3. Największym ułamkiem właściwym a/b w drzewie Calkina-Wilfa – takim, że liczby a, b i a+b składają się w sumie z dziesięciu różnych cyfr – jest 487/539 (a+b=1026). Podany w zadaniu w numerze lutowym przykład najmniejszego takiego ułamka (269/784, a+b=1053) był poprawny tylko dla liczb trzycyfrowych w liczniku i mianowniku; w ogólnym przypadku najmniejszym takim ułamkiem właściwym jest 26/4987 (a+b=5013).

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Roślinny kabaret Richarda Mabeya, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Elżbieta Jakubowska z Warszawy, Paweł Majewski z Trzcianki, Michał Miodek z Książenic, Janusz Włodarczyk z Będzina, Grzegorz Ząbkowicz z Krakowa.

***

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.