Число Лишрел — это натуральное число , которое не может образовать палиндром посредством итеративного процесса многократного переворачивания его цифр и сложения полученных чисел. Этот процесс иногда называют 196-алгоритмом , в честь самого известного числа, связанного с этим процессом. В десятичной системе счисления пока не доказано существование ни одного числа Лишрел , но многие, включая 196, подозреваются на эвристических [1] и статистических основаниях. Название «Лишрел» было придумано Уэйдом Ван Ландингемом как грубая анаграмма имени «Шерил», его девушки. [2]
Процесс обратного сложения производит сумму числа и числа, образованного путем изменения порядка его цифр на обратный. Например, 56 + 65 = 121. Другой пример: 125 + 521 = 646.
Некоторые числа быстро становятся палиндромами после многократного переворота и сложения, и поэтому не являются числами Лишрел. Все однозначные и двузначные числа в конечном итоге становятся палиндромами после многократного переворота и сложения.
Около 80% всех чисел до 10 000 разрешаются в палиндром за четыре или менее шагов; около 90% из них разрешаются за семь или менее шагов. Вот несколько примеров не-Лишрель чисел:
Наименьшее число, которое, как известно, не образует палиндром, — 196. Следовательно, это наименьший кандидат на число Лишрел.
Число, полученное в результате перестановки цифр числа Лишрел, не заканчивающегося на ноль, также является числом Лишрел.
Пусть будет натуральным числом. Определим функцию Лишрела для основания числа b > 1, , следующим образом:
где - количество цифр в числе в базе , а
- это значение каждой цифры числа. Число является числом Лишрела, если не существует натурального числа такого, что , где - это -я итерация
В других системах счисления ( таких как двоичная и шестнадцатеричная ) можно доказать , что некоторые числа никогда не образуют палиндром после многократного переворачивания и сложения [3] , но для числа 196 и других чисел с основанием 10 таких доказательств найдено не было.
Предполагается, что 196 и другие числа, которые пока не дали палиндром, являются числами Lychrel, но ни одно число в десятичной системе счисления пока не было доказано, что является Lychrel. Числа, для которых не было доказано, что они не являются числами Lychrel, неформально называются числами-кандидатами Lychrel. Первые несколько чисел-кандидатов Lychrel (последовательность A023108 в OEIS ):
Числа, выделенные жирным шрифтом, являются предполагаемыми числами Lychrel seed (см. ниже). Компьютерные программы Джейсона Дусетта, Яна Питерса и Бенджамина Депре нашли других кандидатов Lychrel. Действительно, программа Бенджамина Депре идентифицировала все предполагаемые числа Lychrel seed, содержащие менее 17 цифр. [4] На сайте Уэйда Ван Ландингема перечислено общее количество найденных предполагаемых чисел Lychrel seed для каждой длины цифры. [5]
Метод грубой силы, первоначально примененный Джоном Уокером, был усовершенствован, чтобы использовать преимущества итерационного поведения. Например, Vaughn Suite разработал программу, которая сохраняет только первые и последние несколько цифр каждой итерации, что позволяет проводить тестирование цифровых шаблонов в миллионах итераций без необходимости сохранять каждую целую итерацию в файл. [6] Однако до сих пор не было разработано алгоритма, который бы обходил итерационный процесс реверсирования и сложения.
Термин thread , придуманный Джейсоном Дусеттом, относится к последовательности чисел, которые могут или не могут привести к палиндрому через обратный и прибавляемый процесс. Любое заданное семя и связанные с ним числа kin будут сходиться на одной и той же нити. Нить не включает в себя исходное семя или число kin , а только числа, которые являются общими для обоих, после того, как они сходятся.
Начальные числа являются подмножеством чисел Lychrel, то есть наименьшим числом каждой непалиндромной нити. Начальное число может быть палиндромом само по себе. Первые три примера выделены жирным шрифтом в списке выше.
Числа Kin — это подмножество чисел Lychrel, включающее все числа потока, кроме seed, или любого числа, которое будет сходиться на данном потоке после одной итерации. Этот термин был введен Кодзи Ямашитой в 1997 году.
Поскольку 196 ( основание 10 ) является наименьшим кандидатом на число Лишрел, оно привлекло наибольшее внимание.
В 1980-х годах проблема палиндрома 196 привлекла внимание любителей микрокомпьютеров , и программы поиска Джима Баттерфилда и других появились в нескольких массовых компьютерных журналах. [7] [8] [9] В 1985 году программа Джеймса Киллмана безуспешно работала более 28 дней, циклически пройдя 12 954 прохода и достигнув 5366-значного числа. [9]
Джон Уокер начал свой 196 Palindrome Quest 12 августа 1987 года на рабочей станции Sun 3/260. Он написал программу на языке C для выполнения итераций обратного и сложения и проверки палиндрома после каждого шага. Программа работала в фоновом режиме с низким приоритетом и создавала контрольную точку в файле каждые два часа, а когда система выключалась, записывала достигнутое число и количество итераций. Она автоматически перезапускалась с последней контрольной точки после каждого выключения. Она работала почти три года, а затем была завершена (как и было указано) 24 мая 1990 года с сообщением:
Число 196 выросло до миллиона цифр после 2 415 836 итераций без достижения палиндрома. Уокер опубликовал свои выводы в Интернете вместе с последней контрольной точкой, пригласив других продолжить поиски, используя достигнутое число.
В 1995 году Тим Ирвин и Ларри Симкинс использовали многопроцессорный компьютер и достигли отметки в два миллиона цифр всего за три месяца, не найдя палиндрома. Затем Джейсон Дусетт последовал их примеру и достиг 12,5 миллионов цифр в мае 2000 года. Уэйд ВанЛэндингем использовал программу Джейсона Дусетта, чтобы достичь 13 миллионов цифр, рекорд, опубликованный в Yes Mag: Canada's Science Magazine for Kids. С июня 2000 года Уэйд ВанЛэндингем несет флаг, используя программы, написанные различными энтузиастами. К 1 мая 2006 года ВанЛэндингем достиг отметки в 300 миллионов цифр (со скоростью один миллион цифр каждые 5-7 дней). Используя распределенную обработку , [10] в 2011 году Ромен Дольбо выполнил миллиард итераций, чтобы получить число из 413 930 770 цифр, а в феврале 2015 года его вычисления достигли числа из миллиарда цифр. [11] Палиндром до сих пор не найден.
Другие потенциальные числа Лишрел, которые также были подвергнуты тому же методу грубой силы повторного обратного сложения, включают 879, 1997 и 7059: они были доведены до нескольких миллионов итераций, но ни один палиндром не был найден. [12]
В системе счисления с основанием 2 число 10110 (22 в десятичной системе) является числом Лишрела, поскольку после 4 шагов оно достигает 10110100, после 8 шагов оно достигает 1011101000, после 12 шагов оно достигает 101111010000, и в целом после 4 n шагов оно достигает числа, состоящего из 10, за которым следуют n + 1 единица, затем 01, затем n + 1 ноль. Очевидно, что это число не может быть палиндромом, и ни одно из других чисел в последовательности не является палиндромом.
Было доказано, что числа Лишрел существуют в следующих основаниях: 11, 17, 20, 26 и всех степенях числа 2. [13] [14] [15]
Ни одно основание не содержит чисел Лишрел, меньших основания. Фактически, в любом данном основании b ни одно однозначное число не требует более двух итераций для образования палиндрома. Для b > 4, если k < b /2, то k становится палиндромом после одной итерации: k + k = 2 k , что является однозначной цифрой в основании b (и, следовательно, палиндромом). Если k > b /2, то k становится палиндромом после двух итераций.
Наименьшее число в каждой базе, которое может быть числом Лишрел, это (последовательность A060382 в OEIS ):
Числа Лишрел можно расширить до отрицательных целых чисел , используя знаковое цифровое представление для представления каждого целого числа.
