Первые цифры степени

[august_month]

Could you help with the following problem realated to equidistribution of numbers?

Prove that for every finite sequence
of digits c1c2...ck with c1not equal ot 0, there is a
positive integer n such that the decimal expansion
of 2^n starts with the given sequence of digits
2^n = c1c2...ck.... For example 2^1939 = 1945... (582
digits), starts with the date of the end of the Second
World War.

Spasibo!

[maxal]

Let C = c_1c_2\dots c_k, \alpha = \log_{10} 2, \beta_1 = \log_{10} C, \beta_2 = \log_{10}(C+1)

It's enough to find a good approximation to \beta modulo 1 with multiples of \alpha, i.e., integers m and n such that
n\alpha - m belongs to the interval (\beta_1, \beta_2) (according to Kronecker's Approximation Theorem there are infinitely many such approximations).
Then 2^n belongs to the interval (C 10^m, (C+1) 10^m) meanning that 2^n starts with digits c_1c_2\dots c_k.

From the above we can say even more. In the sequence 2^n numbers starting with digits c_1c_2\dots c_k appear with the frequence $\beta_2 - \beta_1 = \log_{10}\frac{C+1}{C}\approx \frac{1}{C\ln{10}}$.

[Edward_Tur]

Пускай $a > 1$ - натуральное число, не делящееся на 10. Выберем из последовательности степеней $a^1 ,a^2 ,a^3 , \ldots $ все числа, начинающиеся с цифры $k$; пусть эти числа (по порядку) $a^{f_a^k (1)} ,a^{f_a^k (2)} ,a^{f_a^k (3)} , \ldots $. Например, $f_2^2 (2) = 8$ поскольку $2^1 = 2$, $2^8 = 256$; $f_3^2 (3) = 7$, поскольку $3^3 = 27$, $3^5 = 243$, $3^7 = 2187$. Найти точное значение $f_a^k (n)$.
Например, $f_3^9 (n)$ при $n > 1$ однозначно определяется из условий:
а) разность $f_3^9 (n) - n$ нечётна;
б) $\left| {f_3^9 (n) - \frac{{n - \lg 9}}{{1 - \lg 9}}} \right| < 1$.

[juna]

Должно выполняться очевидное неравенство:
$\forall n: f_a^k(n)\lg a-\lfloor f_a^k(n)\lg a\rfloor\leqslant \lg (k+1)-\lg(k)$.

Чтобы определить зависимость от $n$, нужно считать, сколько раз это неравенство выполняется.
Но это, конечно, не то, что нужно найти.

[maxal]

А есть ли у автора простой ответ для случая, когда $k$ не является степенью $a$ (и особенно, если $\ln k$ и $\ln a$ несоразмеримы)?

[juna]

Кстати, нашел, что количество решений хорошо выражается: в промежутке до $10^t$ имеется примерно $n\approx 10^t(\lg(k+1)-\lg(k))$ решений.
Соответственно, для всех $f_a^k(n)=10^t$ критерий получается похож на приведенный автором:
$\left| f_a^k(n)-\frac{n}{\lg(k+1)-\lg(k)}\right |<1$

[maxal]

$a^m$ начинается цифры $k$, если дробная часть $m\log_{10} a$ находится в полуинтервале $[\log_{10} k, \log_{10} (k+1)).$ Причем так как $a$ не делится на $10$, то полуинтервал можно заменить интервалом.

Получаем, что $f_a^k(n)=m$ тогда и только тогда, когда $\left\{m\log_{10} a\right\}$ находится в интервале $(\log_{10} k, \log_{10} (k+1))$ и число решений неравенства

$$\left|x\log_{10} a - y - \frac{\log_{10}k+\log_{10}(k+1)}{2}\right|< \frac{\log_{10}(k+1)-\log_{10}k}{2}$$

в целых числах $x,y$, где $0\leq y$ и $1\leq x\leq m$, равно $n$.

Это же неравенство можно переписать в виде

$$\left|\frac{2x\log_{10} a - 2y - \log_{10} k - \log_{10}(k+1)}{\log_{10}(k+1) - \log_{10}k} \right|< 1.$$

Когда логарифмы $k$ и $a$ соразмеримы, все здорово сокращается и упрощается. Как например, для $a=3$ и $k=9$:

$$\frac{x\log_{10} 9 - 2y - \log_{10} 9 - 1}{1 - \log_{10}9} = \frac{(x-1)\log_{10} 9 - (2y + 1)}{1 - \log_{10}9}=\frac{(x - 1) - (2y + 1)}{1 - \log_{10}9}-(x-1)$$

и из этого уже можно находить явный вид функции $f_a^k(n)$. Но что делать в общем случае - непонятно.