Введение
Число Лихреля — это натуральное число, которое невозможно преобразовать в палиндром посредством итеративного процесса, заключающегося в многократном развороте его цифр и сложении полученных чисел. Этот процесс иногда называют алгоритмом 196, по имени наиболее известного числа, связанного с ним. В десятичной системе счисления существование чисел Лихреля пока не доказано, однако многие, включая 196, предполагаются таковыми на основе эвристических и статистических соображений. Название "Лихрел" было придумано Уэйдом Ван Лэндингэмом как приблизительная анаграмма имени "Шерил", имени его девушки.
Доказательства не найдены
В других системах счисления (эти системы являются степенями 2, как двоичная и шестнадцатеричная), для определенных чисел можно доказать, что они никогда не образуют палиндром после многократного обращения и сложения, однако для 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 цифр. На сайте Уэйда Ван Лэндингема указано общее количество найденных подозреваемых семенных чисел Лихреля для каждой разрядности. Метод полного перебора, первоначально использованный Джоном Уокером, был усовершенствован с учетом особенностей итерационного поведения. Например, Vaughn Suite разработал программу, которая сохраняет только первые и последние несколько цифр каждой итерации, что позволяет проводить тестирование закономерностей цифр в миллионах итераций без необходимости сохранять каждую итерацию целиком в файл. Однако на данный момент не разработан алгоритм, позволяющий обойти итеративный процесс обращения и сложения.
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. The numbers in bold are suspected Lychrel seed numbers (see below). Computer programs by Jason Doucette, Ian Peters and Benjamin Despres have found other Lychrel candidates. Indeed, Benjamin Despres' program has identified all suspected Lychrel seed numbers of less than 17 digits. Wade Van Landingham's site lists the total number of found suspected Lychrel seed numbers for each digit length. The brute force method originally deployed by John Walker has been refined to take advantage of iteration behaviours. For example, Vaughn Suite devised a program that only saves the first and last few digits of each iteration, enabling testing of the digit patterns in millions of iterations to be performed without having to save each entire iteration to a file. However, so far no algorithm has been developed to circumvent the reversal and addition iterative process.
Число нитей, семени и родственников
Термин "поток", введенный Джейсоном Дусеттом, обозначает последовательность чисел, которая может или не может привести к палиндрому в результате процесса обращения и сложения. Любое начальное число и его производные числа будут сходиться к одному и тому же потоку. Поток включает в себя только те числа, которые являются общими для всех производных чисел после их схождения, не включая само начальное число или производные числа. Начальные числа являются подмножеством чисел Лихреля, то есть наименьшим числом в каждом потоке, не приводящем к палиндрому. Начальное число само по себе может быть палиндромом. Первые три примера выделены жирным шрифтом в списке выше. Производные числа – это подмножество чисел Лихреля, включающее все числа потока, за исключением начального числа или любого числа, которое сходится к данному потоку после одной итерации. Этот термин был предложен Кодзи Ямаситой в 1997 году.
196 поиск палиндромов
Поскольку 196 (в десятичной системе счисления) является наименьшим кандидатом в числа Лихреля, оно привлекло наибольшее внимание. В 1980-х годах проблема палиндрома для числа 196 заинтересовала любителей микрокомпьютеров, и программы поиска, разработанные Джимом Баттерфилдом и другими, были опубликованы в нескольких популярных журналах по вычислительной технике. В 1985 году программа Джеймса Киллмана безуспешно работала более 28 дней, выполнив 12 954 итерации и достигнув числа, состоящего из 5366 цифр. В 2011 году Ромен Долбо выполнил миллиард итераций, получив число с 413 930 770 цифрами, а в феврале 2015 года его вычисления привели к числу с миллиардом цифр. Палиндром до сих пор не найден. Другие потенциальные числа Лихреля, которые также подвергались методу грубой силы, заключающемуся в многократном сложении с обращением, включают 879, 1997 и 7059: они были рассчитаны в течение нескольких миллионов итераций, но палиндром не был обнаружен.
Расширение на отрицательные целые числа
Числа Лихреля можно расширить на отрицательные целые числа, используя представление чисел со знаком для представления каждого целого числа.