Добро пожаловать на домашнюю страницу проекта «Most Delayed Palindromic Number» или просто MDPN! Основная цель этого проекта — поиск наиболее отложенных палиндромов.

Наиболее отложенный палиндром, известный на данный момент (текущий мировой рекорд), разрешается за 293 операции Перевернуть-И-Сложить. Это 25-значное число 1,000,206,827,388,999,999,095,750. Оно было найдено 14 декабря 2021 года этим проектом.

Данная страница находится в разработке. Но уже сейчас Вы можете проверить, является ли некоторое натуральное число отложенным палиндромом или числом Лишрел. А также ознакомиться со списком всех известных на данный момент отложенных палиндромов. На странице «Термины и определения» есть описание некоторых терминов и понятий, используемых в проекте (страница всё ещё дополняется).

Также Вы можете заглянуть в блог проекта iLWN. Пока там всего-ничего, но я постараюсь в ближайшее время добавить больше интересной информации. Вот здесь лежит старый Дневник проекта (для тех, кому интересно, как всё начиналось). И, конечно, если где-то здесь есть ещё что-то интересное, о чём я не упомянул, то оно точно будет на карте сайта.

Проект MDPN был начат 2 июня 2019 года. И за прошедшее время были проверены все натуральные числа от 1 и до последнего 22-значного числа. В данный момент проверяются числа 23-значного диапазона (прогресс проверки отображается на главной странице).

Процесс этот достаточно ресурсоёмкий, так как единственный известный на данный момент способ — это метод полного перебора (brute-force), то есть проверка каждого числа в диапазоне. Благодаря некоторым оптимизациям, проверять приходится не все числа, а лишь малую их часть. Однако даже при этом, количество проверяемых чисел измеряется сотнями триллионов (для диапазонов 22- и 23-значных чисел), и быстро увеличивается с ростом их длины.

Кандидаты в отложенные палиндромы

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

Помимо этого, с недавнего времени проект использует так называемый метод прямого и обратного вывода, который позволяет находить новые отложенные палиндромы в пределах всего текущего проверяемого диапазона и даже за его пределами.

В обоих случаях возникает ситуация, когда для найденного отложенного палиндрома нельзя утверждать, что он достоверно наименьший. И всё потому, что среди других непроверенных до него чисел может найтись меньшее число, разрешающееся за такое же количество итераций. Такие числа принято называть кандидатами в отложенные палиндромы.

В данный момент проверяются 23-значные числа. Наибольшим числом, перед которым нет других непроверенных натуральных чисел, по состоянию на 15 февраля 2022 года, 0:47 UTC является число 10,000,406,006,593,697,988,159. Среди наименьших отложенных палиндромов для всех 293 известных на данный момент шагов, наименьшие числа для шагов 237, 241-245, 248, 262-285, 288-292 и рекордного шага 293 (всего 37 отложенных палиндромов) пока считаются кандидатами.

Результирующие палиндромы и обратный вывод

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

Поэтому существующая база данных была проанализирована и из неё были извлечены более 30 уникальных результирующих палиндромов вместе с соответствующими им наиболее отложенными палиндромами, которые разрешаются за 230 и более итераций. Полный список находится здесь.

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

В случае обнаружения отложенного палиндрома, которому требуется немного меньше итераций, чем известному наиболее отложенному палиндрому (текущему мировому рекорду), с помощью метода обратного вывода с очень большой вероятностью можно получить новый мировой рекорд!