Итерации с суммой цифр

[grizzly]

Навеяно другой темой про сумму цифр (точнее методом решения).

Задача.
Следующий член последовательности получается из предыдущего добавлением суммы цифр. Доказать, что число чётных членов бесконечно.

Эта задача присутствует в неоднократно упомянутом здесь сборнике монстров Белова (под №39) и я её оттуда же и процитировал. Я знал (и решил) её ещё до выпуска этого сборника и пару раз предлагал в фидошном румате -- со второй попытки её легко взяли.

У этой последовательности есть (это гипотеза) ещё одно замечательное свойство -- если стартовые члены двух разных последовательностей не делятся на 3, то их хвосты будут совпадать (для делящихся на 3 и на 9 имеются такие же гипотезы). У меня просьба -- если кто следил / знает современное состояние этой гипотезы, поделитесь, пжл, информацией.

[Руст]

Правильно я понял, что если $a_0=x, b_0=y, a_{i+1}=a_i+s(a_i), b_{i+1}=b_i+s(b_i)$, то найдутся $n\in N, k\in Z$, что
для любого $m>n$ выполняется $a_m=b_{m+k}$ при предположении, что $v_3(x)=v_3(y)\mod 3$.

[grizzly]

Да, правильно. На словах говорить о хвосте удобнее, а формулами можно чуть проще: достаточно, чтобы для некоторых $m, n \in N$ выполнилось $a_m=b_n$, а далее нужное обеспечит единый итерационный процесс.
Обозначение с $v_3$ мне не знакомо. Сам не соображу, как коротко записать то же -- уверен, что Вы правильно поняли.

-- 21.02.2015, 11:02 --

Подобные последовательности (с суммами цифр) возникают в прикладных задачах передачи информации, поэтому сколько-то активно изучаются. Но вот эту гипотезу когда-то высказали, а чем закончилось, я не могу найти. Сейчас никто не упоминает. Выглядит так, будто доказали и забыли, или бросили как безнадёжную (хотя вон $3n+1$ не бросают же).

-- 21.02.2015, 11:14 --

PS. Совет всем, кто вдруг заинтересуется. Не стоит много усилий тратить на компьютерный перебор для проверки гипотез, разве только чтоб прочувствовать задачу. Здесь с помощью элементарных (очень простых) соображений можно делать проверки сразу до очень больших чисел (как в Ван дер Варденовской гигантомании).

[grizzly]

Я подумал, что вдруг кому-то покажется интересной и такая простенькая задачка (ведь в ней тоже нужно какую-никакую нестандартную идею применить).

Подзадачка к гипотезе.
Проверить с помощью компьютерного перебора, что гипотезе удовлетворяют все числа (стартовые номера), меньшие $100^{(100^{100})}$ (или, в обозначениях быстрой степени, ${}^3 100$.)

Рассматриваем для определённости только не делящиеся на 3 стартовые номера. Понятно, что для решения достаточно только указать на правильную идею такой быстрой проверки.

[grizzly]

В качестве подсказки к основной задаче, поясню идею решения подзадачи к гипотезе (далее для сокращения текста рассматриваются только числа, не кратные 3):

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

Подзадачка к гипотезе.
Проверить с помощью компьютерного перебора, что гипотезе удовлетворяют все числа (стартовые номера), меньшие $100^{(100^{100})}$ (или, в обозначениях быстрой степени, ${}^3 100$.)

Идея очень простая: очевидно, что любое число $N<10^{10}$ через некоторое количество итераций станет числом вида $10^{10}+m$, где $m\le 80=9\cdot 9-1$. Наши итерации для числа $10^{10}+m$ это (очень долго) то же самое, что для числа $m$ итерации, в которых на каждом шаге добавляется сумма цифр плюс 1. Теперь несложно проверить (компьютерным перебором, конечно), что все числа от 0 до 80 через некоторое количество таких взвешенных итераций сольются в одной точке и дальше будут иметь общий хвост. Тем самым мы проверили гипотезу для всех чисел до $10^{10}$.

Дальше понятно: добавляя к сумме цифр 2, мы проверяем всё до ${}^310$. И т.д. Нужно только следить, чтобы последовательность в итерациях не стала больше $10^{10}$ (тогда нужно корректировать логику проверок). В своих проверках я азарта ради доходил где-то до ${}^{85}10$, не привлекая операций длинной арифметики (если мне не изменяет память).

[grizzly]

Думаю, можно уже привести свою версию решения. Точнее, идею -- хотя она проста и незамысловата, но аккуратная запись решения дело весьма занудное. Идею я распишу подробно, и если возникнут вопросы, я смогу ответить. Ниже обсуждение идёт в десятичной системе счисления.

Итак, нужно доказать, что в итерационной последовательности $a_{i+1}=a_i+s(a_i)$, где $s(k)$ -- сумма цифр числа $k$, встретится бесконечное число чётных чисел.

Предположим от противного, что после прохождения какого-то $M$ чётные больше не встречаются. Идея доказательства в том, чтобы продолжить последовательность дальше и показать, что в ней необходимо встретятся числа разной чётности.

Продолжая итерации после $M$ мы будем проходить через все числа вида $10...010...0+K_i$. (Здесь возможное количество нулей в многоточиях и (различные) числа $K_i$ оговариваются несложно и для понимания идеи вряд ли нужно.) Поскольку $C_n^2$ (количество вариантов по-разному расставить 2 единицы) растёт быстрее, чем $9\cdot n$ (это для $K_i<9n$), мы гарантированно получим в нашей последовательности 2 числа указанного вида, у которых $K_i=K_j$, но обе единицы стоят на разных местах (нас больше будет интересовать правая единица).

Проследим после этого параллельно за соответствующими итерациями от двух полученных чисел. Понятно, что они будут развиваться в некотором смысле синхронно до тех пор, пока дело не дойдёт до перехода через ближайшую единицу. Тогда у первого из рассматриваемых чисел единица на этом разряде превратится в 2, а в это же время у другого 0 перейдёт в 1. Сумма цифр у обоих чисел останется одинаковой. И вообще в этот момент оба числа будут по-прежнему отличаться только двумя цифрами. Ещё немного терпения и итераций и рассматриваемый разряд у первого числа перевалит через десяток (у другого числа 8 сменится на 9). Очевидно, что в этот момент сумма цифр у одного и у другого числа станет разной чётности.

Коротко не получилось, а насчёт понятности мне сложно судить.