Еще о палиндромах

[Lesobrod]

Возьмём целое число и переставим цифры в обратном порядке.
Вычтем из большего меньшее. Будем повторять процесс.

Большинство чисел быстро приходит к палиндрому, а после этого - к нулю.
Палиндром содержит только девятки и нули, что связано со свойством делимости на "9".
НО! Есть числа, которые приходят к 2-циклу. Наименьший из них:
$2178\ - \ 6534\ - \ 2178\ - \ 6534\ -\ ... $
Для больших чисел могут возникнуть
$219978\ - \ 659934\ - \ 219978\ - \ 659934\ -\ ...$,
что уже как-то понятно. А откуда беруться 2178 и 6534?!
$2178= 2^1\cdot\ 3^2\cdot\ 11^2,\ 6534\ = \ 2178\cdot\ 3$
И...что?

-- Сб июн 30, 2012 18:31:42 --

Ага, кое-что понял. Оба числа имеют вид
$\overline{[i][i-1][k][k+1]}$ при $i=6,2\ \ k=3,7$
А вот почему все остальные числа такого вида приходят к ним?

[scwec]

Ничего удивительного в появлении циклов нет. Ведь как только мы выбрали число для эксперимента, так сразу же определили верхнюю границу множества чисел, которую перепрыгнуть не можем. Ясно, что в конце-концов придем либо к нулю, либо к повторению чисел.
Другое дело посмотреть, какой длины могут быть циклы, растет ли их размер вместе со значностью начального числа и т.д.
По-моему, это может быть интересным.

[Lesobrod]

scwec в сообщении #591610 писал(а):

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

Я тоже так думал, но это не так! Ведь после перестановки цифр разность может стать больше уменьшаемого. Вот пример процесса:
$1234\ \rightarrow 3087\ \rightarrow4716\ \rightarrow 1458\ \rightarrow 7083\ \rightarrow 3276\ \rightarrow 3447\ \rightarrow 3996\ \rightarrow 2997\ \rightarrow 4995\ \rightarrow 999$
Возможно, что-то связано с делимостью на "9"..

[venco]

Lesobrod в сообщении #592867 писал(а):

scwec в сообщении #591610 писал(а):

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

Я тоже так думал, но это не так! Ведь после перестановки цифр разность может стать больше уменьшаемого.

Но не больше чем $10^n$, где $n$ - число цифр.

[arseniiv]

23981958 порождает десятичный 14-цикл.

(Оффтоп)

Lesobrod в сообщении #592867 писал(а):

"9"

Кавычки лишние! 9 же и имеется в виду.

-- Сб июл 07, 2012 03:56:27 --

venco в сообщении #592904 писал(а):

Но не больше чем $10^n$, где $n$ - число цифр.

Вы не имели в виду $10^{n+1}$?

[venco]

arseniiv в сообщении #592931 писал(а):

venco в сообщении #592904 писал(а):

Но не больше чем $10^n$, где $n$ - число цифр.

Вы не имели в виду $10^{n+1}$?

Это не принципиально, но нет, не имел.

[arseniiv]

(Оффтоп)

Тогда я что-то не так понимаю — числа должны почти всегда терять не менее чем по одному разряду (кроме случая, когда разность будет ровно $10^n$)? Ведь числа с $n$ цифрами находятся в $10^n..10^{n+1}-1$.

[Lesobrod]

Тема оказалась очень богатой, не уверен что стоит продолжать в "Олимпиадах"..
Но как пойдёт..
Спасибо за подсказку про ограниченность. Пошёл немного дальше.
Возьмём 4-значное число $\overline{c_1 c_2 c_3 c_4}$
После первого шага получиться $9 (111 (c_1 - c_4) + 10 (c_2 - c_3))$. Но вариантов разностей цифр гораздо меньше, чем самих цифр!
Проверил численно - из 9000 чисел от 1000 до 9999 после первого же шага остаётся 181 (уникальное) число!
То есть здесь не только ограниченность, но сжатие, в нек. смысле. А отсюда можно и циклы искать.

23 981 958 стало откровением))). Нашёл также:
44 664 246 -- 14-цикл;
115 521 884 478 -- 22-цикл;
614 218 000 178 574 -- 12-цикл...
Если "слепить" вместе все цифры последовательных чисел 22-цикла,
то полученный ряд показывает высокую равнораспределённность, как по отдельным цифрам, так и по парам.
Типа, генератор случайных цифр..
Но такое отображение не может быть стохастическим!

[venco]

(arseniiv)

arseniiv в сообщении #593138 писал(а):

Ведь числа с $n$ цифрами находятся в $10^n..10^{n+1}-1$.

Вот здесь у вас ошибка, хотя, как я уже говорил, конкретный диапазон не важен, важно, что он конечный.

[arseniiv]

(2 venco.)

Спасибо! Точно, это же $n+1$-значные числа (проверил на однозначных и всё встало на место).

[Хорхе]

ссылка

[Lesobrod]

>ссылка
О, спасибо, это солидная статья. С разностями цифр я был на верном пути,
но так далеко, конечно, не зашёл бы...