Палиндромы и 196
Dec. 30th, 2012 10:39 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mancunian1998Возьмем натуральное число, большее 9, и проделаем следующую операцию: прочитаем его в десятичной записи, но в обратную сторону, и прибавим к изначальному числу.
Например, 18+81=99. Как мы видим, получился палиндром, то есть такое число, что если его цифры прочитать задом наперед, получится то же число. Однако 19+91=110, то есть не палиндром. Тем не менее, давайте продолжим процесс: 110+011=121 - палиндром!
С некоторыми числами этот процесс длиннее, например: 69 -> 165 ->721 -> 848 726 -> 1353 -> 4884.
Вопрос: верно ли, что за конечное число шагов (итераций) мы получим палиндром из любого натурального числа?
Ответ: науке это неизвестно.
Первое число, про которое это неизвестно, есть 196. На него, ясное дело, угробили несусветное количество машинного времени, но палиндрома так и не получили. Эвристические аргументы - за то, что если за какое-то разумное число шагов палиндрома не вышло, то с каждым шагом этих шансов становится всё меньше и меньше. То есть можно поставить деньги на то, что 196 - число Личрела.
Я лично считаю, что найти конкретное число Личрела - совершенно нереально, но, например, доказать, что они существуют, математики когда-нибудь смогут. (Более того, уверен, что это множество положительной плотности.)
Проблема (как я ее вижу) тут в том, что операция "разворота" натурального числа в десятичной системе нетривиальна с точки зрения динамических систем, а сложение с развернутым числом приводит к переносам, которые хоть и описываются конечным автоматом, всё равно портят всю картину. Плохо еще то, что неясно, как эту операцию перенести на, скажем, бесконечные последовательности, вложив туда натуральные числа так, чтобы операция была непрерывна в соответствующей топологии (10-адической, например). Если бы это удалось, можно было бы включить аппарат эргодической теории, а так увы.
В общем, еще одно подтверждение того факта, что позиционные системы счисления, к которым мы так привыкли, слишком часто оказываются плохо совместимы с самыми естественными задачами. (Что содержательного вы можете сказать про десятичное разложение корня из двух, например? ответы по почте.)
(Если кто заинтересовался "проблемой 196", рекомендую почитать комменты к соответствующему посту на MathOverFlow, откуда я, собственно, и узнал про эту задачу.)
Например, 18+81=99. Как мы видим, получился палиндром, то есть такое число, что если его цифры прочитать задом наперед, получится то же число. Однако 19+91=110, то есть не палиндром. Тем не менее, давайте продолжим процесс: 110+011=121 - палиндром!
С некоторыми числами этот процесс длиннее, например: 69 -> 165 ->
Вопрос: верно ли, что за конечное число шагов (итераций) мы получим палиндром из любого натурального числа?
Ответ: науке это неизвестно.
Первое число, про которое это неизвестно, есть 196. На него, ясное дело, угробили несусветное количество машинного времени, но палиндрома так и не получили. Эвристические аргументы - за то, что если за какое-то разумное число шагов палиндрома не вышло, то с каждым шагом этих шансов становится всё меньше и меньше. То есть можно поставить деньги на то, что 196 - число Личрела.
Я лично считаю, что найти конкретное число Личрела - совершенно нереально, но, например, доказать, что они существуют, математики когда-нибудь смогут. (Более того, уверен, что это множество положительной плотности.)
Проблема (как я ее вижу) тут в том, что операция "разворота" натурального числа в десятичной системе нетривиальна с точки зрения динамических систем, а сложение с развернутым числом приводит к переносам, которые хоть и описываются конечным автоматом, всё равно портят всю картину. Плохо еще то, что неясно, как эту операцию перенести на, скажем, бесконечные последовательности, вложив туда натуральные числа так, чтобы операция была непрерывна в соответствующей топологии (10-адической, например). Если бы это удалось, можно было бы включить аппарат эргодической теории, а так увы.
В общем, еще одно подтверждение того факта, что позиционные системы счисления, к которым мы так привыкли, слишком часто оказываются плохо совместимы с самыми естественными задачами. (Что содержательного вы можете сказать про десятичное разложение корня из двух, например? ответы по почте.)
(Если кто заинтересовался "проблемой 196", рекомендую почитать комменты к соответствующему посту на MathOverFlow, откуда я, собственно, и узнал про эту задачу.)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-12-30 11:12 am (UTC)Iz populiarnoi lekchii pro abc-conjecture mne ponravilos'
sled. zayavlenie: v matematike est' dve operatsii: slozhenie i umnozhenie,
zadachi tol'ko pro slozhenie ili umnozhenie ( v principe) reshaemue,
no esli zadacha i pro slozhenie i pro umnozhenie,
to mozhet but' sovsem ploxo - princip. drugoi uroven' slozhnosti.
no subject
Date: 2012-12-30 11:16 am (UTC)no subject
Date: 2012-12-30 11:18 am (UTC)Poetomu dolzhno but' proshe. Pravil'noe svoistvo dolzhno but' bolee grubum.
no subject
Date: 2012-12-30 11:26 am (UTC)no subject
Date: 2012-12-30 11:16 am (UTC)99->198->1089->10890->20691 (ноль вначале не учитываем же, да?) Палиндрома не получилось, дальше лень.
12->33 (палиндром)->66 (палиндром)->132->363 (палиндром)->726->1353->4884 (палиндром)->9768->18447По-моему, пятизначные числа довольно трудно увидеть в виде палиндрома. Чем меньше значение числа, тем проще оно доходит до палиндрома?
С числом 12 тоже здорово. Два подряд, пробел в виде одного числа, палиндром, пробел из двух чисел. Красиво. :)
no subject
Date: 2012-12-30 11:22 am (UTC)Конечно, маленькие числа должны "палиндромизироваться" быстрее, из общих соображений. Чем дальше - тем больше переносов...
no subject
Date: 2012-12-30 11:52 am (UTC)no subject
Date: 2012-12-30 01:17 pm (UTC)no subject
Date: 2012-12-30 01:41 pm (UTC)First, there is a regular family which can be shown to extend to any power
of 2:
Base 2:
10(n 1s)1101(n 0s)00
After 4 iterations, becomes same thing with n increased by 1.
Base 4:
10(n 3s)3323(n 0s)00
After 6 iterations, becomes same thing with n increased by 1.
Base 8:
10(n 7s)7767(n 0s)00
After 8 iterations, becomes same thing with n increased by 1.
Base 16:
10(n Fs)FFEF(n 0s)00
After 10 iterations, becomes same thing with n increased by 1.
Base 32:
10(n Vs)VVUV(n 0s)00
After 12 iterations, becomes same thing with n increased by 1.
Sporadic solutions:
Base 4:
1033202000232(n 2s)2302333113230
After 6 iterations, becomes same thing with n increased by 3.
Base 11:
1246277(n As)A170352495681825A5026571A506181864A5143171(n 0s)0872542
After 6 iterations, becomes same thing with n increased by 1.
Base 17:
10023AB83E3B983CFGEC556G4G010(n 0s)0FGCG10FG505GF020CGF(n Gs)GG11G4F655D
DGGB299B3D38BB320G
After 6 iterations, becomes same thing with n increased by 1.
Base 20:
There is a >200 digit number of the same general form which grows
indefinitely without ever producing a palindrome, but I'm not going to
try to transcribe it here!
Base 26:
1N5ELA6C(n Ps)P6E7(n 0s)0D59ME5N
After 4 iterations, becomes same thing with n increased by 1.
no subject
Date: 2012-12-30 03:46 pm (UTC)no subject
Date: 2012-12-30 03:55 pm (UTC)Примера вполне достаточно, если его обосновать (что должно быть просто, раз закономерность просекли). Можно, конечно, спросить: сколько таких чисел? (В смысле плотности, например.) А то мало ли что нашли одно чахлое семейство. ;)
Но это, видимо, гробовой вопрос.
no subject
Date: 2012-12-30 04:23 pm (UTC)Да, и про плотность интересно.
Черт, чем только математики не занимаются,
лишь бы не работать!no subject
Date: 2012-12-30 04:29 pm (UTC)no subject
Date: 2012-12-30 02:01 pm (UTC)no subject
Date: 2012-12-30 02:33 pm (UTC)no subject
Date: 2012-12-30 02:45 pm (UTC)no subject
Date: 2012-12-30 02:58 pm (UTC)no subject
Date: 2012-12-30 02:29 pm (UTC)Ошибка во втором шаге.
69 -> 165 -> 726 -> 1353 -> 4884
no subject
Date: 2012-12-30 02:32 pm (UTC)no subject
Date: 2012-12-30 07:15 pm (UTC)no subject
Date: 2012-12-31 03:03 am (UTC)скажем, стартовав с палиндрома, найти наименьшее число-генератор
no subject
Date: 2012-12-31 04:58 am (UTC)*) исключив конечное число тривиальных