Сумма цифр степени

[Tookser]

Пусть $P(n)$ - сумма цифр натурального числа n.
Доказать, что $\lim\limits_{n \to \infty, n \in \mathbb{N}}{P(2^n)} = \infty$

[Утундрий]

Странно, а у меня предел равен единице. К чему бы это?..

[provincialka]

(Оффтоп)

Утундрий
Видимо, к двоичной системе счисления

[atlakatl]

А это действительно "олимпиадная" задача? В сущности, предлагается доказать нормальность любой достаточно большой степени двойки.
Попробовал посчитать $P(2^n)$ от нуля до $36$:

[Руст]

Ничего сложного нет. К тому же задача неоднократно предлагалась, думаю, что и здесь решалась однажды.

[worm2]

М-да, сложного-то, вроде, нет, но что-то такие тяжеловесные рассуждения получаются, что самого оторопь берёт.

Для любого $k$ последовательность \{$(a_k)_n\}=\{2^n \pmod{10^k}\}$ становится периодической по $n$, начиная с какого-то номера $n=n(k)$, с периодом $p(k)$ (ну это легко доказывается, по Дирихле она хоть один раз, да повторится, а дальше никуда не денется с подводной лодки). Значит, начиная с этого номера периодической будет и последовательность сумм $k$ последних цифр $\{2^n\}$ (возможно, с меньшим периодом).

Пусть максимальная сумма последних $k$ цифр в этом бесконечном периодическом хвосте равна $M(k)$. Далее идём от противного. Если утверждение задачи неверно, то последовательность $\{M(k)\}$ тем более ограничена сверху числом $M(K)$ (которое достигается при некотором $k=K$). Поскольку, очевидно, $M(k)$ не убывает при росте $k$, то это значит, что $M(k)=M(K)$ для всех $k>K$.

В свою очередь, отсюда следует, что для тех номеров $n$, которые реализуют максимум суммы последних $k>K$ цифр в бесконечном периодическом хвосте $\{(a_k)_n\}$, десятичная запись $2^n$ содержит только нули в разрядах $K+1$, $K+2$, ..., $k$. Однако отсюда с необходимостью следует, что период $p(k)=P(K)$ для всех $k>K$ (один раз повторившись через $p(K)$ членов, никуда последовательность уже не денется).

И вот тут в наши сети наконец попадается долгожданное противоречие. Ведь эти нули являются результатом переноса из нижних $K$ разрядов при последовательном сложении (надеюсь, все держат в памяти, что в последовательности $\{2^n\}$ каждый последующий член является суммой предыдущего с самим собой?). Взяв достаточно большое $k$, мы можем добиться, чтобы $p(K)$ членов было недостаточно, чтобы в результате переносов из этих разрядов во всех разрядах $K+1$, $K+2$, ..., $k$ снова появились сплошные нули (для этого требуется по крайней мере один перенос из $k$-го разряда, а $k$ в наших руках, в то время как период $p(k)=p(K)$ фиксирован).

[Null]

Число $2^n $может начинаться на $99999$ это не сложно показать.

[atlakatl]

worm2, спасибо.
Для себя по результатам прочтения Вашего варианта вывел доказательство "на пальцах":
Для любого $k$ последовательность $\{$(a_k)_n\}=\{2^n \pmod{10^k}\}$$ становится периодической по $n$, начиная с какого-то номера $n=n(k)$, с периодом $p(k)$. Зафиксируем минимальную сумму цифр в этом периоде $S_m(n)$.
И продолжаем увеличивать степень. - Всякий раз проверяя, не увеличился ли период $p(k)$. Если в новом периоде $S_m(n)$ не увеличилась (самая левая цифра $0$), то просто идём дальше. Рано или поздно $S_m(n)$ увеличится. - И т.д. по индукции.

-- 20.02.2015, 21:50 --

Null в сообщении #980545 писал(а):

Число $2^n $может начинаться на $99999$ это не сложно показать.

Но всё равно будут степени, начинающиеся с $10000000...$, - именно по ним мы считаем промежуточный итог последовательности, а не по максимальным значениям.

[Руст]

Проще так. Если не стремится, то существует подпоследовательность, у которой сумма цифр ограничена некоторым числом.
Отсюда можно выбрать подпоследовательность, который заканчивается на некоторое число a, отличное от нуля, и далее сколь угодно много нулей.
Этого не может быть, так как это означает, что не равное нулю число a делится на какую угодно высокую степень двойки (используется что 10 делится на 2).
Более того $s(2^n)\ge [an], a=(lg(2))^2$.

[grizzly]

(Оффтоп)

Жаль, цитатник форума находится в юморной ветке. Я бы такие вот решения от Руст (или решение ИСН из соседней темы) собирал в специальном цитатнике.
Очень вдохновляет этот форум, где можно попытаться решить самому, потом увидеть, как это удалось сделать более сильным, восхититься и, заодно, оценить свои ошибки, чтобы попытаться ещё раз, в следующей попытке...

[ex-math]

Руст в сообщении #980573 писал(а):

Отсюда можно выбрать подпоследовательность, который заканчивается на некоторое число a, отличное от нуля, и далее сколь угодно много нулей.

Почему?

[Руст]

Имеется только конечный набор возможных расположений цифр (без нулей) с суммой цифр меньше заданного. Хотя бы один из таких наборов расположения встречается бесконечное число раз.
Имеется только конечное число возможностей разделить этот набор нулями.
Для какого то окончания получаем, что оно разделяется какого угодно большим количеством нулей от остальных цифр.

[Evgenjy]

Руст в сообщении #980668 писал(а):

Имеется только конечное число возможностей разделить этот набор нулями.

Имеется только конечное число возможностей разделить этот набор ограниченным числом нулей.

[Руст]

Пусть бесконечное число раз встречается набор ненулевых цифр $a_0,a_1,...,a_k$,
т.е. числа вида $a_0+a_1*10^{n_1}+...+a_k*10^{n_k}, 0<n_1<...<n_k$ представляют бесконечное число степеней двойки.
Если в разрыве между $n_1,0$ только конечное число возможностей, то для некоторого фиксированного значения $n_1$
имеется бесконечное число степеней двойки и т.д. Такие разрывы фиксируем и объединяем в одно окончание $A$.
После A встречаются как угодно большие разрывы, что означает, что не равное нулю число А делится на какую угодно большую степень двойки.

[Munin]

(Оффтоп)

grizzly в сообщении #980638 писал(а):

Жаль, цитатник форума находится в юморной ветке.

На самом деле, та ветка шире, чем юморная, и в "цитатнике" есть некоторое количество неюморных цитат. Хотя, конечно, для интересных задач и решений стоило бы выделить отдельную ветку...