2^n начинается на n

[maxal]

Найти натуральные числа $n$ (хотя бы алгоритмически) такие, что десятичная запись числа $2^n$ начинается на $n.$

Например, известно такое решение: $n=72780032758751764.$ (см. A100129)
Можете ли вы найти еще большее решение?

[нг]

Могу предложить только меньшее: $6$.

[Dandan]

а что, в этом есть какой-то скрытый смысл?

[maxal]

А что в большинстве остальных задач есть скрытый смысл?
Вообще-то я задал вполне конкретный вопрос и не давал повода для философствования. Так что, высказывайтесь, пожалуйста, по существу задачи.

[RIP]

Прошу прощения, что не по теме, но в связи с этой задачей предлагаю такую задачку.
Доказать, что множество чисел $n$, удовлетворяющих условию, имеет нулевую плотность. Т.е. если обозначить через $A(N)$ количество искомых чисел $n\leqslant N$, то

$$\lim_{N\to\infty}\frac{A(N)}N=0.$$

Upd. Не, эта задача тривиальна. Лучше докажите, что ряд $\sum\frac1n$, где суммирование идёт по всем искомым $n$, сходится.

[juna]

maxal писал(а):

Найти натуральные числа $n$ (хотя бы алгоритмически) такие, что десятичная запись числа $2^n$ начинается на $n.$

Например, известно такое решение: $n=72780032758751764.$
Можете ли вы найти еще большее решение?

Maxal, мне кажется, вы ошибаетесь. У числа $2^{72780032758751764}$ первая цифра 1.

[RIP]

Артамонов Ю.Н. писал(а):

Maxal, мне кажется, вы ошибаетесь. У числа $2^{72780032758751764}$ первая цифра 1.

Странно. Мой калькулятор говорит, что maxal не ошибается.

[juna]

Xм, не посмотрел, что у результата еще $10^{16}$. Так, что все верно. Sorry! Excuse me.

[maxal]

Артамонов Ю.Н. писал(а):

Maxal, мне кажется, вы ошибаетесь. У числа $2^{72780032758751764}$ первая цифра 1.

PARI/GP утверждает следующее:

? 10^frac(72780032758751764*log(2)/log(10))
%1 = 7.2780032758751764578243794275606385634

Первые цифры результата в точности есть $72780032758751764.$

Добавлено спустя 3 минуты 14 секунд:

Артамонов Ю.Н. писал(а):

Дробная часть $n\lg2$ равна примерно 0.19, это меньше $\lg 2=0.3$

Она равна

? frac(72780032758751764*log(2)/log(10))
%2 = 0.86201224672894597707947155016544593664

[Руст]

По сути надо найти такие n, чтобы дробная часть $\{nlg2-lgn\}<\frac{1}{nln(10)}+O(\frac{1}{n^2}).$
Соответственно можно показать, что имеется бесконечно много таких n.

[maxal]

Руст писал(а):

По сути надо найти такие n, чтобы дробная часть $\{nlg2-lgn\}<\frac{1}{nln(10)}+O(\frac{1}{n^2}).$
Соответственно можно показать, что имеется бесконечно много таких n.

Прошу, маэстро!

[Руст]

Пусть $lg2=\frac{P_k}{Q_k}+\frac{\theta }{Q_kQ_{k+1}},|\theta |<1$ соответствующие приближения, получаемые из непрерывных дробей. Тогда n можно искать в виде $n=Q_k+m.$
Это дает $\{nlg2-lgn\}=\{\frac{mP_k}{Q_k}-lg(Q_k+m)+\frac{\theta (1+m/Q_k)}{Q_{k+1}}\}<\frac{1}{\ln{10} (Q_k+m)}.$
Легко добиться того, чтобы первые два слагаемых были малы. Однако нам нужны более точные приближения из-за ln(10)>2. Если бесконечно много частных дробей больше некоторого числа порядка 6-7 то между $(0<m<Q_{k+1}-Q_k=(q_k-1)Q_k+Q_{k-1}$ можно подобрать m удовлетворяющее этому свойству.

[RIP]

Руст писал(а):

Легко добиться того, чтобы первые два слагаемых были малы.

Никак не могу понять, как это сделать. Не мог бы кто-нибудь объяснить.

[Руст]

Задача эквивалентно
(1) $\{nlg2-lgn\}<lg(1+\frac{1}{n})=\frac{1}{nln{10}}+O(\frac{1}{n^2}).$
Будем искать решение в интервале
(2) $Q_k\le n<Q_{k+1}$.
Тогда можно искать n в виде $n_1+n_2, n_2<\sqrt n$. Фиксируя первое слагаемое находим
(3) $n=P_k^{-1}([lg(n_1)Q_k ]+ l), l<\sqrt n$
Примерно из $\sqrt n $ решений $\{nlg2 -lgn\}<\frac{1}{\sqrt n}$ находим самую точную, удовлетворяющую (1). Не в каждом интервале (2) такое решение найдётся. Вообще строгое доказательство существования бесконечного числа решений (1) является трудной задачей (ни такой простой, как казалось мне вначале). Поэтому, я изложил только идеи как найти такие числа.

[maxal]

Robert Gerbicz пояснил, как числа порядка $72780032758751764$ можно найти с помощью метода встречи посередине.

Предположим, что мы ищем число n длиной в $D$ десятичных цифр, которое удовлетворяет неравенству:

$$\{\log_{10} n\} \leq \{n\cdot \log_{10}2\} < \{\log_{10}(n+1)\},$$

где $\{\dots \}$ обозначает дробную часть.
Разобьем цифры $n$ на две группы примерно одинаковой длины: $n=k\cdot 10^d + m$, где $d\approx \frac{D}{2}$ и $0\leq m< 10^d$.
Тогда мы, во-первых немного ослабим неравенство, исключив из оценок $m$:

$$\{\log_{10} k\} \leq \{\log_{10} n\} \leq \{n\cdot \log_{10}2\} < \{\log_{10}(n+1)\} < \{\log_{10}(k+1)\},$$

а во-вторых, заметим, что

$$\{n\cdot \log_{10}2\} = \{k\cdot 10^d\cdot \log_{10}2\} + \{m\cdot \log_{10}2\}-1?,$$

где ? указывает на возможный, но не обязательный член.

Итак имеем:

$$\{\log_{10} k\} - \{k\cdot 10^d\cdot \log_{10}2\} + 1? \leq \{m\cdot \log_{10}2\} < \{\log_{10}(k+1)\} - \{k\cdot 10^d\cdot \log_{10}2\} + 1?.$$

Теперь идея состоит в том, чтобы составить таблицу всех возможных $m$, упорядоченных по величине $\{m\cdot \log_{10}2\}$. Тогда для каждого $k$ мы быстро сможем найти по этой таблице подходящие $m$ (удовлетворяющие последнему неравенству), если такие существуют, скомбинировать их в $n$ и уже строго проверить, является ли оно решением.
Таким образом задача сводится к перебору порядка $10^{D/2}$ различных значений $k$.