Проблема 196: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Интернет#Написание (к сожалению, источник лучше не нашел)
→Открытая проблема: Добавил шаблон. Шаблон:Переход, cc by-sa 3.0, ru-wiki, авторы - Special:History/Шаблон:Переход, изменений не внесено, кроме, собственно, ссылки.
Строка 35: Строка 35:
: '''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'''.
: '''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>. Сайт Wade VanLandingham содержит списки базовых чисел Лишрел для каждой длины числа.<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>
Выделенные жирным считаются базовыми числами Лишрел (см. ниже{{Переход|Связанные определения}}). Компьютерные программы Джейсона Дусетта, Яна Петерса и Бенджамина Деспреса нашли другие кандидаты Лишрел. Более того, Бенджамин Деспрес выявил все базовые числа Лишрел, состоящие из менее, чем 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>. Сайт Wade VanLandingham содержит списки базовых чисел Лишрел для каждой длины числа.<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>


[[Полный перебор|Метод полного перебора]], первоначально разработанный Джоном Уокером, был усовершенствован, чтобы использовать поведение при итерациях. Например, Vaughn Suite разработал программу, которая сохраняет только первые и последние несколько цифр каждой итерации, позволяя тестировать цифровые закономерности на протяжении миллионов итераций без необходимости сохранения каждой итерации в файл<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>. Но пока не было придумано [[алгоритм]]а, который бы обходил итеративный процесс.
[[Полный перебор|Метод полного перебора]], первоначально разработанный Джоном Уокером, был усовершенствован, чтобы использовать поведение при итерациях. Например, Vaughn Suite разработал программу, которая сохраняет только первые и последние несколько цифр каждой итерации, позволяя тестировать цифровые закономерности на протяжении миллионов итераций без необходимости сохранения каждой итерации в файл<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>. Но пока не было придумано [[алгоритм]]а, который бы обходил итеративный процесс.

Версия от 11:58, 28 декабря 2019

Проблема 196 — условное название нерешённой математической задачи: неизвестно, приведёт ли операция «перевернуть и сложить», применённая к числу 196 какое-то количество раз, к палиндрому — числу, читающемуся с конца так же, как с начала.

Число Лишрел (англ. Lychrel number) — это натуральное число, которое не может стать палиндромом с помощью итеративного процесса «перевернуть и сложить» в десятичной системе счисления. Этот процесс называется 196-алгоритмом. Название «Lychrel», придуманное Уэйдом ВанЛэндингхэмом (англ. Wade VanLandingham), — примерная анаграмма имени его подруги — Шерил (англ. Cheryl). Строго доказанных чисел Лишрел не существует (для десятичной системы счисления; для некоторых других систем счисления доказанные числа Лишрел существуют), но многие числа предполагаются таковыми, причём наименьшее из них — 196.

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

«Перевернуть и сложить» (англ. reverse-and-add) — название операции, выполняемой над числом. Суть заключается в сложении исходного десятичного числа с его перевёрнутой копией (числом, записанным с конца). Например, 56 + 65 = 121, 521 + 125 = 646.

Некоторые числа (в частности, все однозначные и двузначные числа) становятся палиндромами достаточно быстро — после нескольких применений операции, и поэтому не являются числами Лишрел. Около 80 % всех чисел, меньших 10000, разрешаются в палиндром в 4 или меньше шагов. Около 90 % — за 7 и меньше шагов.

Вот несколько примеров чисел не-Лишрел:

  • 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.

26 апреля 2019 года Rob van Nobelen установил новый мировой рекорд: 23-значное число 12 000 700 000 025 339 936 491 превращается в палиндром за 288 шагов.

Последовательность OEIS A326414 содержит 19353600 чисел, известных в настоящее время, превращающихся в палиндром после 288 шагов.

Последовательность А281506 содержит полный список первых 108864 наиболее отложенных палиндромов, требующих 261 итерацию для превращения в палиндром. Она начинается с 1186060307891929990 и заканчивается 1999291987030606810.

Первое известное число, начиная с 0, которое, видимо, не образует палиндром, — трёхзначное число 196. Это наименьший номер кандидата Lychrel.

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

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

Существует гипотеза, что 196 и другие числа, которые пока ещё не стали палиндромом, являются числами Лишрел, но ни для одного числа нет строгого доказательства, что оно Лишрел. Подобные числа неофициально называют «кандидаты в числа Лишрел». Первые несколько кандидатов в Лишрел последовательность 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.

Выделенные жирным считаются базовыми числами Лишрел (см. ниже➤). Компьютерные программы Джейсона Дусетта, Яна Петерса и Бенджамина Деспреса нашли другие кандидаты Лишрел. Более того, Бенджамин Деспрес выявил все базовые числа Лишрел, состоящие из менее, чем 17 цифр[3]. Сайт Wade VanLandingham содержит списки базовых чисел Лишрел для каждой длины числа.[4]

Метод полного перебора, первоначально разработанный Джоном Уокером, был усовершенствован, чтобы использовать поведение при итерациях. Например, Vaughn Suite разработал программу, которая сохраняет только первые и последние несколько цифр каждой итерации, позволяя тестировать цифровые закономерности на протяжении миллионов итераций без необходимости сохранения каждой итерации в файл[5]. Но пока не было придумано алгоритма, который бы обходил итеративный процесс.

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

Поток числа 196 и родственных с ним чисел

Термин нить или поток (англ. thread) придумал Джейсон Дусетт, обозначая так последовательность чисел, получаемых в результате итераций первоначального числа. Базовое число (англ. seed) и его связанные родственные (англ. kin) числа сходятся в одном потоке. Поток не включает исходное базовое число или его родственника, но только числа, которые являются общими для обоих, после того, как они сойдутся.

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

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

Квест 196

Поскольку число 196 является наименьшим кандидатом в числа Лишрел, оно получило наибольшее внимание.

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

Достигнута точка остановки на проходе 2 415 836.
Число содержит 1 000 000 цифр.
Оригинальный текст (англ.)
Stop point reached on pass 2,415,836.
Number contains 1,000,000 digits.

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

В 1995 году Тим Ирвин использовал суперкомпьютер и достиг отметки в два миллиона цифр всего за три месяца, опять не найдя палиндрома. Джейсон Дусетт затем последовал их примеру и достиг 12,5 миллионов цифр в мае 2000 года. Wade VanLandingham, используя программу Джейсона Дусетта, достиг 13 миллионов цифр, что было опубликовано[6] в Yes Mag — канадском научном журнале для детей. С июня 2000 года VanLandingham продолжал нести флаг первенства, используя программы, написанные различными энтузиастами. К 1 мая 2006 года VanLandingham достиг отметки 300 миллионов цифр (со скоростью одного миллиона цифр каждые 5-7 дней). Используя распределённые вычисления, в 2011 году Romain Dolbeau совершил миллиард итераций и получил число, состоящее из 413 930 770 цифр[7], в июле 2012 года его вычисления достигли числа с 600 млн цифр, а в феврале 2015 число цифр перевалило за 1 миллиард[8], но палиндром так и не был обнаружен.

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

Примечания

  1. ↑ Архивированная копия. Дата обращения: 29 мая 2006. Архивировано 16 мая 2006 года.
  2. ↑ Digit Reversal Sums Leading to Palindromes. Дата обращения: 4 января 2011. Архивировано из оригинала 6 февраля 2010 года.
  3. ↑ Архивированная копия. Дата обращения: 4 января 2011. Архивировано из оригинала 18 марта 2010 года.
  4. ↑ Архивированная копия. Дата обращения: 4 января 2011. Архивировано из оригинала 26 июля 2010 года.
  5. ↑ Архивированная копия. Дата обращения: 15 октября 2006. Архивировано 15 октября 2006 года.
  6. ↑ Coming or Going? (англ.)
  7. ↑ The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest
  8. ↑ The p196_mpi page
  9. ↑ Lychrel Records. Архивировано 21 октября 2006 года.

Ссылки

Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Проблема_196&oldid=104209008