М1473. О записи степеней двойки

Решение

1. Отметим на «логарифмической шкале» $y=\log_{10}{x}$ числа $x=2^{n}$ (каждая следующая отметка получается из предыдущей сдвигом на расстояние   $\log_{10}{2}$). Число $x$ начинается с $1$, если   $10^{k} \le x < 2 \cdot 10^{k+1}$   для некоторого $k$; соответствующие интервалы на рисунке 1 выделены красным (поскольку длина интервала как раз равна   $\log_{10}{2}$, на каждый из них попадает ровно одна отметка). Поскольку

   $$\log_{10}{2} = 0.30103…, \quad 10^{301} \le 2^{1000} < 10^{302},$$

   так что   $2^{n}(n=0,1,2,…,1000)$   ровно 301 раз перейдет через степень $10$ и поэтому (не считая $2^{0}=1$) 301-ый её член начинается с 1.



2. Чтобы более детально разобраться в закономерностях последовательности $c_{n}$, свернем логарифмическую шкалу $y=\log{10}{x}$ в «логарифмический круг» $z=y-\left[ y \right]$: каждый отрезок от $10^k$ до $10^{k+1}$ даёт новый оборот круга, а точки $0=\log_{10}{1}, \quad \log_{10}{2}, \quad \log_{10}{3}, \quad …, \quad \log_{10}{9}$ — границы интервалов, в которых расположены значения z, соответствующие различным первым значащим цифрам числа $x$ от $1$ до $9$ (см. рисунок 2).

   

   Прежде чем решать задачу $(2)$, объясним идею рассуждения на более простом примере: выясним, сколько разных пар $\left( c_{k}, c_{k+1} \right)$ цифр встречается в нашей последовательности.

   (Конечно, ответ — $13$ — можно получить и простым перебором.) Мы должны выяснить, во сколько разных пар из $9$ интервалов   $1,…,9$   попадают пары точек   $z,z+\log_{10}{2}$   окружности (конечно, здесь сумма берется «по модулю 1», т.е. $z+\log_{10}{2}$ — точка, получающаяся из $z$ «поворотом» на $\log_{10}{2}$). Для этого достаточно к $9$ точкам деления   $0,\quad \log_{10}{2}, \quad \log_{10}{3}, \quad …, \quad \log_{10}{9}$   на окружности добавить еще те, при прибавлении к которым $\log_{10}{2}$ получается одна из этих $9$ точек деления (новые точки деления на рисунке показаны красным). Тогда окружность разобьётся на более мелкие интервалы $\Delta$ так, что для всех $z$ из каждого $\Delta$ пара   $z, z+\log_{10}{2}$   попадает в одну и ту же пару интервалов   $1,…,9$,   а $z$ из разных $\Delta$ дают разные пары цифр.

   Точно так же можно разобраться со «словами» любой длины.

   Пусть

   $$R: z \rightarrow z+\log_{10}{2}\left(\text{mod 1}\right)$$

   — поворот окружности, соответствующий уможению на   $2: x \rightarrow 2x; \quad L=R^{-1}$ — обратное к $R$ преобразование   $z \rightarrow z-\log_{10}{2} \left(\text{mod 1}\right)$.   Чтобы проследить, в какие именно интервалы могут попадать последовательности точек длины 13

   $$z, \quad Rz, \quad …,\quad R^{12}z$$

   — т.е. какие возможны последовательности цифр

   $$c_{k}c_{k+1}…c_{k+12}$$

   — достаточно выяснить, на сколько интервалов будет разбит круг точками

   $$\log_{10}{k}, \quad L\left(\log_{10}{k}\right), \quad …, \quad L^{12} \left(\log_{10}{k}\right),$$

   где   $k=1,2,…,9$.   Для точек $z$ из каждого интервала $\Delta$ между этими точками получится своя последовательность «номеров». Заметим, что поскольку

   $$L\left(\log_{10}{2}\right)=0, \quad L\left(\log_{10}{4}\right)=\log_{10}{2}, \quad L\left(\log_{10}{6}\right)=\log_{10}{3}\\L\left(\log_{10}{8}\right)=\log_{10}{4}, \quad L\left(\log_{10}{1}\right)=\log_{10}{5}$$

   (ведь   $\log_{10}{1}$   на окружности совпадает с   $\log_{10}{10}$), то среди точек   $L\left(\log_{10}{k}\right)$   появляются лишь четыре новых

   $$L\left(\log_{10}{3}\right)=\log_{10}{\frac{3}{2}}, \quad L\left(\log_{10}{5}\right)=\log_{10}{\frac{5}{2}},\\ L\left(\log_{10}{7}\right)=\log_{10}{\frac{7}{2}},\quad L\left(\log_{10}{9}\right)=\log_{10}{\frac{9}{2}},$$

   отмеченных на рисунке красным цветом; точно так же, среди точек $L^{n+1}\left(\log_{10}{k}\right)$ по сравнению с   $L^{j}\left(\log_{10}{3}\right)\left(j=0,1,…,n\right)$   появляется лишь четыре новых, соответствующих   $k=3,5,7,9.$ Таким образом, среди точек

   $$L^{i}\left(\log_{10}{k}\right),\quad 0 \le i < n, \quad 1 \le k \le 9$$

   будет всего $4n+5$ различных (при $n=1$ их число равно $9$, при $n=2$ — $13$). В частности, при $n=13$ получим ответ:   $4 \cdot 13+5=57.$

   Осталось заметить, что последовательность точек $z_{n}$, соответствующих числам $2^{n}$ будет «всюду плотной на окружности» — это следует из иррациональности $\log_{10}{2}$ (если бы некоторый интервал $\delta$ был свободен от точек $z_{n}$ — мы могли бы выбрать его максимальным влево и вправо, — то интервалы   $\delta, R \delta, R^{2} \delta, …$ не могли бы пересекаться). Значит, в каждом интервале $\Delta$ будет хоть одна точка $z_{n}$.