Проблема 196

Проблема 196 — условное название нерешённой математическойзадачи: неизвестно, приведёт ли операция «перевернуть и сложить»,применённая к числу 196 какое-то количество раз, к палиндрому — числу,читающемуся с конца так же, как с начала.
Число Лишрел  — это натуральное число, которое не можетстать палиндромом с помощью итеративного процесса «перевернуть исложить» в десятичной системе счисления. Этот процесс называется196-алгоритмом. Название «Lychrel», придуманное WadeVanLandingham, — примерная анаграмма имени его подруги — Шерил .Строго доказанных чисел Лишрел не существует, но многие числапредполагаются таковыми, причём наименьшее из них — 196.

Перевернуть исложить


 «Перевернуть и сложить»  — название операции, выполняемой надчислом. Суть заключается в сложении исходного десятичного числа с егоперевёрнутой копией (числом, записанным с конца). Например, 56 + 65 =121, 521 + 125 = 646.
 Некоторые числа (в частности, все однозначные и двузначные числа)становятся палиндромами достаточно быстро — после несколькихприменений операции, и поэтому не являются числами Лишрел. Около 80 всех чисел, меньших 10000, разрешаются в палиндром в 4 или меньше шагов.Около 90 Вот несколько примеров чисел не-Лишрел:

  • 56 становится палиндромом после одной итерации: 56 + 65 = 121.
  • 57 становится палиндромом после двух итераций: 57 + 75 = 132, 132 + 231 = 363.
  • 59 становится палиндромом после трех итераций: 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111
  • 89 проходит необычно много — 24 итерации (наибольшее кол-во для чисел менее 10000, которые точно разрешаются в палиндром), прежде чем достичь палиндрома 8813200023188.
  • 10 911 достигает палиндрома 4668731596684224866951378664 после 55 итераций.
  • 1 186 060 307 891 929 990 проходит 261 итерацию и становится 119-значным палиндромом 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544. Это число является в настоящее время мировым рекордом (наиболее отложенным палиндромом). Оно было найдено Джейсоном Дусеттом с помощью компьютера 30 ноября 2005 года.

 В мае 2017 года телеканал МИР24 сообщил, что московский школьник АндрейЩебетов обнаружил самый большой известный отложенный палиндром -число1999291987030606810.
 Последовательность А281506 содержит полный список первых 108864 наиболееотложенных палиндромов, требующих 261 итерацию для превращения впалиндром. Она начинается с 1186060307891929990 и заканчивается1999291987030606810.
 Первое известное число, начиная с 0, которое, видимо, не образуетпалиндром, — трёхзначное число 196. Это наименьший номер кандидатаLychrel.

Открытаяпроблема


 В других основаниях для некоторых чисел может быть доказано, что они необразуют никогда палиндром после последовательных итераций, но не былообнаружено таких доказательств для 196 и других десятичных чисел.
 Существует гипотеза, что 196 и другие числа, которые пока ещё не сталипалиндромом, являются числами Лишрел, но ни для одного числа нетстрогого доказательства, что оно Лишрел. Подобные числа неофициальноназывают «кандидаты в числа Лишрел». Первые несколько кандидатов вЛишрел :

196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887,978, 986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855, 1857,1945, 1947, 1997.
 Выделенные жирным считаются базовыми числами Лишрел (см. ниже).Компьютерные программы Джейсона Дусетта, Яна Петерса и БенджаминаДеспреса нашли другие кандидаты Лишрел. Более того, Бенджамин Деспресвыявил все базовые числа Лишрел, состоящие из менее, чем 17 цифр. СайтWade VanLandingham содержит списки базовых чисел Лишрел для каждой длинычисла.
 Метод грубой силы, первоначально разработанный Джоном Уокером, былусовершенствован, чтобы использовать поведение при итерациях. Например,Vaughn Suite разработал программу, которая сохраняет только первые ипоследние несколько цифр каждой итерации, позволяя тестировать цифровыезакономерности на протяжении миллионов итераций без необходимостисохранения каждой итерации в файл. Но пока не было придумано алгоритма,который бы обходил итеративный процесс.

Связанныеопределения


 Термин нить или поток придумал Джейсон Дусетт,обозначая так последовательность чисел, получаемых в результате итерацийпервоначального числа. Базовое число и его связанныеродственные числа сходятся в одном потоке. Поток не включаетисходное базовое число или его родственника, но толькочисла, которые являются общими для обоих, после того, как они сойдутся.
Базовые числа представляют собой подпоследовательность чиселЛишрел, то есть наименьшее число из каждого не производящего палиндромпотока. Базовое число может быть само по себе палиндромом. Первые трипримера выделены полужирным шрифтом в приведённом выше списке.
Родственные числа представляют собой подмножество чисел Лишрел,которые включают все числа потока, за исключением базового, или любоечисло, которое вольётся в данный поток после одной итерации. Этот терминбыл представлен Кодзи Ямаситой в 1997 году.

Квест 196


 Поскольку 196 (по основанию 10) является наименьшим кандидатом в числаЛишрел, оно получило наибольшее внимание.
 начал квест, посвящённый изучению потока «196», 12 августа 1987 года нарабочей станции Sun 3/260. Он написал программу на C, которая выполняетитерации «перевернуть и сложить» и проверяет на палиндром после каждогошага. Программа была запущена в фоновом режиме с низким приоритетом. Онасбрасывала контрольные точки в файл каждые два часа и в момент закрытиясистемы, записывая достигнутые к тому времени число и номер итерации.Она перезапускалась сама автоматически из последней контрольной точкипосле каждого включения компьютера. Она работала в течение почти трёхлет, а затем остановилась (как было запрограммировано) 24 мая 1990 годас сообщением:
 196 увеличилось до числа в один миллион разрядов после 2 415 836итераций без достижения палиндрома. Уокер опубликовал свои выводы вИнтернет вместе с последней контрольной точкой, приглашая другихвозобновить поиски на основе последнего достигнутого числа.
 В 1995 году Тим Ирвин использовал суперкомпьютер и достиг отметки в двамиллиона цифр всего за три месяца, опять не найдя палиндрома. ДжейсонДусетт затем последовал их примеру и достиг 12,5 миллионов цифр в мае2000 года. Wade VanLandingham, используя программу Джейсона Дусетта,достиг 13 миллионов цифр, что было опубликовано в Yes Mag — канадскомнаучном журнале для детей. С июня 2000 года VanLandingham продолжалнести флаг первенства, используя программы, написанные различнымиэнтузиастами. К 1 мая 2006 года VanLandingham достиг отметки 300миллионов цифр (со скоростью одного миллиона цифр каждые 5-7 дней).Используя распределённые вычисления, в 2011 году Romain Dolbeauсовершил миллиард итераций и получил число, состоящее из 413 930 770цифр, в июле 2012 года его вычисления достигли числа с 600 млн цифр, а вфеврале 2015 число цифр перевалило за 1 миллиард, но палиндром так и небыл обнаружен.
 Другие кандидаты в числа Лишрел, которые подвергались такому жеперебору, включают 879, 1997 и 7059: они были прослежены на протяжениимиллионов итераций без обнаружения палиндрома.