Термины и определения

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

Я постарался добавить ссылки на всех страницах, где тот или иной термин употребляется впервые. Но если Вам где-то встретится непонятное слово или словосочетание, не снабжённое ссылкой, то Вы наверняка найдёте его здесь.

Эта страница находится в разработке, поэтому чего-то нужного на ней может не быть. Отсутствующие термины и определения будут добавлены позже. Спасибо за понимание!
ALSN
iLWN
MDPN
P196
RAA
Reverse-And-Add
RSN
базовое число Лишрел
глубина поиска
достоверно наименьший ОП
итерация
кандидат (ОП)
канонический вид
число Лишрел
локальный рекорд
мировой рекорд
наиболее отложенный палиндром
наименьший отложенный палиндром
обратный вывод
отложенный палиндром
палиндром
Перевернуть-И-Сложить
поток числа
прямой вывод
родственное число Лишрел
шаг
• • •
ALSN (проект)

Проект ALSN является частью iLWN. Его короткое имя — это акроним от All Lychrel Seed Numbers. В переводе на русский «Все базовые числа Лишрел». Из названия следует, что основная задача этого проекта — поиск всех базовых чисел Лишрел, начиная от самого первого числа 196 и далее.

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

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

Помимо поиска базовых чисел Лишрел, проектом ALSN собирается различная статистика, например, по «сходимости» чисел Лишрел и их распределению внутри диапазонов, а также ищутся другие интересные особенности.

В то время, как проект MDPN ищет отложенные палиндромы и пропускает числа Лишрел, а проект P196 проверяет, что базовые числа Лишрел не могут стать палиндромами, проект ALSN выясняет, какие именно числа Лишрел следует проверять (базовые), а какие из них можно не проверять (родственные). Также он выполняет достаточно большое количество (десятки тысяч) операций Перевернуть-И-Сложить над каждым найденным числом. Это гарантирует, что проектом MDPN не будет пропущен ни один отложенный палиндром.

В данный момент проект ALSN находится в ранней стадии разработки. В качестве эксперимента было написано некоторое количество исходного кода и проделан небольшой объём вычислений: найдены все базовые числа до 12-значных включительно. Для каждого из них было выполнено по 23,000 итераций. А в рамках проекта P196 для самых первых — значительно больше.

• • •
iLWN (серия проектов)

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

В настоящее время iLWN объединяет 3 проекта:

Аббревиатура iLWN — это сокращение от In Love With Numbers, что переводится на русский язык как «Влюблённые в числа». Название было придумано ещё в июне 2019 года. Но так как на тот момент существовал лишь проект MDPN, то я использовал только его название, чтобы избежать путаницы.

В конце лета 2021 года начались работы по улучшению и расширению этого веб-сайта. А уже в сентябре был начат второй проект — P196. И теперь этот сайт вполне может называться домашней страницей проекта iLWN!

Во всех проектах iLWN я придерживаюсь принципа полной открытости. Все результаты, полученные в рамках исследований, доступны публично: я стараюсь рассказывать обо всём, что имеет хоть какое-то значение, и стараюсь предоставить возможность скачать любые данные. Весь исходный код проектов, как и исходники этого веб-сайта также доступны в публичном репозитории на GitHub. Любой желающий может использовать их в любых целях, с единственным условием — указывать источник.

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

• • •
MDPN (проект)

Проект MDPN является старейшим подпроектом iLWN. Его сокращённое имя — это акроним от Most Delayed Palindromic Number. В переводе на русский «Наиболее отложенное число-палиндром». Из названия следует, что основная цель проекта — поиск наиболее отложенных палиндромов.

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

Поиск отложенных палиндромов — главная задача проекта MDPN, но не единственная. Все найденные числа сохраняются в огромную базу данных. Также собирается различная статистика, например, точное полное количество чисел Лишрел в каждом диапазоне. Анализ этих данных помогает находить интересные особенности отложенных палиндромов. Кроме того, эта база данных используется в проекте ALSN, который занимается поиском базовых чисел Лишрел.

Проект MDPN стартовал 2 июня 2019 года как самостоятельный проект (в то время iLWN был только идеей, другие его проекты были начаты лишь в 2021 году). В рамках этого проекта я перепроверил все наименьшие отложенные палиндромы, найденные другими исследователями раньше, а также нашёл новые. Собрал в базе данных все канонические отложенные палиндромы для шагов от 50 и выше. Полностью проверил все диапазоны десятичных чисел до 22-значных включительно (по состоянию на 1 апреля 2021 года). И продолжаю поиск дальше.

• • •
P196 (проект)

Проект P196 был начат 19 сентября 2021 года, является частью iLWN. Его полное название «196 Palindrome Quest» переводится на русский как «Поиск палиндрома 196». Иногда также встречается перевод «Эстафета числа 196» или «Квест числа 196».

Цель этого проекта — проверить, смогут ли какие-либо из базовых чисел Лишрел стать палиндромами в результате многократного выполнения над ними операции Перевернуть-И-Сложить.

Для этого над числами, найденными проектом ALSN, выполняются десятки и сотни миллионов итераций. После чего, как и в проекте ALSN, проверяется, что все они продолжают свои уникальные потоки.

Кроме самого первого числа Лишрел — числа 196 — и первых базовых чисел 879, 1,997, 7,059 и 9,999 в рамках проекта P196 проверяются тысячи других базовых чисел Лишрел.

• • •
RAA (операция)

Аббревиатура RAA — это сокращение от Reverse-And-Add (то же самое, что и Перевернуть-И-Сложить), обозначающее математическую операцию, применимую к любому натуральному числу. Её суть заключается в том, чтобы сложить исходное число с его «перевёрнутой» копией, то есть числом, цифры которого записаны в обратном порядке.

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

• • •
Reverse-And-Add (операция)

Операция Reverse-And-Add, сокращённо RAA, — математическая операция (то же самое, что и Перевернуть-И-Сложить), которую можно применить к любому натуральному числу. Её суть заключается в том, чтобы сложить исходное число с его «перевёрнутой» копией, то есть числом, цифры которого записаны в обратном порядке.

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

• • •
RSN

Аббревиатура RSN — это сокращение от Reliably Smallest Number (дословно «достоверно наименьшее число»), применяемое по отношению к наименьшему отложенному палиндрому и означающее, что были проверены абсолютно все натуральные числа, меньшие его, и что среди них нет отложенных палиндромов, разрешающихся за такое же количество итераций.

Понятие достоверно наименьшего отложенного палиндрома неразрывно связано с понятием кандидата.

• • •
Глубина поиска

Глубиной поиска называется количество операций Перевернуть-И-Сложить, которое выполняется над каждым проверяемым числом в процессе поиска отложенных палиндромов. Значение глубины зависит от диапазона проверяемых чисел, обычно одинаково для всех чисел в одном диапазоне и увеличивается с ростом количества цифр в числе.

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

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

• • •
Достоверно наименьший отложенный палиндром

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

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

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

• • •
Итерация

Термин итерация (от лат. iteratio — «повторение») в широком смысле означает повторение какого-либо действия. Говоря об отложенных палиндромах или числах Лишрел, под итерацией понимают выполнение одной операции Перевернуть-И-Сложить внутри цикла.

Например, когда говорят «5 итераций», то имеют в виду, что над некоторым числом было подряд выполнено пять операций Перевернуть-И-Сложить.

• • •
Кандидат (отложенный палиндром)

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

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

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

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

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

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

Числа Лишрел делятся на базовые и родственные. Базовые числа начинают так называемые потоки. А родственные им числа Лишрел сходятся с ними в этих потоках.

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

Точнее говоря, на самом деле мы не знаем, получится когда-нибудь в результате палиндром или нет. Это нерешённая математическая задача (по крайней мере для десятичных чисел), получившая условное название «Проблема 196» (англ. «196 Palindrome quest»), также иногда называемая «Квест 196» или «Эстафета числа 196». Поиском палиндрома для этого числа занимается проект P196.

Для десятичной системы счисления не существует строго доказанных чисел Лишрел, но многие числа предполагаются таковыми. В других основаниях (11, 17, 20, 26, а также любой степени 2 — 2, 4, 8, 16 и др.) для некоторых чисел может быть доказано, что они никогда не образуют палиндром после последовательных итераций. В рамках проектов ALSN, MDPN и P196 рассматриваются только десятичные числа Лишрел.

Интересно, что 196 не является единственным подобным числом. В действительности таких чисел бесконечно много. Вот, например, ещё несколько: 879, 1,997, 10,728, 349,762. Более того, по данным, полученным в проекте MDPN, чем длиннее числа, тем среди них больше чисел Лишрел.

Например, все одно- и 2-значные числа являются отложенными палиндромами. Среди всех 3-значных таких чисел всего 13 (примерно 1.4%). Среди 5-значных их уже 5,842 (или 6.5%). Среди 10-значных — более 4 миллиардов (или 48.3%). А среди 22-значных — 96.059%!

• • •
Локальный рекорд

Локальный рекорд — это наиболее отложенный палиндром, то есть такой отложенный палиндром, которому требуется наибольшее среди всех других отложенных палиндромов количество операций Перевернуть-И-Сложить для того, чтобы стать палиндромом.

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

Так, когда 24 ноября 2019 года проектом MDPN было найдено число 1,186,060,307,891,929,990, разрешающееся за 261 шаг, оно стало локальным рекордом, так как это число впервые было обнаружено в ноябре 2005 года другим исследователем.

Но когда 14 декабря 2021 года проектом MDPN был найден наименьший отложенный палиндром, разрешающийся за 293 шага, он стал новым мировым рекордом, сменив предыдущий, установленный Антоном Стефановым (Anton Stefanov), так как потребовал на 4 итерации больше для того, чтобы стать палиндромом.

• • •
Мировой рекорд

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

Действующим мировым рекордом среди отложенных палиндромов является 25-значное число 1,000,206,827,388,999,999,095,750, разрешающееся за 293 итерации. Оно было найдено 14 декабря 2021 года проектом MDPN.

Предыдущий мировой рекорд среди отложенных палиндромов требовал 289 итераций, и был обнаружен 4 января 2021 года Антоном Стефановым (Anton Stefanov).

• • •
Наиболее отложенный палиндром

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

Среди чисел, требующих такого количества итераций, лишь отложенные палиндромы для шагов 286 и 287 являются на данный момент достоверно наименьшими, в то время как все остальные (для шагов от 262 до 285, а также от 288 до 293) пока считаются кандидатами. Иными словами, мы пока не знаем наверняка, являются ли они наименьшими из всех возможных отложенных палиндромов, разрешающихся за соответствующее количество итераций.

Наиболее отложенный палиндром, известный на данный момент, требует 293 итерации и является текущим мировым рекордом среди наиболее отложенных палиндромов. Он был обнаружен 14 декабря 2021 года проектом MDPN, и в настоящий момент считается кандидатом.

• • •
Наименьший отложенный палиндром

Наименьший отложенный палиндром (для шага N) — это наименьшее число среди всех проверенных натуральных чисел, которые разрешаются за N итераций. Иными словами — это наименьший среди всех известных в данный момент отложенных палиндромов для шага N.

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

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

• • •
Отложенный палиндром

В отличие от обычного палиндрома, отложенный палиндром (сокращённо ОП) — это такое натуральное число, которое становится палиндромом после одной или нескольких операций Перевернуть-И-Сложить (Reverse-And-Add, сокращённо RAA), выполненных над ним. Причём само исходное число может являться палиндромом, а может и нет.

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

  1. Возьмите некоторое целое положительное число.
  2. Переставьте цифры числа задом наперёд и прибавьте получившееся число к исходному.
  3. Если число, полученное в результате, не является палиндромом, перейдите к шагу 2.

Примеры отложенных палиндромов в десятичной системе счисления:

Число 12
1. 12 + 21 = 33
Число 37
1. 37 + 73 = 110
2. 110 + 011 = 121
Число 59
1. 59 + 95 = 154
2. 154 + 451 = 605
3. 605 + 506 = 1111
Число 78
1. 78 + 87 = 165
2. 165 + 561 = 726
3. 726 + 627 = 1353
4. 1353 + 3531 = 4884

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

Разные числа требуют разного количества итераций, чтобы превратиться в палиндром. А некоторые из них (так называемые числа Лишрел) вообще никогда не становятся палиндромами. Множество всех отложенных палиндромов, как и множество всех натуральных чисел бесконечно. Однако, чем больше шагов требуется отложенным палиндромам, тем реже они встречаются.

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

• • •
Палиндром

Палиндро́м (от древнегреческого πάλιν — «назад, снова» и δρóμος — «бег, движение») — число, буквосочетание, слово или фраза (текст), одинаково читающееся в обоих направлениях. Этот термин в 1638 году ввёл в обиход Генри Пичем младший (Henry Peacham), английский литератор и иллюстратор.

Примерами палиндромов являются десятичные числа 101 и 2332, шестнадцатеричное число 1ABA1; слова «дед» и «потоп» в русском языке, «Eve» и «radar» в английском, финское «saippuakivikauppias» (продавец мыла; торговец щёлоком) — самое длинное слово-палиндром в мире; словосочетания «а роза упала на лапу Азора», «Не видно, как он дивен» и «Sum summus mus» (в переводе с латинского «Я — сильнейшая мышь»).

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

• • •
Перевернуть-И-Сложить (операция)

Операция Перевернуть-И-Сложить (англ. Reverse-And-Add, сокращённо RAA) заключается в том, чтобы сложить исходное число с его «перевёрнутой» копией, то есть числом, цифры которого записаны в обратном порядке. Например, к числу 12 нужно прибавить 21 (12+21=33). А к числу 310 прибавить 013 (310+013=323).

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

Интересно, что длина числа увеличивается в среднем на 1 знак каждые 2.416 операции Перевернуть-И-Сложить, выполненные подряд, и не зависит от значения исходного числа. А количество операций, которое можно выполнить над числом, чтобы при этом его длина оставалась неизменной, не может превышать 4 ни для каких чисел.

Таким образом, при многократном применении к числу операции Перевернуть-И-Сложить его длина может увеличиться через 1, 2, 3, 4 или 5 операций, но не более. Другими словами, длина числа остаётся постоянной не дольше 5 раз подряд. Вот несколько примеров таких чисел:

• • •
Шаг

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

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

Иногда встречается формулировка «число становится палиндромом на 28 шаге» или «число превращается в палиндром через 28 шагов». В обоих случаях речь идёт о выполнении 28 операций Перевернуть-И-Сложить над некоторым отложенным палиндромом.

Также часто встречается такое употребление термина: «отложенный палиндром для шага N» или «отложенные палиндромы для шагов M и K». В этих случаях речь идет об отложенных палиндромах, разрешающихся за N, M и K итераций соответственно.