Число Лишрела

Нерешенная задача по математике :

Существуют ли какие-либо числа Лишрела с основанием 10?

(еще нерешенные задачи по математике)

Число Лишрела — это натуральное число , которое не может образовать палиндром посредством итерационного процесса многократного изменения его цифр и сложения полученных чисел. Этот процесс иногда называют 196-алгоритмом , по имени самого известного числа, связанного с процессом. В десятичной системе счисления еще не доказано существование чисел Лишрела , но многие из них, включая 196, подозреваются в эвристических и статистические основания. Имя «Ликрел» было придумано Уэйдом Ван Ландингемом как грубая анаграмма имени его девушки «Шерил».

Процесс обратного и сложения

Процесс обратного сложения дает сумму числа и числа, образованного путем изменения порядка его цифр. Например, 56 + 65 = 121. Другой пример: 125 + 521 = 646.

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

Около 80% всех чисел меньше 10 000 превращаются в палиндром за четыре или меньше шагов; около 90% из них решаются за семь шагов или меньше. Вот несколько примеров чисел, отличных от Lychrel:

• 56 становится палиндромным после одной итерации: 56+65 = 121 .
• 57 становится палиндромным после двух итераций: 57+75 = 132, 132+231 = 363 .
• 59 становится палиндромом после трех итераций: 59+95 = 154, 154+451 = 605, 605+506 = 1111.
• 89 требует необычно больших 24 итераций (большая часть любого числа меньше 10 000, которое, как известно, превращается в палиндром), чтобы достичь палиндрома 8813200023188 .
• Число 10911 достигает палиндрома 4668731596684224866951378664 (28 цифр) после 55 шагов .
• 1 186 060 307 891 929 990 требуется 261 итерация Для получения 119-значного палиндрома 38748888307835667984873422673467987856626544 , что было бывшим мировым рекордом для самого задерживающегося палиндромного числа . Она была решена с помощью алгоритма и программы Джейсона Дусетта (с использованием Бенджамина Депре ) 30 ноября 2005 года. кода обратного сложения
• 23 января 2017 года российский школьник Андрей Щебетов объявил на своем сайте, что нашел последовательность из первых 126 чисел (125 из них никогда ранее не сообщались), которым требуется ровно 261 шаг, чтобы достичь 119-значного палиндрома. Эта последовательность была опубликована в OEIS как A281506 . Эта последовательность начиналась с 1 186 060 307 891 929 990 — к тому времени единственное общеизвестное число, найденное Джейсоном Дусеттом еще в 2005 году. 12 мая 2017 года эта последовательность была расширена в общей сложности до 108 864 членов и включала первые 108 864 отложенных палиндрома с задержкой в ​​261 шаг. Расширенная последовательность закончилась числом 1 999 291 987 030 606 810 – ее самым большим и последним членом.
• 26 апреля 2019 года Роб ван Нобелен вычислил новый мировой рекорд по самому отложенному палиндромному числу: 12 000 700 000 025 339 936 491 требуется 288 итераций , чтобы получить 142-значный палиндром 663434344554418817836515449766224992. 2269477578658488045222897505659677887769565057982225408848568757749622299422667944515638718814455443434366 .
• 5 января 2021 года Антон Стефанов вычислил два новых палиндромных числа с наибольшей задержкой: 13968441660506503386020 и 13568441660506503386420. Требуется 289 итераций, чтобы получить тот же 142-значный палиндром, что и число Роба ван Нобелена.
• 14 декабря 2021 года Дмитрий Маслов установил новый мировой рекорд по самому запаздывающему палиндромному числу: 1 000 206 827 388 999 999 095 750 требует 293 итераций , чтобы получить 132-значный палиндром 88022661552988847333026526976864644 43334338877338834659967654248544584245676995643883377883343333444646867962562033374888925516622088
• Последовательность OEIS A326414 содержит 19353600 термов с известной в настоящее время задержкой в ​​288 шагов.
• Любое число из A281506 можно использовать в качестве основной базы для построения 261-ступенчатых палиндромов более высокого порядка. Например, на основе 1 999 291 987 030 606 810 получается следующее число 1999291987030606810000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000001999291987030606810 также становится 238-значным палиндромом 445626658789764376224378489766538703888847836625984258559 63436955852489526638748888307835667984873422673467987856626544 4456266587897643762243784897665387038888478366259842585596343 6955852489526638748888307835667984873422673467987856626544 после 261 шага.

Наименьшее число, которое, как известно, не образует палиндром, — 196 . Таким образом, это наименьший кандидат на число Лишрела.

Число, полученное в результате перестановки цифр числа Лишрела, не заканчивающегося нулем, также является числом Лишрела.

Формальное определение процесса

Позволять $n$ быть натуральным числом. Определим функцию Лишрела для системы счисления b > 1: $F_{b}:\mathbb {N} \rightarrow \mathbb {N}$, быть следующим:

$F_{b}(n)=n+\sum _{i=0}^{k-1}d_{i}b^{k-i-1}$

где $k=\lfloor \log _{b}n\rfloor +1$ это количество цифр в числе по основанию $b$, и

$d_{i}={\frac {n{\bmod {b^{i+1}}}-n{\bmod {b}}^{i}}{b^{i}}}$

— значение каждой цифры числа. Число является числом Лишрела, если не существует натурального числа. $i$ такой, что $F_{b}^{i+1}(n)=2F_{b}^{i}(n)$, где $F^{i}$ это $i$-я итерация ​ $F$

Доказательства не найдены

В других системах счисления (эти базы представляют собой степени 2 , например, двоичные и шестнадцатеричные ) можно доказать, что некоторые числа никогда не образуют палиндром после многократного перестановки и сложения. но такого доказательства не было найдено для 196 и других чисел с основанием 10.

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

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 .

Цифры, выделенные жирным шрифтом, соответствуют предполагаемому количеству семян Lychrel (см. ниже). Компьютерные программы Джейсона Дусетта, Яна Питерса и Бенджамина Депре нашли других кандидатов на Lychrel. Действительно, программа Бенджамина Депре выявила все предполагаемые номера семян Lychrel, содержащие менее 17 цифр. На сайте Уэйда Ван Ландингема указано общее количество найденных подозрительных номеров семян Lychrel для каждой длины цифр.

Метод грубой силы, первоначально использованный Джоном Уокером, был усовершенствован, чтобы использовать преимущества итерационного поведения. Например, Вон Сюит разработал программу, которая сохраняет только первые и последние несколько цифр каждой итерации, что позволяет выполнять тестирование шаблонов цифр за миллионы итераций без необходимости сохранять каждую итерацию целиком в файл. Однако до сих пор не разработан алгоритм, позволяющий обойти итерационный процесс обращения и сложения.

Нити, семенные и родственные номера

Термин «нитка» , придуманный Джейсоном Дусеттом, относится к последовательности чисел, которая может или не может привести к палиндрому посредством обратного процесса и процесса сложения. Любое заданное семя и связанные с ним кин -номера сойдутся в одной нити. Нить не включает в себя исходное семя или число родственников , а только числа, которые являются общими для них обоих после их сходимости.

Начальные числа представляют собой подмножество чисел Лишрела, то есть наименьшее число каждой нити, не производящей палиндром. Начальное число само может быть палиндромом. Первые три примера выделены жирным шрифтом в списке выше.

Числа кинов — это подмножество чисел Лишрела, которые включают в себя все номера потока, кроме начального, или любое число, которое сходится в данном потоке после одной итерации. Этот термин был введен Кодзи Ямаситой в 1997 году.

196 квест палиндром

Поскольку 196 ( по основанию 10 ) — это наименьшее число-кандидат Лишрела, оно привлекло наибольшее внимание.

В 1980-х годах проблема палиндрома 196 привлекла внимание любителей микрокомпьютеров : программы поиска Джима Баттерфилда и других появились в нескольких массовых компьютерных журналах. В 1985 году программа Джеймса Киллмана безуспешно работала более 28 дней, выполнив 12 954 прохода и достигнув 5366-значного числа.

Джон Уокер начал свой квест «196 Палиндром» 12 августа 1987 года на рабочей станции Sun 3/260. Он написал программу на языке C , выполняющую итерации обращения и сложения, а также проверяющую наличие палиндрома после каждого шага. Программа работала в фоновом режиме с низким приоритетом и каждые два часа создавала контрольную точку для файла, а при выключении системы записывала достигнутое на данный момент число и количество итераций. Он автоматически перезагружался с последней контрольной точки после каждого выключения. Он действовал почти три года, а затем был прекращен (в соответствии с инструкциями) 24 мая 1990 года с сообщением:

Точка остановки достигнута на перевале 2 415 836.

Номер содержит 1 000 000 цифр.

Число 196 выросло до числа в один миллион цифр после 2 415 836 итераций, не достигнув палиндрома. Уокер опубликовал свои выводы в Интернете вместе с последней контрольной точкой, предложив другим возобновить квест, используя достигнутое на данный момент число.

В 1995 году Тим Ирвин и Ларри Симкинс использовали многопроцессорный компьютер и всего за три месяца достигли отметки в два миллиона цифр, так и не найдя палиндрома. Затем Джейсон Дусетт последовал его примеру и в мае 2000 года достиг 12,5 миллионов цифр. Уэйд ВанЛэндингем использовал программу Джейсона Дусетта, чтобы достичь 13 миллионов цифр, что стало рекордом, опубликованным в Yes Mag: канадском научном журнале для детей. С июня 2000 года Уэйд ВанЛэндингем несет флаг, используя программы, написанные различными энтузиастами. К 1 мая 2006 года ВанЛэндингем достиг отметки в 300 миллионов цифр (при скорости одного миллиона цифр каждые 5–7 дней). Используя распределенную обработку , в 2011 году Ромен Дольбо выполнил миллиард итераций, чтобы получить число из 413 930 770 цифр, а в феврале 2015 года его расчеты достигли числа с миллиардом цифр. Палиндром до сих пор не найден.

Другие потенциальные числа Лишрела, которые также были подвергнуты тому же методу грубой силы с повторным обратным сложением, включают 879, 1997 и 7059: они были подвергнуты нескольким миллионам итераций, но палиндром не был найден.

Другие базы

в системе счисления 2 Доказано, что 10110 (22 в десятичном формате) является числом Лишрела, так как после 4 шагов оно достигает 10110100, через 8 шагов оно достигает 1011101000, через 12 шагов оно достигает 101111010000 и вообще через 4 n шагов оно достигает число, состоящее из 10, за которыми следуют n + 1 единиц, за которыми следует 01, за которыми следуют n + 1 нулей. Очевидно, что это число не может быть палиндромом, и ни одно из других чисел в последовательности не является палиндромом.

Было доказано, что числа Лишрела существуют в следующих основаниях: 11, 17, 20, 26 и всех степенях двойки.

Ни одна база не содержит чисел Лишрела, меньших, чем база. Фактически, в любой заданной системе счисления b ни одно однозначное число не требует более двух итераций для формирования палиндрома. Для b > 4, если k < b /2, то k становится палиндромом после одной итерации: k + k = 2 k , что является однозначным по основанию b (и, следовательно, палиндромом). Если k > b /2, k становится палиндромным после двух итераций.

Наименьшее число в каждом основании, которое могло бы быть числом Лишрела: (последовательность A060382 в OEIS ):

б	Наименьшее возможное число Лишрела в основании b записано по базе b (основание 10)
2	10110 (22)
3	10211 (103)
4	10202 (290)
5	10313 (708)
6	4555 (1079)
7	10513 (2656)
8	1775 (1021)
9	728 (593)
10	196 (196)
11	83А (1011)
12	179 (237)
13	12СА (2701)
14	1ББ (361)
15	1ЭК (447)
16	19Д (413)
17	Б6Г (3297)
18	1АФ (519)
19	Привет (341)
20	ЭйДжей (379)
21	1КИ (711)
22	КЛ (461)
23	ЛМ (505)
24	Миннесота (551)
25	1ФМ (1022)
26	ОП (649)
27	ПК (701)
28	QR-код (755)
29	РС (811)
30	СТ (869)
31	ТУ (929)
32	УФ (991)
33	Фольксваген (1055)
34	1IV (1799)
35	1JW (1922)
36	ЯЗ (1259)

Расширение для отрицательных целых чисел

Числа Лишрела можно расширить до отрицательных целых чисел , используя представление цифр со знаком для представления каждого целого числа.

См. также

• Арифметическая динамика
• Палиндромное число

Внешние ссылки

• Последовательность OEIS A023108 (Положительные целые числа, которые, очевидно, никогда не приводят к палиндрому под ...)
• Джон Уокер – Три года вычислений
• Тим Ирвин – Около двух месяцев вычислений
• Джейсон Дусетт - Мировые рекорды - 196 квестов-палиндромов, самое запаздывающее палиндромное число
• Бенджамин Депре
• 196 и другие числа Ликрела Уэйда ВанЛэндингема
• Вайсштейн, Эрик В. «196-Алгоритм» . Математический мир .
• MathPages — суммы переворота цифр, ведущие к палиндромам
• НомерФайл
• Все известные отложенные палиндромные числа – Дмитрий Маслов, проект MDPN
• Testing a delayed palindrome – Dmitry Maslov, MDPN project