Просмотр кода страницы Проблема 196

'''Проблема числа 196''' или '''Число Лишрел''' ({{lang-en|Lychrel number}}) — это [[натуральное число]], которое не может стать [[палиндром]]ом с помощью [[Итерация (математика)|итеративного]] процесса «перевернуть и сложить» в десятичной системе счисления. Этот процесс называется ''196-алгоритмом''. Название «Lychrel», придуманное Уэйдом ВанЛэндингемом ({{lang-en|Wade VanLandingham}}), — неточная [[анаграмма]] имени его подруги, Шерил ({{lang-en|Cheryl}}). Строго доказанных чисел Лишрел не существует (для десятичной системы счисления; для некоторых других систем счисления доказанные числа Лишрел существуют), но многие числа предполагаются таковыми, причём наименьшее из них — число [https://dmaslov.me/ru/mdpn/checkpal.html?n=196 196].

== Перевернуть и сложить ==
Операция ''«Перевернуть и сложить»'' ({{lang-en|Reverse-and-add}}) заключается в том, чтобы сложить исходное число с его «перевёрнутой» копией, то есть числом, цифры которого записаны в обратном порядке, например: 56 + 65 = 121, 521 + 125 = 646.

Эта операция может быть применена к любому натуральному числу. Если в результате применения этой операции N раз к будет получен [[палиндром]], то такое число называют ''«отложенным палиндромом»'', разрешающимся за N операций. В отличие от отложенных палиндромов, для чисел Лишрел эта операция не приводит к получению палиндрома, сколько бы раз мы её не выполняли.

Некоторые числа (в частности, все однозначные и почти все двузначные числа) становятся палиндромами достаточно быстро — после применения всего нескольких операций. Так, около 80 % всех чисел, меньших 10 000, разрешаются в палиндром за 4 или меньше итерации. Около 91 % — за 7 и меньше итераций. И только два числа — 89 и 98 — требуют необычно много: 24 операции.

Вот несколько примеров отложенных палиндромов:

* 56 становится палиндромом после одной итерации: 56 + 65 = ''121''.
* 57 становится палиндромом после двух итераций: 57 + 75 = 132, 132 + 231 = ''363''.
* 59 становится палиндромом после трёх итераций: 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = ''1111''.
* 89 требует необычно много — [https://dmaslov.me/ru/mdpn/checkpal.html?n=89 24 итерации], прежде чем достичь палиндрома ''8 813 200 023 188'' (это наибольшее количество операций среди чисел до 10 000, о которых на текущий момент времени научному сообществу [https://dmaslov.me/ru/mdpn/records.html точно известно], что они разрешаются в палиндром).
* 10 911 достигает палиндрома ''4 668 731 596 684 224 866 951 378 664'' после [https://dmaslov.me/ru/mdpn/checkpal.html?n=10911 55 итераций].
Наименьшее число, начиная с [[1 (число)|1]], для которого не удалось найти палиндром трёхзначное число [[196 (число)|196]]. Это наименьшее известное потенциальное десятичное число Лишрел.

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

Так, 30 ноября 2005 года Джейсоном Дусеттом ({{lang-en|Jason Doucette}}) с помощью компьютера был найден отложенный палиндром [https://dmaslov.me/ru/mdpn/checkpal.html?n=1186060307891929990 1 186 060 307 891 929 990], который после 261 итерации становится 119-значным палиндромом <small>''44 562 665 878 976 437 622 437 848 976 653 870 388 884 783 662 598 425 855 963 436 955 852 489 526 638 748 888 307 835 667 984 873 422 673 467 987 856 626 544''</small>. Это число являлось мировым рекордом среди [http://www.jasondoucette.com/worldrecords.html#Most наиболее отложенных палиндромов] на протяжении более чем 13 лет.

В мае 2017 года телеканал [[МИР24]] сообщил, что московский школьник Андрей Щебетов обнаружил самый большой известный отложенный палиндром — [https://mir24.tv/news/16134712/moskovskii-shkolnik-otkryl-samoe-bolshoe-chislo-palindrom число 1 999 291 987 030 606 810]. Однако, ничего интересного в этом числе нет, так как оно получено простой перестановкой пар симметричных цифр из числа, обнаруженного Джейсоном Дусеттом. Наибольшим известным 19-значным числом, разрешающимся за 261 итерацию является число [https://dmaslov.me/ru/mdpn/checkpal.html?n=1999999936042548910 1 999 999 936 042 548 910], а самое большое известное число состоит из [https://dmaslov.me/ru/mdpn/checkpal.html?n=29993253499999991004282194000000540 35 цифр].

26 апреля 2019 года Роб ван Нобелен ([[Нидерландский язык|нидер.]] ''Rob van Nobelen'') установил новый мировой рекорд среди наиболее отложенных палиндромов: 23-значное число [https://dmaslov.me/ru/mdpn/checkpal.html?n=12000700000025339936491 12 000 700 000 025 339 936 491], которое превращается в палиндром за 288 шагов.

5 января 2021 года Антон Стефанов опубликовал<ref>{{Статья|ссылка=https://habr.com/ru/post/536104/|автор=Антон Стефанов (stefanov94)|заглавие=Откладываем палиндромы на новый год|год=2021|язык=Русский|издание=Хабр|тип=сайт|месяц=январь|число=5|том=|номер=|страницы=|issn=|archivedate=2021-01-07|archiveurl=https://web.archive.org/web/20210107144456/https://habr.com/ru/post/536104/}}</ref> 23-значные числа [https://dmaslov.me/ru/mdpn/checkpal.html?n=13968441660506503386020 13 968 441 660 506 503 386 020] и [https://dmaslov.me/ru/mdpn/checkpal.html?n=13568441660506503386420 13 568 441 660 506 503 386 420], которые за 289 шагов превращаются в тот же палиндром, что и число, найденное Робом ван Нобеленом, установив новый рекорд. 14 октября 2021 года Дмитрий Маслов сообщил<ref>{{Статья|ссылка=https://dmaslov.me/news.html#211014|автор=Дмитрий Маслов (Dmitry Maslov)|заглавие=Найден наименьший отложенный палиндром для шага 289|год=2021|язык=Русский|издание=Проект iLWN|тип=сайт|месяц=октябрь|число=14|том=|номер=|страницы=|issn=|archivedate=2021-11-06|archiveurl=https://web.archive.org/web/20211106134420/https://dmaslov.me/news.html#211014}}</ref> о том, что им было найдено меньшее 23-значное число, разрешающееся за 289 итераций: [https://dmaslov.me/ru/mdpn/checkpal.html?n=10036069400174999499950 10 036 069 400 174 999 499 950].

14 декабря 2021 года Дмитрий Маслов установил<ref>{{Статья|ссылка=https://dmaslov.me/news.html#211214|автор=Дмитрий Маслов (Dmitry Maslov)|заглавие=Установлен новый мировой рекорд среди отложенных палиндромов: 293 итерации!|год=2021|язык=русский|издание=iLWN|тип=сайт|месяц=декабрь|число=14|archivedate=2021-11-06|archiveurl=https://web.archive.org/web/20211106134420/https://dmaslov.me/news.html#211214}}</ref> новый мировой рекорд среди наиболее отложенных палиндромов: 25-значное число [https://dmaslov.me/ru/mdpn/checkpal.html?n=1000206827388999999095750 1 000 206 827 388 999 999 095 750], которое в результате 293 итераций становится 132-значным палиндромом. Это число является текущим мировым рекордом среди наиболее отложенных палиндромов.

Последовательность OEIS [[oeis:A326414|A326414]] содержит 19 353 600 чисел, превращающихся в палиндром после 288 шагов.

Последовательность [[oeis:A281506|А281506]] содержит список из 108 864 отложенных палиндромов, требующих 261 итерацию для превращения в палиндром. Она начинается с 1 186 060 307 891 929 990 и заканчивается [https://mir24.tv/news/16134712/moskovskii-shkolnik-otkryl-samoe-bolshoe-chislo-palindrom 1 999 291 987 030 606 810].

== Формульное объяснение ==
Допустим, что <math>\mathcal{n}</math> — натуральное число. Определим '''функцию Лишрел''' для '''базовых чисел''' (см. связанные определения) <math display="inline">b>1\ F_b:\N\rightarrow\N </math> следующим образом:

<math>F_b(n)=n\ + \sum_{i=0}^{k-1}d_ib^{k-i-1} </math>,

где <math>k=\lfloor\log_b n\rfloor+1</math> это количество цифр в базовом числе <math>b</math>, а

<math>d_i=\frac{n\bmod b^{i+1}-n\bmod b^i}{b^i} </math>

значение каждой цифры числа. Число является '''числом Лишрел,''' если не существует такого натурального числа <math>i</math>, что <math>F^{i+1}_b(n)=2F^i_b(n)</math>, где <math>F^i</math> это [[Итерация (математика)|<math>i</math> итераций]] <math>F</math>.

== Новая проблема ==
В других [[Система счисления|системах счисления]] для некоторых чисел может быть доказано, что они не образуют никогда палиндром после последовательных итераций<ref>{{cite web |url=http://www.math.niu.edu/~rusin/known-math/96/palindrome |title=Архивированная копия |accessdate=2006-05-29 |archiveurl=https://web.archive.org/web/20060516143033/http://www.math.niu.edu/~rusin/known-math/96/palindrome |archivedate=2006-05-16 }}</ref><ref>{{Cite web |url=http://www.mathpages.com/home/kmath004.htm |title=Digit Reversal Sums Leading to Palindromes<!-- Заголовок добавлен ботом --> |accessdate=2011-01-04 |archiveurl=https://web.archive.org/web/20100206113915/http://mathpages.com/home/kmath004.htm |archivedate=2010-02-06 |deadlink=yes }}</ref>, но не было обнаружено таких доказательств для 196 и других десятичных чисел.

Существует [[гипотеза]], что 196 и другие числа, которые пока ещё не стали палиндромом, являются числами Лишрел, но ни для одного числа нет строгого доказательства, что они являются таковыми. Подобные числа неофициально называют «кандидаты в числа Лишрел». Первые несколько кандидатов в чисел Лишрел {{OEIS|A023108}}:
: '''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 цифр<ref>{{Cite web |url=http://www.p196.org/lychrel%20records.html |title=Архивированная копия |accessdate=2011-01-04 |archiveurl=https://web.archive.org/web/20100318053921/http://www.p196.org/lychrel%20records.html |archivedate=2010-03-18 |deadlink=yes }}</ref>. Сайт Уэйда ВанЛэндингема содержит списки базовых чисел Лишрел для каждой длины числа<ref>{{Cite web |url=http://www.p196.org/lychrel%20seeds.html |title=Архивированная копия |accessdate=2011-01-04 |archiveurl=https://web.archive.org/web/20100726131749/http://www.p196.org/lychrel%20seeds.html |archivedate=2010-07-26 |deadlink=yes }}</ref>.

[[Полный перебор|Метод полного перебора]], первоначально разработанный Джоном Уокером, был усовершенствован, чтобы использовать поведение при итерациях. Например, существует программа, созданная Вон Сьют, и она сохраняет только первые и последние несколько цифр каждой итерации, позволяя тестировать цифровые закономерности на протяжении миллионов итераций без необходимости сохранения каждой итерации в файл<ref>{{cite web |url=http://home.cfl.rr.com/p196/math%20solutions.html |title=Архивированная копия |accessdate=2006-10-15 |archiveurl=https://web.archive.org/web/20061015175443/http://home.cfl.rr.com/p196/math%20solutions.html |archivedate=2006-10-15 }} </ref>. Но пока не было придумано [[алгоритм]]а, который бы обходил итеративный процесс.

== Связанные определения ==
[[Файл:Lychrel numbers - 196 thread.svg|thumb|upright|Поток числа 196 и родственных с ним чисел]]
Термин '''нить''' или '''поток''' ({{lang-en|thread}}) придумал Джейсон Дусетт, обозначая так [[последовательность]] чисел, получаемых в результате итераций первоначального числа. '''Базовое число''' ({{lang-en|seed}}) и его связанные '''родственные''' ({{lang-en|kin}}) числа сходятся в одном потоке. Поток не включает исходное '''базовое''' число или его '''родственника''', но только числа, которые являются общими для обоих, после того, как они сойдутся.

'''Базовые числа''' представляют собой [[подпоследовательность]] чисел Лишрел, то есть наименьшее число из каждого не производящего палиндром потока. Базовое число может быть само по себе палиндромом. Первые три примера выделены полужирным шрифтом в приведённом выше списке.

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

== Эстафета числа 196 ==
Поскольку число [[196 (число)|196]] является наименьшим кандидатом в числа Лишрел, оно получило наибольшее внимание.

{{нп1|Джон Уокер (программист)|Джон Уокер|en|John Walker (programmer)}} начал эстафету, посвящённую изучению потока «196», 12 августа 1987 года на рабочей станции [[Sun Microsystems|Sun]] 3/260. Он написал программу на [[Си (язык программирования)|C]], которая выполняет итерации «перевернуть и сложить» и проверяет на палиндром после каждого шага. Программа была запущена в [[Фоновый режим|фоновом режиме]] с низким приоритетом. Она сбрасывала итерационные результаты в файл каждые два часа и в момент закрытия системы, записывая достигнутые к тому времени число и номер итерации. Она перезапускалась сама автоматически из последней контрольной точки после каждого включения компьютера. Она работала в течение почти трёх лет, а затем остановилась (как было запрограммировано) 24 мая 1990 года с сообщением:
{{Цитата|
: Достигнута точка остановки на проходе 2 415 836.
: Число содержит 1 000 000 цифр.
{{oq|en|Stop point reached on pass 2,415,836. <br>Number contains 1,000,000 digits.}}
}}

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

В [[1995 год]]у Тим Ирвин использовал [[суперкомпьютер]] тех лет, достигнув отметки в два миллиона цифр всего за три месяца, опять не найдя палиндром. Джейсон Дусетт затем присоединился к этому количественному направлению и достиг 12,5 миллионов цифр в мае 2000 года. Уэйд ВанЛэндингем, используя программу Джейсона Дусетта, достиг 13 миллионов цифр, что было опубликовано<ref>[http://www.jasondoucette.com/yesmagazine/yes-magazine-75-dpi.jpg Coming or Going?]{{ref-en}}</ref> в [[Yes Mag]] — канадском научном журнале для детей. С июня 2000 года Уэйд ВанЛэндингем продолжал нести флаг первенства, используя программы, написанные различными энтузиастами. К 1 мая 2006 года ВанЛэндингем достиг отметки 300 миллионов цифр (со скоростью одного миллиона цифр каждые 5-7 дней). Используя [[распределённые вычисления]], в 2011 году Ромен Дольбо ([[Французский язык|фр.]] ''Romain Dolbeau'') совершил миллиард итераций и получил число, состоящее из 413 930 770 цифр<ref>{{Cite web |url=http://www.isc-events.com/isc14_ap/presentationdetails.htm?t=presentation&o=264&a=select&ra=sessiondetails |title=The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest |access-date=2015-01-17 |archive-date=2015-04-19 |archive-url=https://web.archive.org/web/20150419100449/http://www.isc-events.com/isc14_ap/presentationdetails.htm?t=presentation&o=264&a=select&ra=sessiondetails |deadlink=no }}</ref>, в июле 2012 года его вычисления достигли числа с 600 млн цифр, а в феврале 2015 количество цифр перевалило за 1 миллиард<ref>{{Cite web |url=http://www.dolbeau.name/dolbeau/p196/p196.html |title=The p196_mpi page |access-date=2015-01-17 |archive-date=2015-02-11 |archive-url=https://web.archive.org/web/20150211062852/http://dolbeau.name/dolbeau/p196/p196.html |deadlink=no }}</ref>, но палиндром так и не был обнаружен.

Другие кандидаты в числа Лишрел, которые подвергались такому же перебору, включают 879, 1997, 7059 и другие базовые числа: они были прослежены на протяжении миллионов и десятков миллионов итераций без обнаружения палиндрома<ref>{{cite web|url=http://home.cfl.rr.com/p196/lychrel+records.html|title=Lychrel Records|archiveurl=https://web.archive.org/web/20061021025636/http://home.cfl.rr.com/p196/lychrel+records.html|archivedate=2006-10-21}}</ref><ref>{{cite web|url=https://dmaslov.me/p196/|title=Поиск палиндрома 196 — Проект iLWN|access-date=2021-11-06|archive-date=2021-11-06|archive-url=https://web.archive.org/web/20211106141309/https://dmaslov.me/p196/|deadlink=no}}</ref>.

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://www.fourmilab.ch/documents/threeyears/threeyears.html Джон Уокер]{{ref-en}} — три года вычислений.
* [http://www.fourmilab.ch/documents/threeyears/two_months_more.html Тим Ирвин]{{ref-en}} — около двух месяцев вычислений.
* [http://www.jasondoucette.com/worldrecords.html Джейсон Дусетт — Мировые рекорды]{{ref-en}} — «Эстафета числа 196», наиболее отложенные палиндромы.
* [http://users.tmok.com/~pla/Lychrel/Lychrel.shtml Бенджамин Деспрес]{{ref-en}}.
* [https://web.archive.org/web/20061104023524/http://www.p196.org/ 196] и другие числа Лишрел. Сайт Wade VanLandingham{{ref-en}}.
* {{MathWorld|urlname=196-Algorithm|title=196-Algorithm}}
* {{MathWorld|urlname=LychrelNumber|title=Lychrel Number}}
* {{MathWorld|urlname=PalindromicNumberConjecture|title=Palindromic Number Conjecture}}
* {{MathWorld|urlname=Reverse-Then-AddSequence|title=Reverse-Then-Add Sequence}}
* [https://web.archive.org/web/20100206113915/http://mathpages.com/home/kmath004.htm MathPages — цифра перенос суммы, приведшие к Palindromes]
* [https://web.archive.org/web/20160304191337/http://dostoyaniye.com/arhiv/number5/ziskin.html Рассказы о математиках.] Клара Зискин. Упоминание проблемы в русскоязычной литературе.
* [https://dmaslov.me/ru/mdpn/records.html Все известные отложенные палиндромы] — Дмитрий Маслов, проект MDPN.
* [https://dmaslov.me/ru/mdpn/checkpal.html Проверка отложенного палиндрома] — Дмитрий Маслов, проект MDPN.

[[Категория:Целочисленные последовательности, зависящие от системы счисления]]
[[Категория:Математические гипотезы]]