Collatz inaczej

[mol_ksiazkowy]

Niech \(\displaystyle{ a_0=1 }\) oraz \(\displaystyle{ a_{n+1}= \begin{cases} \frac{a_n}{2} & \text{gdy } a_n \text{ parzyste} \\ a_ n+d & \text{gdy } a_n \text{ nieparzyste} \end{cases} }\)
Wyznaczyć dla jakich \(\displaystyle{ d}\) istnieje \(\displaystyle{ n>0}\) takie, że \(\displaystyle{ a_n =1 }\)

[Gosda]

Wszystkie nieparzyste. Na przykład dla \(d = 25\) mamy \(a_{30} = 1\) i \(a_k \neq 1\) dla \(k = 1, 2, \ldots, 29\). Wygląda na to, że wartość \(d\) można znaleźć tutaj:

Kod: Zaznacz cały

https://oeis.org/A165783

[Dasio11]

Rzeczywiście: niech \(\displaystyle{ d}\) będzie dowolną liczbą nieparzystą. Najpierw wykażemy, że istnieją \(\displaystyle{ k, n \in \NN \setminus \{ 0 \}}\), takie że \(\displaystyle{ k \cdot d = 2^n-1}\). Istotnie, zbiór \(\displaystyle{ \{ 2^i \bmod{d} : i \in \NN \}}\) jest ograniczony, więc \(\displaystyle{ 2^i \equiv 2^j \pmod{d}}\) dla pewnych \(\displaystyle{ i < j}\). Wtedy \(\displaystyle{ d \mid 2^{j-i}-1}\) z uwagi na nieparzystość \(\displaystyle{ d}\) i wystarczy przyjąć \(\displaystyle{ n = j-i}\).

Niech \(\displaystyle{ k = 2^{n_1} + 2^{n_2} + \ldots + 2^{n_p}}\), gdzie \(\displaystyle{ n_1 < n_2 < \ldots < n_p < n}\). Ponieważ \(\displaystyle{ k}\) jest nieparzyste, zatem \(\displaystyle{ n_1 = 0}\). Mamy więc

\(\displaystyle{ 1 + d \cdot \left( 1 + 2^{n_2} + \ldots + 2^{n_p} \right) = 2^n.}\)

Stąd kolejno:

\(\displaystyle{ 1+d = 2^n - d \cdot \left( 2^{n_2} + \ldots + 2^{n_p} \right)}\) jest liczbą parzystą;

\(\displaystyle{ \frac{1+d}{2^{n_2}} = 2^{n-n_2} - d \cdot \left( 1 + 2^{n_3-n_2} + \ldots + 2^{n_p-n_2} \right)}\) jest liczbą całkowitą nieparzystą;

\(\displaystyle{ \frac{1+d}{2^{n_2}}+d = 2^{n-n_2} - d \cdot \left( 2^{n_3-n_2} + \ldots + 2^{n_p-n_2} \right)}\) jest liczbą parzystą;

\(\displaystyle{ \frac{\frac{1+d}{2^{n_2}}+d}{2^{n_3-n_2}} = 2^{n-n_3} - d \cdot \left( 1 + 2^{n_4-n_3} + \ldots + 2^{n_p - n_3} \right)}\) jest liczbą całkowitą nieparzystą;

i tak dalej. Widać zarazem, że wypisane powyżej liczby będą kolejno występować jako elementy rozpatrywanego ciągu. Wreszcie jednym z wyrazów będzie

\(\displaystyle{ \cfrac{\stackrel{\cfrac{\cfrac{\cfrac{1+d}{2^{n_2}}+d}{2^{n_3-n_2}}+d}{2^{n_4-n_3}} \Large \: + \: d \qquad}{\ddots}}{2^{n_p-n_{p-1}}} + d = 2^{n - n_p}}\)

i po kilku kolejnych dzieleniach otrzymamy jako wyraz ciągu jedynkę, co kończy dowód.