XLVII OM - III - Zadanie 5

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

III

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:

$ x_0 = 1, \quad x_{n+1} = \frac{x_n p(x_n)}{q(x_n)} \text{ dla } n = 0,1,2,\ldots . $

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:

$ (*) \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. $

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

$ n=\sum_{i=1}^m c_i 2^i \quad \textrm{oraz} \quad x_n=\prod_{i=1}^m p^{c_i}_i. $

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

$ 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; $

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

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

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

$ x_n = \prod_{i=0}^{j-1} p_i \cdot \prod_{i=j+1}^m p^{c_i}_i. $

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:

$ 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, $

$ x_{n+1} = \frac{x_n}{q(x_n)} \cdot p_j = p_j \cdot \prod_{i=j+1}^m p^{c_i}_i; $

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:

$ n=\overline{\underbrace{11\ldots11}_{m+1}} = \sum_{i=0}^m 2^i. $

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

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

Zatem

$ 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}. $

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.