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

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

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

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

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

Решение

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

  3. Чтобы более детально разобраться в закономерностях последовательности 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).

    log_circle

    Прежде чем решать задачу (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=213). В частности, при 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}.

Ответ:

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

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

Добавить комментарий

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