О новом проекте P196

19 сентября 2021
Время на чтение: 12 минут

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

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

Конечно, это не означает, что число 196 (в десятичной системе) никогда не станет палиндромом. Строго говоря, мы этого не знаем. То есть в настоящий момент этот вопрос является одной из нерешённых математических проблем.

Однако для некоторых других систем счисления (с основанием 2, 4, 8, 11, 16 и некоторых других) есть строгое математическое доказательство того, что существуют такие числа, которые никогда не смогут стать палиндромами в этих системах счисления. Но для всем нам привычной десятичной системы такого доказательства нет, по крайней мере пока.

• • •

Интересно, что 196 не является единственным подобным числом. В действительности таких чисел бесконечно много. Вот, например, ещё несколько: 879, 1,997, 7,059, 9,999. Более того, по данным, полученным в проекте MDPN, чем длиннее числа, тем среди них больше «таких» чисел.

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

Все такие числа принято называть числами Лишрел. В свою очередь, числа Лишрел делятся на базовые и родственные. Если не вдаваться в подробности, то базовые числа — это «основные» числа Лишрел, они начинают так называемые потоки. А родственные числа Лишрел — это такие числа, которые в эти потоки «вливаются».

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

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

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

• • •

Сегодня официально был дан старт проекту с кодовым названием P196, которое расшифровывается как «196 Palindrome Quest» (в переводе на русский «Поиск палиндрома 196»)!

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

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

В первую очередь планируется проверить все базовые числа Лишрел до 6-значных включительно. Всего таких чисел 173. Вот первые 20 из них: 196, 879, 1,997, 7,059, 9,999, 10,553, 10,563, 10,577, 10,583, 10,585, 10,638, 10,663, 10,668, 10,697, 10,715, 10,728, 10,735, 10,746, 10,748, 10,783. Речь идёт о сотнях и десятках миллионов операций.

Все полученные в рамках проекта результаты будут доступны публично на странице проекта. То есть любой желающий сможет скачать|1| любой файл с результатом. Например, файл с результатом 150 миллионов операций для числа 196, или файл с результатом 30 миллионов операций для числа 10,735.

Все результаты будут верифицироваться, чтобы полностью исключить вероятность ошибки в расчётах из-за сбоев в работе оборудования. Это означает, что операции над числами будут выполняться независимо как минимум на 2 разных компьютерах. Затем результаты будут сравниваться, и в случае их расхождения, вычисления будут выполняться снова, но уже на третьем компьютере. И так далее.

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

• • •

Этот проект предполагает огромное количество вычислений. Но самое первое время его программа будет работать в один поток. И немного позднее — в два. А число 196 будет проверяться большую часть времени.

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

В любом случае, впереди длинный путь как минимум до 2.5 миллиарда операций для числа 196. А также огромный объём вычислений для других чисел. Удачи этому проекту и побольше гигагерц!

• • •

Заранее предвидя возможные вопросы вроде «Ведь кто-то уже проверил, что даже после миллиарда операций число 196 так и не стало палиндромом?» или «Зачем делать ту же работу с самого начала?», отвечу. Есть 3 основных момента, объясняющих целесообразность существования моего проекта P196.

Но прежде я скажу следующее. Миллиард (как и любое другое количество) выполненных операций над числом 196 не исключает того, что этому числу для того, чтобы стать палиндромом, просто нужно ещё больше операций. Хоть это и очень маловероятно. А теперь мои 3 довода.

1. Да, число 196, как и некоторые другие числа, уже много раз пытались проверять. И проделали огромное количество работы. Но результаты этих попыток очень трудно найти в сети. Если результатов много (например, по 1 файлу на каждый миллион операций для каждого базового числа), то это как минимум десятки гигабайт. Хранить такой объём данных на сервере, особенно с публичным доступом, непросто. Размер отдельных таких файлов составляет десятки мегабайт. По этой причине большая часть найденных мной ссылок уже не работает, а файлы невозможно скачать.

Я хочу собрать и сделать доступными все результаты в одном месте|1|. То есть много отдельных файлов для каждого базового числа Лишрел. Между отдельными файлами будет 1 миллион операций в начале вычислений и не более 10-50 миллионов операций в середине и после первого миллиарда.

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

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

Исходный код моей программы, и особенно блок, выполняющий операции RAA над числами, снабжён многочисленными тестами, которые запускаются для каждого билда, что гарантирует корректность вычислений. А сам исходный код будет находиться в публичном репозитории на GitHub|2|. Файлы результатов содержат контрольные суммы, что исключает возможность незаметного их повреждения. В парке оборудования на данный момент имеется 3 отдельных компьютера, работающих в режиме 24/7 на задачах проекта iLWN, что позволяет мне самостоятельно выполнить минимально необходимую верификацию результатов.

3. В сети мне удалось найти сведения о том, что были тщательно проверены числа 196 и 879 (сотни миллионов операций). Также есть упоминания о том, что были проверены десятки других базовых чисел Лишрел. Но о том, какие именно это были числа, и насколько тщательно они проверялись, ничего не известно.

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

• • •

Примечания:

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

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