М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] цифр встречается в нашей последовательности. Читать далее «М1473. О записи степеней двойки»