Произведения цифр

[grizzly]

Речь пойдёт о последовательности A063108. Точнее, о гипотезе к ней, которая указана в комментарии по той же ссылке:

Цитата:

Conjecture: no matter what the starting term is, the sequence eventually joins this one. This should be true in any base - base 2, for example, is trivial.

In Russian: с какого бы стартового номера мы не начали, последовательность рано или поздно вольётся в оригинальную. Утверждение истинно по любому основанию (например, для основания 2 гипотеза тривиальна).

Задача. Найти простое доказательство для основания 3.

То же самое доказательство работает и для оснований 4 и 5. Но если для основания 3 все необходимые рассуждения и проверки можно провести в уме, то для больших оснований потребуется какая-то компьютерная проверка.

(Оффтоп)

Как по мне, задача вполне доступна (идейно) ученику средних классов, но оформить решение качественно смог бы только старшеклассник и выше, имхо.

В своё время был удивлён, что P.A.Loomis (автор последовательности) предпринял попытку, но не нашёл доказательства, ограничившись публикацией гипотез в научно-популярных журналах. Хотя не исключаю, что его интересовало только общее для всех оснований доказательство.

[worm2]

Доказательства пока нет. Но можно прикинуть схему для каждого отдельно взятого основания $a$.

Для достаточно большого числа произведение его цифр значительно меньше его самого, значит, продолжая считать, и перейдя через какой-то рубеж $a^k$, мы получим число вида $1X...Z_a$. Далее в течение нескольких (как минимум $m$) итераций последовательность будет вести себя как последовательность для меньшего начального значения $X...Z_a$, но с добавкой $10...0_a$, и первой её цифрой будет единица. Получается метод типа спуска до какого-то $N$ (для которого произведение цифр уже сравнимо с ним самим), а все значения, меньшие $N$, можно проверить перебором. Проверять нужно, что все стартовые номера, меньшие $N$, вольются в "основную" последовательность не более, чем за $m$ итераций.

Однако уже для $a=3$ меня ломает это делать. Предположительно, $N=80$, $m=9$. То есть все начальные значения, только что превысившие 80, не будут ещё минимум в течение 9 шагов превышать $161 = 12222_3$, а все начальные значения, меньшие 80, в течение этих 9 шагов или менее, "вольются" в основную последовательность.

Нет, не получается. Для значений, превысивших $3^5$, нужно заново выбирать $m$... Может, тут возможна какая-то модификация, которую я не вижу. А может, безнадёжно всё и надо по-другому подходить.

[grizzly]

worm2 в сообщении #940105 писал(а):

А может, безнадёжно всё и надо по-другому подходить.

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

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

-- 04.12.2014, 14:21 --

Вот, кстати -- A063112. Как я сразу не догадался? Это должно в 4 раза уменьшить трудозатраты на рутинный перебор :)

[worm2]

Ну да. Я немножко не в ту сторону пошёл.
Для основания $a=3$ получается такое рассуждение. Обозначим через $G_3(i)$ член последовательности, начинающейся с $i$, который совпадает с каким-то членом последовательности, начинающейся с единицы (т.е. "точку вливания" последовательности для $i$ в "основную" последовательность). Разумеется, это обозначение корректно только если последовательность действительно вливается в "основную". Если это не так, то положим $G_3(i) = +\infty$. Нам нужно доказать, что для любого $i$ $G_3(i)< +\infty$.
Думаю, тут я должен привести пример. "Основная" последовательность такова:
$1$, $2$, $4=11_3$, $5=12_3$, $7=21_3$, $9=100_3$, $10=101_3$, $11=102_3$, $13=111_3$, $14=112_3$, $16=121_3$, ...
Последовательность для $6$ получается такой:
$6=20_3$, $8=22_3$, $12=110_3$, $13=111_3$: совпадение с основной последовательностью. Значит, $G_3(6)=13$.
А давайте-ка мы оценим $G_3(i)$ для всех $i$, не превышающих 9. Для членов основной последовательности, понятно, что $G(i)=i$, остальных всего 3 штуки: 3, 6 и 8, причём 8 следует за 6, поэтому $G_3(6)=G_3(8)=13$. Ещё легче посчитать $G_3(3)=4$. Итак, $G_3(i)\leqslant 13$ для всех $i\leqslant 9$.
Здесь мы уже просто обязаны ввести обозначение $p_3(i)$ — произведение троичных цифр числа $i$. Вообще-то должны были давно ввести, но теперь без этого обозначения никак.
Оценим теперь $G_3(i)$ для всех $i$, не превышающих 27. Поскольку для любого такого числа $p_3(i)\leqslant 2\cdot 2\cdot 2 = 8$, последовательность для любого такого числа обязательно пройдёт между $27=1000_3$ и $26+8=34=1022_3$. Будем рассматривать последовательность, пока она не достигнет (или превысит) $54=2000_3$. Поскольку первая троичная цифра рассматриваемого числа равна 1, $p_3(i)=p_3(i-27)$, то есть последовательность повторится со сдвигом 27 и с начальным значением, не превосходящим 8. Что мы можем сказать о такой последовательности? Что она обязательно вольётся в основную, не достигнув 54, потому что $G_3(i-27)\leqslant 13$, а следовательно, $G_3(i)\leqslant 13+27=40<54$. Итак, мы продлили доказательство конечности $G_3$ до 27, показав для неё новую оценку. Аналогично, мы можем продлить $G_3$ для всех чисел, не превосходящих 81, до $40+81=121$, пользуясь тем, что для них $p_3(i)\leqslant 2^4<3^3$.
Более грубо и формально: мы доказываем индукцией по $n$, что при $i\leqslant 3^n$ выполняется $G_3(i)\leqslant 2\cdot 3^n<3^{n+1}$. База индукции: $n=2$. Переход к $n+1$:
1) Убеждаемся, что последовательность обязательно попадёт в отрезок $\[3^{n}..3^n+3^{n-1}-1\]$, поскольку для последнего члена, не превысившего $3^n$, справедливо: $p_3(i)\leqslant 2^n<3^{n-1}$.
2) Замечаем, что для нескольких следующих членов последовательности $p_3(i)=p_3(i-3^{n+1})$ (пока она не превысит $2\cdot 3^{n+1}$), а значит, некоторое время последовательность будет повторять последовательность для $i-3^{n+1}$ со сдвигом $3^{n+1}$.
3) Подсчитываем, что это "некоторое время" по индукционному предположению превысит время слияния всех последовательностей в одну, а значит, $G_3(i)=G_3(i-1)+3^{n+1}<3^{n+2}$, индукционный переход совершён.

[grizzly]

Всё верно, спасибо за разделённый интерес! :)

Я шёл по такому же пути, только заметил, что все числа до $2^5$ проходят через точку $1111_3$. А отсюда по такого же типа индукции следует, что в последовательности с любым стартовым номером $a_0<3^N$ встретятся все числа вида $11...1_3$ -- с любым количеством единиц, большим $N$.

Но опорная точка эта:

worm2 в сообщении #941139 писал(а):

1) Убеждаемся, что последовательность обязательно попадёт в отрезок $\[3^{n}..3^n+3^{n-1}-1\]$, поскольку для последнего члена, не превысившего $3^n$, справедливо: $p_3(i)\leqslant 2^n<3^{n-1}$.

И если для оснований 4 и 5 всё почти так же просто (но начальные проверки нужно делать на компьютере), то для основания 10 сделать начальную проверку на современных компьютерах пока не реально (или алгоритмы нужны совсем не детские).

А Вы не умеете оставить Comment на той страничке Слоана?

[worm2]

grizzly писал(а):

А Вы не умеете оставить Comment на той страничке Слоана?

Вроде бы, нужно на указанный там e-mail написать?

[maxal]

worm2 в сообщении #941179 писал(а):

grizzly писал(а):

А Вы не умеете оставить Comment на той страничке Слоана?

Вроде бы, нужно на указанный там e-mail написать?

Сейчас достаточно зарегистрироваться на http://oeis.org/wiki/Special:RequestAccount и у вас появится возможность отсылать исправления (в том числе и новые комментарии) к последовательностям в OEIS.