XLVII OM - III - Zadanie 5

Dla liczby naturalnej $ k \geq 1 $ oznaczmy przez $ p(k) $ najmniejszą liczbę pierwszą, która nie jest dzielnikiem liczby $ k $. Jeśli $ p(k) > 2 $, to przyjmujemy, że $ q(k) $ jest iloczynem wszystkich liczb pierwszych mniejszych od $ p(k) $; gdy zaś $ p(k) = 2 $, to przyjmujemy $ q(k) = 1 $. Określamy ciąg $ (x_n) $ wzorami:

\[<br />
x_0 = 1, \quad x_{n+1} = \frac{x_n p(x_n)}{q(x_n)} \text{ dla } n = 0,1,2,\ldots .<br />
\]

Wyznaczyć wszystkie liczby naturalne $ n $, dla których zachodzi równość $ x_n = 111111 $.

Rozwiązanie

Niech $ p_0 = 2 $, $ p_1 = 3 $, $ p_2 = 5 $, $ p_3 = 7 $, $ \ldots $ będzie rosnącym ciągiem wszystkich liczb pierwszych. Wyrazy rozważanego w zadaniu ciągu $ (x_n) $ dadzą się scharakteryzować przez cyfry zapisu wskaźnika $ n $ w dwójkowym układzie pozycyjnym. Wykażemy mianowicie, że dla $ n \geq 1 $ zachodzi implikacja:

\[<br />
(*) \qquad \textrm{jeżeli} \ n=\overline{c_m c_{m-1}\ldots c_1c_0} = \sum_{i=0}^m c_i 2^i \quad (c_i \in \{0,\ 1\}),\ \textrm{to}\ x_n = \prod_{i=0}^m p^{c_i}_i.<br />
\]

Dla $ n = 1 $ jest to prawda ($ x_1 = x_0 p(x_0)/q(x_0) =p(1)/q(1) = 2 = p_0 $).

Przyjmijmy słuszność zdania (*) dla pewnej liczby naturalnej $ n \geq 1 $. Jeżeli $ n $ jest liczbą parzystą, to $ c_0 = 0 $, więc

\[<br />
n=\sum_{i=1}^m c_i 2^i \quad \textrm{oraz} \quad x_n=\prod_{i=1}^m p^{c_i}_i.<br />
\]

Zatem $ p(x_n) = 2 $, $ q(x_n) = 1 $, i zgodnie z podanym wzorem rekurencyjnym: $ x_{n+1} =2x_n $. Tak więc

\[<br />
n+1 =2^0 + \sum_{i=1}^m c_i2^i, \quad x_{i+1}=p_0 \cdot \prod_{i=1}^m p^{c_i}_i;<br />
\]

reguła (*) zachowuje słuszność dla $ n + 1 $.

Jeżeli natomiast $ n $ jest liczbą nieparzystą, to $ c_0 = 1 $. Załóżmy, że zapis dwójkowy liczby $ n $ nie składa się z samych jedynek (przypadek, gdy tak jest, rozpatrzymy za chwilę). Niech $ j $ będzie najmniejszym numerem, dla którego $ c_j =0 $. To znaczy, że

\[<br />
n = \overline{c_m c_{m-1} \ldots c_{j+1} 0 \underbrace{11 \ldots 11}_{j} } = \sum_{i=0}^{j-1} 2^i + \sum_{i=j+1}^m c_i 2^i.<br />
\]

Reguła (*) (która w myśl założenia indukcyjnego zachodzi dla rozważanej liczby $ n $) daje równość

\[<br />
x_n = \prod_{i=0}^{j-1} p_i \cdot \prod_{i=j+1}^m p^{c_i}_i.<br />
\]

Zatem $ p(x_n) =p_j $, $ q(x_n)=\prod_{i=0}^{j-1} p_i $. Liczby $ n+ 1 $ oraz $ x_{n+1} $ mają więc przedstawienia:

\[<br />
n+1 = \overline{c_m c_{m-1} \ldots c_{j+1}1 \underbrace{00\ldots 00}_j}= 2^j + \sum_{i=j+1}^{m} c_i 2^i,<br />
\]
\[<br />
x_{n+1} = \frac{x_n}{q(x_n)} \cdot p_j = p_j \cdot \prod_{i=j+1}^m p^{c_i}_i;<br />
\]

także i w tym przypadku reguła (*) jest słuszna dla $ n + 1 $.

Pozostała do rozpatrzenia sytuacja, gdy w przedstawieniu dwójkowym liczby $ n $ są same jedynki:

\[<br />
n=\overline{\underbrace{11\ldots11}_{m+1}} = \sum_{i=0}^m 2^i.<br />
\]

Zgodnie z założeniem indukcyjnym (*) oraz z podanym wzorem rekurencyjnym mamy teraz:

\[<br />
x_n=\prod_{i=0}^m p_i, \quad p(x_n)=p_{m+1}, \quad q(x_n)=\prod_{i=0}^m p_i = x_n.<br />
\]

Zatem

\[<br />
x_{n+1} = \frac{x_n}{q(x_n)} \cdot p_{m+1} = p_{m+1}; \quad \textrm{jednocześnie} \ n +1 = 2^{m+1}.<br />
\]

Jak widać, również w takim przypadku reguła (*) zachowuje słuszność dla $ n+1 $.

Na mocy zasady indukcji implikacja (*) zachodzi dla wszystkich liczb naturalnych $ n \geq 1 $.

Różne liczby $ n $ mają różne rozwinięcia dwójkowe. Wynika stąd (wobec charakteryzacji ($ * $)), że w ciągu $ (x_n) $ żadna liczba nie powtarza się. Pozostaje zauważyć, że w rozkładzie na czynniki pierwsze liczba $ 111111 $ ma postać iloczynu $ 3\cdot 7\cdot 11 \cdot 13 \cdot 37 $, czyli spełnia równość $ 111111 = p_1p_3p_4p_5p_{11} $. Stąd wniosek, że dla liczby $ n = 2^1 + 2^3 +2^4 + 2^5 + 2^{11} = 2106 $, i tylko dla niej, zachodzi równość $ x_n = 111111 $.

Uwaga: Z przeprowadzonego rozumowania wynika, że w ciągu $ (x_n) $ występują wszystkie dodatnie liczby całkowite bezkwadratowe, to znaczy nie dzielące się przez kwadrat żadej liczby pierwszej; innymi słowy, mające rozkład na iloczyn różnych czynników pierwszych; przy tym każda taka liczba pojawia się w tym ciągu dokładnie raz.

Wzór rekurencyjny, generujący ów ciąg, naśladuje algorytm dodawania jedynki w dwójkowym układzie pozycyjnym. Do zauważenia tego faktu oraz jego precyzyjnego opisu sprowadza się powyższe rozwiązanie.

Komentarze

Dodaj nową odpowiedź