Докажите, без логарифмов

[qwert129]

Пусть $S(m)$ — это сумма цифр числа $m$. Докажите, без понятии логарифмов, что существует бесконечно много натуральных $k$ таких, что $S(2^k)\ge S(2^{k+1})$

[wrest]

Интересная задача. Подсчет говорит о том, что для $k$ от одного до $10^4$ нет таких, что $S(2^k) = S(2^{k+1})$

[gris]

да они все равны одному!

[Утундрий]

(Оффтоп)

Докажите с завязанными глазами...

[Drimacus]

А можно поточнее что значит "без логарифмов"? Потому что плохо понятен этот запрет в контексте суммы цифр. Как и в принципе чем продиктован этот запрет, ну, кроме желания левой пятки и искусственно усложнить и без того не очень простой вопрос.

[qwert129]

Ну я примерно знаю решение, и там используется логарифмы, хотелось бы без логарифмов увидеть решение.
Логарифм использовался в следующем факте, пусть $10^{k-1}<2^n<10^k$, тогда $k>nlg2$

-- 17.01.2024, 10:27 --

wrest в сообщении #1626189 писал(а):

Интересная задача. Подсчет говорит о том, что для $k$ от одного до $10^4$ нет таких, что $S(2^k) = S(2^{k+1})$

Это вроде верно изза факта что $2^n$ не делится на $9$, иначе $2^{n+1}-2^n=S(2^{n+1})-S( 2^n)=0\pmod 9$

[Drimacus]

Хм, цикл остатков по модулю 9 в точности совпадает для $2^n$ и $S(2^n)$ (это 2,4,8,7,5,1). Получается, что если последовательность сумм цифр монотонна с какого-то момента, то для всех очень больших чисел сумма будет почти линейной не хуже $9m+r$, $r$ это наши остатки, а раз так, то мы получаем набор оценок:
$S(2^n) = 9m+2, S(2^{n+1})=9m+4,S(2{n+2})=9m+8,S(2^{n+3})=9m+16,S(2^{n+4})=9m+23,S(2^{n+5})=9m+28,S(2^{n+6})=9m+33$, т.е. отсюда рост не меньше чем на $31$ за умножение на $2^6$, а это ощутимо опережает темпы роста суммы цифр, которая не может быть больше $2.7$ на разряд в среднем, т.е. на $2^6$ это вообще не больше $5.4$. Противоречие с максимальной скоростью роста суммы цифр степени двойки.
Если я не ошибся нигде, то вроде бы это (почти) доказывает немонотонность суммы цифр двойки?

-- 17.01.2024, 09:14 --

А без логарифмов не знаю как, мне кажется, никак, потому что какую-то оценку на сумму цифр делать в любом случае надо, а это по сути логарифмы и есть.

[TOTAL]

Если $2^k = 4 \mod 9$, то $2^{k+3} = 5 \mod 9$.
Если $2^k = 5 \mod 9$, то $2^{k+3} = 4 \mod 9$.
Предположив, что сумма цифр при каждом удвоении росла, получаем, что при умножении на $2^6=64$ сумма цифр выросла по крайней мере на $10+8=9+9$. Разрядов в числе не хватит для такого постоянного роста суммы цифр.

[Cash]

Drimacus в сообщении #1626259 писал(а):

А без логарифмов не знаю как, мне кажется, никак, потому что какую-то оценку на сумму цифр делать в любом случае надо, а это по сути логарифмы и есть.

Да не нужны там логарифмы. Доказанного хватает, чтобы оценивать плюс-минус километр.
С одной стороны, если начиная с некоторого $n_0$ сумма цифр монотонна - $S(2^{n_0+6i}) > 31i$,
С другой стороны, $S(2^{n_0+6i}) < 9k_0 + 18i$, где $k_0$ - количество цифр числа $2^{n_0}$
т.к. каждый следующий член длиннее не более чем на 2 цифры: $2^{n+6}= 64 \cdot 2^n < 100\cdot 2^n$

[Drimacus]

Cash в сообщении #1626402 писал(а):

Drimacus в сообщении #1626259 писал(а):

А без логарифмов не знаю как, мне кажется, никак, потому что какую-то оценку на сумму цифр делать в любом случае надо, а это по сути логарифмы и есть.

Да не нужны там логарифмы. Доказанного хватает, чтобы оценивать плюс-минус километр.
С одной стороны, при условии монотонности суммы цифр с некоторого $n_0$: $S(2^{n_0+6i}) > 31i$,
С другой стороны, $S(2^{n_0+6i}) < 9k + 18i$, где $k$ - количество цифр числа $2^{n_0}$
т.к. каждый следующий член длиннее не более чем на 2 цифры: $2^{n+6}= 64 \cdot 2^n < 100\cdot 2^n$

Да, спасибо, это то, что я и имел в виду в своем рассуждении, но сказанное более аккуратно.