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

Задача из журнала «Квант» (1995, выпуск №4)

Пусть [latex]c_{n}[/latex] — первая цифра числа [latex]2^{n}[/latex] (в десятичной записи).

  1. Сколько единиц среди первых 1000 членов этой последовательности?
  2. Докажите, что в последовательности
    $$ c_{1}=2, \quad c_{2}=4, \quad c_{3}=8, \quad c_{4}=1, \quad c_{5}=3, \quad… $$

    встретится ровно 57 различных «слов» [latex]c_{k}c_{k+1}…c_{k+12}[/latex] длины 13.

Решение

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

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

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

  2. line

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

    log_circle

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

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

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

    Пусть

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

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

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

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

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

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

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

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

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

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

Ответ:

  1. 301.
  2. Число различных «слов» длины [latex]n[/latex] задается формулой [latex] 4n+5 [/latex]. В частности, при [latex]n=13[/latex] получим ответ:   [latex]4 \cdot 13+5=57.[/latex]
А.Васильев, А.Канель

М1473. О записи степеней двойки: 2 комментария

Добавить комментарий для Igor Mazurok Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *