Откладываем палиндромы на новый год

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

Проблема 196 и отложенные десятичные палиндромы

Палиндром — это объект, который может быть представлен в виде упорядоченного набора символов (слово, строка, число) и обладает свойством симметрии относительно своего центрального элемента (или пары таких совпадающих центральных элементов, если палиндром состоит из четного числа символов). Проще говоря, мы называем палиндромом то, что одинаково читается слева направо и справа налево. Например, слово «довод» является палиндромом из русских букв, а число 1991 — палиндромом из цифр.
В конце XX века математик и программист Ван Лэндингхэм придумал простой алгоритм, который с высокой вероятностью может превратить случайное натуральное число в палиндром. Рассмотрим пример:

• Возьмем число 192. Запишем его цифры справа налево, образовав новое число: 291. Оно не совпадает с исходным, значит 192 не является палиндромом
• Сложим исходное число 192 с его «обратной записью» — числом 291. Получим:

  $$

• Проверим число 483. Запишем его справа налево и получим:

  $$

• Пока палиндром не будет найден, повторяем операцию сложения числа со своей обратной записью:

  $$

  $$

  $$

  $$

  $$

  $$

• Запишем все найденные нами числа (а также исходное) в порядке, обратном их появлению:

  $$

• Так как 6996 — число-палиндром, которое получено сложением числа 1635 со своей обратной записью, назовем число 1635 палиндромом, отложенным на 1 шаг или «отложенным палиндромом глубины 1». Тогда 867 будет отложенным палиндромом глубины 2, 483 — глубины 3, а искомое 192 — глубины 4.

Алгоритму потребовалось всего 4 шага чтобы сделать из 192 числовой палиндром. Большинству чисел, включая достаточно большие значения вроде 3783783443, хватает меньше чем 30-и шагов. Суть проблемы числа 196 состоит в том, что оно не приводится к палиндрому при помощи данного алгоритма даже после миллиона шагов. И в десятичной системе исчисления мы пока не можем ни доказать, ни опровергнуть что 196 является палиндромом, отложенным на некоторое количество шагов. Подробнее проблема числа 196 и отложенных палиндромов объясняется в следующем видео:

С другой стороны, сами по себе числа, являющиеся отложенными палиндромами большой глубины, являются редкостью. И поскольку математический анализ не дает подходящего метода для теоретического вывода чисел с таким свойством, задача практического поиска рекордно больших «отложений» числовых палиндромов равно как и проверка чисел подобных 196 являются поводом для соревнований среди программистов и математиков-любителей. Так, с апреля 2019-ого года по 4 января 2021-ого был действителен следующий рекорд:

Число 12000700000025339936491 является отложенным палиндромом глубины 288

Это число содержит 23 знака, а соответствующий ему точный палиндром — 142 знака, поэтому его сложно найти полным перебором всех начальных для алгоритма Лэндингхэма значений. Но изучение некоторых важных свойств отложенных палиндромов помогает оптимизировать поиск, вычеркнув целые классы как повторяющихся, так и гарантированно «слабых» относительно текущего рекорда значений.

О псевдорекордах и критериях принятия решений

Рассмотрим первые несколько ступеней вывода палиндрома из 288-ишагового рекорда:

  12000700000025339936491 +
  19463993352000000700021 =
  31464693352025340636512 +
  21563604352025339646413 =
  53028297704050680282925 +
  52928208605040779282035 =
 105956506309091459564960 +
 069465954190903605659501 =
 175422460499995065224461 +
 164422560599994064224571 =
 339845021099989129449032

Важно обратить внимание на то, что цифры 5 в начале и конце суммы 53028297704050680282925, полученной после двух шагов операции «перевернуть и сложить», являются суммами крайних элементов 3 и 2 числа 31464693352025340636512 в «прямой» записи и соответствующих им крайних элементов 2 и 3 в обратной записи того же числа:

  2...3 + 
  3...2 = 
  5...5

Так случается потому что при сложении «в столбик» числа и его обратной записи, друг под другом оказываются первая и последняя цифра одного и того же числа, вторая и предпоследняя и так далее. При этом сложение можно выполнять не только школьным методом справа налево, но и более сложным — слева направо — также без искажения результата. При сложении справа налево мы добавляем лишнюю единицу к следующему разряду, если в предыдущем сумма была 10 или больше. При сложении же слева направо мы наоборот вычитаем десятку из предыдущего разряда каждый раз, когда в текущем разряде значение суммы на единицу меньше того, которое мы ожидаем исходя из свойств возвратности/симметричности результата. В общем же случае, сложение слева направо выполняется с постоянной коррекцией уже вычисленных разрядов на единицу переноса. Изучив этот процесс, можно строго доказать, что в любой последовательности чисел такой, что каждое следующее является результатом операции «перевернуть и сложить» над предыдущим, все числа кроме первого гарантированно являются 0-возвратными или 1-возвратными.
Возвратность — это некое условное обозначение для чисел, которые близки к палиндромам, но не являются ими. Так, 0-возвратное число имеет вид:

где

То есть при прочтении справа налево каждая цифра может либо совпадать с цифрой исходного (записанного слева направо) числа в том же разряде, либо отличаться от нее не более чем на единицу (следуют из правил сложения и того факта, что сумма двух цифр никогда не превышает 18-и без учета единицы переноса и 19-и с учетом переноса). Рассмотрим вывод числа 12000700000025339936491 и заметим, что большинство промежуточных значений 0-возвратны. Так в числе 21563604352025339646413 крайние разряды 2 и 3 отличаются на единицу, второй и предпоследний совпадают и равны 1, третий сначала и с конца равны соответственно 5 и 4 и отличаются на единицу и так далее.
Некоторые промежуточные значения вывода палиндрома не являются 0-возвратными, но из них можно сделать 0-возвратное удалением первой цифры. Так происходит когда складываются прямая и обратная запись числа, крайние цифры которого либо в сумме превышают 9, либо равны 9 и при сложении получают дополнительную единицу из-за переноса второго слева разряда. Таким является, например, число: 105956506309091459564960. Действительно: $$, $$, $$, $$ и т.д.
Свойство возвратности позволяет описывать огромные семейства чисел, которые после одной или нескольких операций «перевернуть и сложить» приходят к одному и тому же числу. Так, рассмотрим рекорд, установленный московским школьником в 2017-ом году:

Число 1999291987030606810 является отложенным палиндромом глубины 261

Зная, что симметричное изменение разрядов (увеличение первого и уменьшение второго на одно и то же число, увеличение/уменьшение второго одновременно с уменьшением/увеличением предпоследнего и так далее) может сохранять результат операции «перевернуть и сложить» над исходным числом, выполним следующие шаги:

• Запишем число 1999291987030606810 справа налево. Получим: 0186060307891929991
• Сложим два числа, выводя таким образом отложенный на 260 шагов палиндром. Получим:

  0186060307891929991 +
  1999291987030606810 =
  2185352294922536801

• Так как результат сложения имеет вид 2…1 и содержит 23 знака — столько же, сколько и число Щебетова, можно однозначно утверждать, что сумма первых и последних цифр любого отложенного на 261 шаг палиндрома, проходящего через число 2185352294922536801, будет равняться единице. Тогда можем в числе 0186060307891929991 избавиться от значащего нуля вначале и получить число: 1186060307891929990
• А теперь рассмотрим рекорд 2005-ого года, упомянутый в видео от Numberphile:
  
  Как видим, официальный рекорд 2005-ого полностью совпадает с одношаговым выводом из числа Щебетова. Так, переставив местами две цифры в обратной записи числа 12-илетней давности, можно создать новый псевдорекорд.

Свойство возвратности для промежуточных значений вывода точного палиндрома (то есть для результатов операции «перевернуть и сложить») сводит идею «рекордности» больших чисел, отложенных на одинаковое количество шагов, к нулю. Более того, имея 23-хзначное число, являющееся отложенным палиндромом глубины 288, можно легко построить даже миллион-значное число, отложенное также на 288 шагов. Вернемся к примеру с числом 192.
Чтобы после четырех итераций алгоритма Лэндингхэма оно стало точным палиндромом, необходимо чтобы на первой итерации двойка была подписана под единицей, девятка под девяткой, а единица под двойкой при сложении в столбик. Но того же эффекта можно достигнуть при помощи числа 192000192, а именно:

  192000192 + 
  291000291 = 
  483000483 + 
  384000384 = 
  867000867 +
  768000768 = 
 1635001635 +
 5361005361 = 
 6996006996
  

Если бы мы взяли число 1920000192, то оно также оказалось бы отложенным на 4 шага палиндромом, но уже с результатом 69960006996. Этот способ работает с любым
отложенным палиндромом при достаточно большом количестве нулей — разделителей. Если нулей будет недостаточно, то на определенном этапе результат сложения в правой половине числа начнет влиять на сумму слева и вывод изменится. Например, число 192192 на третьей итерации алгоритма даст число 1636635, где результат 1635 справа превратился в 635, а 1635 слева превратились в 1636 из-за «наезда» поразрядных сумм друг на друга.
Используя это свойство, можно легко побить как «рекорд» Щебетова, предложив число 1999291987030606810000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001999291987030606810, отложенное на 261 шаг, так и действующий рекорд Нобелена, заменив его числом 120007000000253399364910000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000012000700000025339936491, отложенным на 288 шагов.
При этом сама задача вывода отложенного палиндрома глубины большей чем n при наличии сколь угодно большой базы отложенных палиндромов глубины n, является вычислительно тяжелой, поэтому предлагаю:

• Считать значимыми только работы (как теоретический вывод, так и результаты выполнения программ), которые либо предоставляют достоверную информацию о распределении отложенных палиндромов среди всех чисел, либо приводят к появлению отложенного палиндрома большей глубины, чем любой из ранее известных.
• В первом случае принимаются публикации вида: «я проверил все 28-изначние числа и среди них точно (из доказательства корректности моего алгоритма и по результатам выполнения моей программы) нет отложенных палиндромов глубже n = (некоторое значение)».
• Во втором случае достаточно предъявить число, являющееся отложенным палиндромом достаточно большой глубины и предоставить информации о том, каким методом это число было получено. Например: «я наугад запустил алгоритм полного перебора (реализация прилагается) начиная с числа 28924893289389574 и, оставив компьютер включенным на 2 года, получил отложенный палиндром глубины (некоторое значение), а именно: (само число — отложенный палиндром)»
• Поскольку из отложенного палиндрома x глубины n можно непосредственно вывести отложенный палиндром глубины n+1 только тогда, когда число x являлось 0-возвратным или 1-возвратным, рекомендую сразу публиковать новые рекорды второго типа в возвратной форме.

Критерий принятия рекорда только по глубине отложения (независимо от значения самого числа на входе алгоритма Лэндингхэма) официально поддержан Джейсоном Дусеттом — автором рекорда 2005-ого года, ныне занимающегося проверкой и публикацией новых палиндромов-рекордсменов (ссылка на официальный сайт дана в конце статьи). Идея же представления новых рекордов только в 0-возратной или 1-возвратной записи пока оспаривается из-за наличия работающий программ, ищущих невозвратные рекорды. Но любой из таких рекордов может быть преобразован в возвратный вручную, как это было сделано московским школьником. Поэтому моё число приводится в возвратной форме. Рассмотрим подробнее процесс поиска рекорда.

Метод неопределенного перебора

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

Рассмотрим пример. Число 1137301 является отложенным палиндромом глубины 15 — полный вывод здесь. Попробуем получить из него отложенный палиндром глубины 16:

Для 7-изначного числа 1137301 результат операции одношагового вывода может содержать как 0-возвратные 7-изначные числа (левая половина дерева вывода), так 1-возвратные 6-изначные решения (правая половина изображения). Рассмотрим левую половину:

• Утверждая что число 1137301 можно получить сложением двух семизначных чисел L и LRev, одно из которых получается обратной записью другого, мы получим ряд сопутствующих этому утверждению обязательных ограничений на каждый из разрядов. Представив число L как цепочку цифр X1..X7, имеем: сложение X1 + X7 дает в разряде единиц числа 1137301 цифру 1, а значит сумма X1 + X7 строго равна либо единице, либо 11 (тогда старшая единица повлияет на сумму X2 и X6). Сложение же X1 + X7 в разряде миллионов дает цифру 1 и число 1137301 меньше десяти миллионов, поэтому сумма X1 + X7 строго равна либо 1, либо 0 (если единица добавится при сложении X2 и X6). При этом суммы X1 + X7 слева и X1 + X7 справа должны совпадать. На пересечении левых и правых условий получим однозначно: X1 + X7 = 1
• Сумма X1 + X7 = 1 при наличии точного значения 1 в разрядах единиц и миллионов числа 1137301 не занимает единицу у разряда ста тысяч и не переносит единицу на разряд десятков. Поэтому цифру 0 в разряде десятков числа 11373011 можно интерпретировать как X2 + X6 строго равно либо 0 либо 10, а цифру 1 в разряде ста тысяч как X2 + X6 строго равно либо 0 либо 1. На пересечении этих условий получим: X2 + X6 строго равно 0 и в разряде десятков тысяч числа 1137301 цифра 3 должна рассматриваться с учетом дополнительного десятка (X3 + X5 = 12 или 13 слева). Отсюда, с учетом тройки в разряде сотен для числа 113701 и отсутствия единицы переноса (X2+X6 <10) получим однозначно: X3+X5 = 13
• Так как X3+X5 > 10, цифра 7 в разряде тысяч числа 1137301 должна рассматриваться как X4+X4+1(единица переноса) либо как X4+X4+1-10. Второй вариант исключен, так как сумма X3+X5 производит тройку в разряде десятков тысяч самостоятельно — без единицы переноса. Таким образом, X4+X4+1=1, откуда X4 = 3
• Для суммы X1+X7=1 понимая что первая цифра в числе L не может быть нулем имеем: X1=1, X7=0. Для суммы цифр X2+X6 = 0 однозначно получим X2=0 и X6=0. Сумму X3+X5=13 можно интерпретировать многими способами, но если мы утверждаем что L является 0-возвратным числом, то по определению X3=X5+1 или X3=X5-1 (так как их сумма нечетна). Таким образом, либо X3=6 и X5=7, либо X3=7 и X5=6. Значение X4 как центрального элемента однозначно определено: X4=3. Таким образом: числа 1063700 и 1073600 являются отложенными палиндромами глубины 16 и образуют множество $$, которое является результатом операции одношагового обратного вывода, ограниченной на 0-возвратные элементы.

Аналогичное рассмотрение 1-возратного решения с неопределенными цифрами X1…X6 привело к противоречию, поэтому результатом одношагового обратного отложения числа 1137301, ограниченного 1-возвратными элементами является пустое множество. Итак, числа 1063700 и 1073600 являются 0-возвратными отложенными палиндромами глубины 16, проходящими через число 1137301. А 1-возвратных отложенных палиндромов глубины 16, проходящих через число 1137301, достоверно не существует. Проверить оба значения можно здесь и здесь.

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

1. Пусть нам известны возможные значения некоторых цифр искомого числа с учетом возвратности, например: пара первая-последняя цифра может быть либо 1-1, либо 1-0, пара вторая-предпоследняя цифра — либо 3-2, либо 2-3, либо 4-3, либо 3-4. Тогда к каждому из таких вариантом мы добавляем все возможные с учетом возвратности пары цифр для следующей пары неопределенных разрядов. В нашем примере, мы утверждаем, что пара третья слева-третья справа цифра может быть одним из значений: 0-0, 0-1, 1-0, 9-0, 0-9, 1-1, 2-1, 1-2, 2-2,…..,9-8, 8-9, 9-9. Заметим, что таких вариантом меньше сотни, поэтому ограничение 0- и 1-возвратность оказывается выгодно по времени вычисления результирующего множества
2. Для каждого возможного сочетания пар известных десятичных разрядов достраиваем потенциальный кандидат на элемент множества обратного восстановления глубины 1 нулями во всех неизвестных разрядах. Так, в нашем примере будут получены числа 1300…0021, 1310…0021, …., 1200…0031, 1210…0031,.., 1300…0020, 1310…0020,…, 1390…0940
3. Каждое из полученных на прошлом этапе чисел сложим со своей обратной записью и сравним с начальным значением — числом, над которым применяется операция обратного восстановления. Если результат сложения меньше исходного числа, но отличается от него не более чем на $$(где t — индекс максимального смещения, равный порядковому номеру текущего неопределенного разряда при 0-возвратном поиске и на единицу превышает порядковый номер текущего неопределенного разряда при 1-возвратном поиске), то последняя из пар, использованных при построении суммируемого числа (например для 1280…0730 это будет пара 8-7), объявляется особой.
4. По окончании итерации считать что пара цифр, стоящих на очередном (в нашем случае: третьем слева и третьем справа) может принимать только те значения, которые были помечены как особые (например только 7-8 и 8-7). Теперь данные подготовлены для выполнения первого шага следующей итерации и все возможные пары определены для первых n+1 разрядов слева и столько же справа, где n — количество разрядов, пары для которых были определены перед началом текущей итерации.

Этот метод является авторским и для его возникновения потребовалось длительное наблюдение за свойствами отложенных палиндромов разной глубины. Для реализации нашего алгоритма на C# понадобится класс BigInteger и ряд вспомогательных процедур:

• Invert — получает длинное целое и возвращает его обратную запись
• GetStep — получает длинное целое и количество итераций step (по умолчанию — одна) и возвращает результат вычисления step-ой итерации алгоритма Лэндингхэма
• RightCheck и oRightCheck — реккурсивная и нереккурсивная соответственно реализации процедуры, возвращаюшей результат проверки значения step-ой (начиная с длинного целого числа val) итерации алгоритма Лэндингхэма на палиндром. Возвращает true только при выводе точного палиндрома за заданное количество шагов
• oCheckPalin — получает длинное целое и возвращает количество итераций алгоритма Лэндингхэма, необходимое для превращения этого целого в точный палиндром. Если не удалось получить точный палиндром за предельное lim количество итераций, то вернет отлицательное число
• dup — принимает начальную строку и количество times повторений и возвращает строку, состоящую их times конкатенированных двух за другом входных строк. Например, dup(«228», 3) вернет «228228228»

Получим:

        static BigInteger Invert(BigInteger a)
        {
            return BigInteger.Parse(new string(a.ToString().Reverse().ToArray()));
        }

        static BigInteger GetStep(BigInteger val, int step = 1)
        {
            int iter = 0;
            BigInteger res = val;
            while (iter < step)
            {
                res += Invert(res);
                iter++;
            }
            return res;
        }

        static bool RightChech(BigInteger val, int step = 0)
        {
            if (step == 0)
            {
                char[] data = val.ToString().ToCharArray();
                for (int len = 0; len < data.Length; len++)
                    if (data[len] != data[data.Length - len - 1])
                        return false;
                return true;
            }
            else
                return RightChech(val + BigInteger.Parse(new string(val.ToString().Reverse().ToArray())), step - 1);
        }

        static bool oRightCheck(BigInteger val, int step = 0)
        {
            BigInteger testval = val;
            int iter = 0;
            while (iter < step)
            {
                testval += BigInteger.Parse(new string(testval.ToString().Reverse().ToArray()));
                iter++;
            }
            return RightChech(testval);
        }

        static int oCheckPalin(BigInteger val, int lim = 600)
        {
            if (lim < 0)
                return int.MinValue;
            if (RightChech(val))
                return 0;
            {
                int iter = 0;
                while (iter <= lim)
                {
                    if (RightChech(val))
                        return iter;
                    val += BigInteger.Parse(new string(val.ToString().Reverse().ToArray()));
                    iter++;
                }
                return int.MinValue;
            }
        }

        static string dup(string val, int times = 1)
        {
            string res = "";
            for (int i = 1; i <= times; i++)
                res += val;
            return res;
        }

Частичная реализация метода неопределенного перебора на примере процедуры R21:

 static void Re21(BigInteger val)
{
int dlim = 0;
{
char[] conv = val.ToString().ToCharArray();
if (conv[0].ToString() == "1")
if (conv[conv.Length - 1].ToString() != "0")
dlim = 1;                    
}
char[][] lp = new char[2][];
char[][] rp = new char[2][];
lp[0] = new char[30];
rp[0] = new char[30];
lp[1] = new char[30];
rp[1] = new char[30];
int[] plen = new int[] { 0, 0 };
for (int xsel = 0; xsel < plen.Length; xsel++)
{
for (int i = 0; i <= 18; i++)
if (i % 2 == 0)
{
lp[xsel][plen[xsel]] = (i / 2).ToString().ToCharArray()[0];
rp[xsel][plen[xsel]] = lp[xsel][plen[xsel]];
plen[xsel]++;
}
else
{
int min = (i / 2);
if (xsel == 1)
{
lp[xsel][plen[xsel]] = (min).ToString().ToCharArray()[0]; //com
rp[xsel][plen[xsel]] = (min + 1).ToString().ToCharArray()[0]; //com
plen[xsel]++; //com
}
lp[xsel][plen[xsel]] = (min + 1).ToString().ToCharArray()[0];
rp[xsel][plen[xsel]] = (min).ToString().ToCharArray()[0];
plen[xsel]++;
}
lp[xsel][plen[xsel]] = '9';
rp[xsel][plen[xsel]] = '0';
plen[xsel]++;
if (xsel == 1)
{
lp[xsel][plen[xsel]] = '0'; //com
rp[xsel][plen[xsel]] = '9'; //com
plen[xsel]++; //com
}
}
int sel = val.ToString().Length;
for (int d1 = 0; d1 <= dlim; d1++)
if ((sel - d1 == 21) || (sel - d1 == 22))
for (int lr1 = 0; lr1 < plen[d1]; lr1++)
{
string pr1 = lp[d1][lr1].ToString();
if (d1 == 1)
pr1 = "1" + pr1;
string sf1 = rp[d1][lr1].ToString();
string my1 = pr1 + dup("0", 21 - 2) + sf1;
BigInteger val1 = BigInteger.Parse(my1);
val1 = GetStep(val1);
if (val1 <= val)
if ((val - val1) <= 2 * BigInteger.Pow(10, 20 + d1 * 1))
{
for (int lr2 = 0; lr2 < plen[d1]; lr2++)
{
string pr2 = pr1 + lp[d1][lr2].ToString();
string sf2 = rp[d1][lr2].ToString() + sf1;
string my2 = pr2 + dup("0", 21 - 4) + sf2;
BigInteger val2 = BigInteger.Parse(my2);
val2 = GetStep(val2);
if (val2 <= val)
if ((val - val2) <= 2 * BigInteger.Pow(10, 19 + d1 * 1))
{
for (int lr3 = 0; lr3 < plen[d1]; lr3++)
{
string pr3 = pr2 + lp[d1][lr3].ToString();
string sf3 = rp[d1][lr3].ToString() + sf2;
string my3 = pr3 + dup("0", 21 - 6) + sf3;
BigInteger val3 = BigInteger.Parse(my3);
val3 = GetStep(val3);
if (val3 <= val)
if ((val - val3) <= 2 * BigInteger.Pow(10, 18 + d1 * 1))
{
for (int lr4 = 0; lr4 < plen[d1]; lr4++)
{
string pr4 = pr3 + lp[d1][lr4].ToString();
string sf4 = rp[d1][lr4].ToString() + sf3;
string my4 = pr4 + dup("0", 21 - 8) + sf4;
BigInteger val4 = BigInteger.Parse(my4);
val4 = GetStep(val4);
if (val4 <= val)
if ((val - val4) <= 2 * BigInteger.Pow(10, 17 + d1 * 1))
{
for (int lr5 = 0; lr5 < plen[d1]; lr5++)
{
string pr5 = pr4 + lp[d1][lr5].ToString();
string sf5 = rp[d1][lr5].ToString() + sf4;
string my5 = pr5 + dup("0", 21 - 10) + sf5;
BigInteger val5 = BigInteger.Parse(my5);
val5 = GetStep(val5);
if (val5 <= val)
if ((val - val5) <= 2 * BigInteger.Pow(10, 16 + d1 * 1))
{
for (int lr6 = 0; lr6 < plen[d1]; lr6++)
{
string pr6 = pr5 + lp[d1][lr6].ToString();
string sf6 = rp[d1][lr6].ToString() + sf5;
string my6 = pr6 + dup("0", 21 - 12) + sf6;
BigInteger val6 = BigInteger.Parse(my6);
val6 = GetStep(val6);
if (val6 <= val)
if ((val - val6) <= 2 * BigInteger.Pow(10, 15 + d1 * 1))
{
for (int lr7 = 0; lr7 < plen[d1]; lr7++)
{
string pr7 = pr6 + lp[d1][lr7].ToString();
string sf7 = rp[d1][lr7].ToString() + sf6;
string my7 = pr7 + dup("0", 21 - 14) + sf7;
BigInteger val7 = BigInteger.Parse(my7);
val7 = GetStep(val7);
if (val7 <= val)
if ((val - val7) <= 2 * BigInteger.Pow(10, 14 + d1 * 1))
{
for (int lr8 = 0; lr8 < plen[d1]; lr8++)
{
string pr8 = pr7 + lp[d1][lr8].ToString();
string sf8 = rp[d1][lr8].ToString() + sf7;
string my8 = pr8 + dup("0", 21 - 16) + sf8;
BigInteger val8 = BigInteger.Parse(my8);
val8 = GetStep(val8);
if (val8 <= val)
if ((val - val8) <= 2 * BigInteger.Pow(10, 13 + d1 * 1))
{
for (int lr9 = 0; lr9 < plen[d1]; lr9++)
{
string pr9 = pr8 + lp[d1][lr9].ToString();
string sf9 = rp[d1][lr9].ToString() + sf8;
string my9 = pr9 + dup("0", 21 - 18) + sf9;
BigInteger val9 = BigInteger.Parse(my9);
val9 = GetStep(val9);
if (val9 <= val)
if ((val - val9) <= 2 * BigInteger.Pow(10, 12 + d1 * 1))
{
for (int lr10 = 0; lr10 < plen[d1]; lr10++)
{
string pr10 = pr9 + lp[d1][lr10].ToString();
string sf10 = rp[d1][lr10].ToString() + sf9;
string my10 = pr10 + dup("0", 21 - 20) + sf10;
BigInteger val10 = BigInteger.Parse(my10);
val10 = GetStep(val10);
if (val10 <= val)
if ((val - val10) <= 2 * BigInteger.Pow(10, 11 + d1 * 1))
{
if (val10 == val)
{
BigInteger rval = BigInteger.Parse(my10);
int rstep = oCheckPalin(rval);
if ((rstep > _rep_maxstep) || ((rstep == _rep_maxstep) && (_rep_maxval < rval)))
{
_rep_maxstep = rstep;
_rep_maxval = rval;
}
Console.WriteLine(my10 + " [{0}]   ({1}|{2})",
rstep, _rep_maxstep, _rep_maxval.ToString());
{
int[] emul = new int[10];
if ((lp[d1][lr1] + rp[d1][lr1]) % 2 == 0)
emul[0] = 1;
else
emul[0] = 2;
if ((lp[d1][lr2] + rp[d1][lr2]) % 2 == 0)
emul[1] = 1;
else
emul[1] = 2;
if ((lp[d1][lr3] + rp[d1][lr3]) % 2 == 0)
emul[2] = 1;
else
emul[2] = 2;
if ((lp[d1][lr4] + rp[d1][lr4]) % 2 == 0)
emul[3] = 1;
else
emul[3] = 2;
if ((lp[d1][lr5] + rp[d1][lr5]) % 2 == 0)
emul[4] = 1;
else
emul[4] = 2;
if ((lp[d1][lr6] + rp[d1][lr6]) % 2 == 0)
emul[5] = 1;
else
emul[5] = 2;
if ((lp[d1][lr7] + rp[d1][lr7]) % 2 == 0)
emul[6] = 1;
else
emul[6] = 2;
if ((lp[d1][lr8] + rp[d1][lr8]) % 2 == 0)
emul[7] = 1;
else
emul[7] = 2;
if ((lp[d1][lr9] + rp[d1][lr9]) % 2 == 0)
emul[8] = 1;
else
emul[8] = 2;
if ((lp[d1][lr10] + rp[d1][lr10]) % 2 == 0)
emul[9] = 1;
else
emul[9] = 2;
if (d1 == 1) // == 1
for (int i = 0; i < emul.Length; i++)
emul[i] = 1;
for (int m1 = 0; m1 < emul[0]; m1++)
for (int m2 = 0; m2 < emul[1]; m2++)
for (int m3 = 0; m3 < emul[2]; m3++)
for (int m4 = 0; m4 < emul[3]; m4++)
for (int m5 = 0; m5 < emul[4]; m5++)
for (int m6 = 0; m6 < emul[5]; m6++)
for (int m7 = 0; m7 < emul[6]; m7++)
for (int m8 = 0; m8 < emul[7]; m8++)
for (int m9 = 0; m9 < emul[8]; m9++)
for (int m10 = 0; m10 < emul[9]; m10++)
{
string pref = "";
if (d1 == 1)
pref = "1";
string suf = "";
{
if (m1 == 0)
{
pref += lp[d1][lr1];
suf = rp[d1][lr1] + suf;
}
else
{
pref += rp[d1][lr1];
suf = lp[d1][lr1] + suf;
}
}
{
if (m2 == 0)
{
pref += lp[d1][lr2];
suf = rp[d1][lr2] + suf;
}
else
{
pref += rp[d1][lr2];
suf = lp[d1][lr2] + suf;
}
}
{
if (m3 == 0)
{
pref += lp[d1][lr3];
suf = rp[d1][lr3] + suf;
}
else
{
pref += rp[d1][lr3];
suf = lp[d1][lr3] + suf;
}
}
{
if (m4 == 0)
{
pref += lp[d1][lr4];
suf = rp[d1][lr4] + suf;
}
else
{
pref += rp[d1][lr4];
suf = lp[d1][lr4] + suf;
}
}
{
if (m5 == 0)
{
pref += lp[d1][lr5];
suf = rp[d1][lr5] + suf;
}
else
{
pref += rp[d1][lr5];
suf = lp[d1][lr5] + suf;
}
}
{
if (m6 == 0)
{
pref += lp[d1][lr6];
suf = rp[d1][lr6] + suf;
}
else
{
pref += rp[d1][lr6];
suf = lp[d1][lr6] + suf;
}
}
{
if (m7 == 0)
{
pref += lp[d1][lr7];
suf = rp[d1][lr7] + suf;
}
else
{
pref += rp[d1][lr7];
suf = lp[d1][lr7] + suf;
}
}
{
if (m8 == 0)
{
pref += lp[d1][lr8];
suf = rp[d1][lr8] + suf;
}
else
{
pref += rp[d1][lr8];
suf = lp[d1][lr8] + suf;
}
}
{
if (m9 == 0)
{
pref += lp[d1][lr9];
suf = rp[d1][lr9] + suf;
}
else
{
pref += rp[d1][lr9];
suf = lp[d1][lr9] + suf;
}
}
{
if (m10 == 0)
{
pref += lp[d1][lr10];
suf = rp[d1][lr10] + suf;
}
else
{
pref += rp[d1][lr10];
suf = lp[d1][lr10] + suf;
}
}
Re21(BigInteger.Parse(pref + "0" + suf));
}
}
}
for (int c = 1; c <= 9; c++)
{
string myc = pr10 + c.ToString() + sf10;
BigInteger valc = BigInteger.Parse(myc);
valc = GetStep(valc);
if (valc == val)
{
BigInteger rval = BigInteger.Parse(myc);
int rstep = oCheckPalin(rval);
if ((rstep > _rep_maxstep) || ((rstep == _rep_maxstep) && (_rep_maxval < rval)))
{
_rep_maxstep = rstep;
_rep_maxval = rval;
}
Console.WriteLine(myc + " [{0}]   ({1}|{2})",
rstep, _rep_maxstep, _rep_maxval.ToString());
//Re21(rval); wide
{
int[] emul = new int[10];
if ((lp[d1][lr1] + rp[d1][lr1]) % 2 == 0)
emul[0] = 1;
else
emul[0] = 2;
if ((lp[d1][lr2] + rp[d1][lr2]) % 2 == 0)
emul[1] = 1;
else
emul[1] = 2;
if ((lp[d1][lr3] + rp[d1][lr3]) % 2 == 0)
emul[2] = 1;
else
emul[2] = 2;
if ((lp[d1][lr4] + rp[d1][lr4]) % 2 == 0)
emul[3] = 1;
else
emul[3] = 2;
if ((lp[d1][lr5] + rp[d1][lr5]) % 2 == 0)
emul[4] = 1;
else
emul[4] = 2;
if ((lp[d1][lr6] + rp[d1][lr6]) % 2 == 0)
emul[5] = 1;
else
emul[5] = 2;
if ((lp[d1][lr7] + rp[d1][lr7]) % 2 == 0)
emul[6] = 1;
else
emul[6] = 2;
if ((lp[d1][lr8] + rp[d1][lr8]) % 2 == 0)
emul[7] = 1;
else
emul[7] = 2;
if ((lp[d1][lr9] + rp[d1][lr9]) % 2 == 0)
emul[8] = 1;
else
emul[8] = 2;
if ((lp[d1][lr10] + rp[d1][lr10]) % 2 == 0)
emul[9] = 1;
else
emul[9] = 2;
if (d1 == 1) // == 1
for (int i = 0; i < emul.Length; i++)
emul[i] = 1;
for (int m1 = 0; m1 < emul[0]; m1++)
for (int m2 = 0; m2 < emul[1]; m2++)
for (int m3 = 0; m3 < emul[2]; m3++)
for (int m4 = 0; m4 < emul[3]; m4++)
for (int m5 = 0; m5 < emul[4]; m5++)
for (int m6 = 0; m6 < emul[5]; m6++)
for (int m7 = 0; m7 < emul[6]; m7++)
for (int m8 = 0; m8 < emul[7]; m8++)
for (int m9 = 0; m9 < emul[8]; m9++)
for (int m10 = 0; m10 < emul[9]; m10++)
{
string pref = "";
if (d1 == 1)
pref = "1";
string suf = "";
{
if (m1 == 0)
{
pref += lp[d1][lr1];
suf = rp[d1][lr1] + suf;
}
else
{
pref += rp[d1][lr1];
suf = lp[d1][lr1] + suf;
}
}
{
if (m2 == 0)
{
pref += lp[d1][lr2];
suf = rp[d1][lr2] + suf;
}
else
{
pref += rp[d1][lr2];
suf = lp[d1][lr2] + suf;
}
}
{
if (m3 == 0)
{
pref += lp[d1][lr3];
suf = rp[d1][lr3] + suf;
}
else
{
pref += rp[d1][lr3];
suf = lp[d1][lr3] + suf;
}
}
{
if (m4 == 0)
{
pref += lp[d1][lr4];
suf = rp[d1][lr4] + suf;
}
else
{
pref += rp[d1][lr4];
suf = lp[d1][lr4] + suf;
}
}
{
if (m5 == 0)
{
pref += lp[d1][lr5];
suf = rp[d1][lr5] + suf;
}
else
{
pref += rp[d1][lr5];
suf = lp[d1][lr5] + suf;
}
}
{
if (m6 == 0)
{
pref += lp[d1][lr6];
suf = rp[d1][lr6] + suf;
}
else
{
pref += rp[d1][lr6];
suf = lp[d1][lr6] + suf;
}
}
{
if (m7 == 0)
{
pref += lp[d1][lr7];
suf = rp[d1][lr7] + suf;
}
else
{
pref += rp[d1][lr7];
suf = lp[d1][lr7] + suf;
}
}
{
if (m8 == 0)
{
pref += lp[d1][lr8];
suf = rp[d1][lr8] + suf;
}
else
{
pref += rp[d1][lr8];
suf = lp[d1][lr8] + suf;
}
}
{
if (m9 == 0)
{
pref += lp[d1][lr9];
suf = rp[d1][lr9] + suf;
}
else
{
pref += rp[d1][lr9];
suf = lp[d1][lr9] + suf;
}
}
{
if (m10 == 0)
{
pref += lp[d1][lr10];
suf = rp[d1][lr10] + suf;
}
else
{
pref += rp[d1][lr10];
suf = lp[d1][lr10] + suf;
}
}
Re21(BigInteger.Parse(pref + c.ToString() + suf));
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}

После полной реализации набора вспомогательных процедур, я взял в качестве начального значение 105956506309091459564960, так как оно отстоит от текущего рекорда на 3 шага (отложено на 285 шагов против 288 в рекорде), но при этом может является суммой только 23-хзначного числа и его обратной записи. Так мы сочетаем сравнительно небольшие размер кода и продолжительность вычислений с достаточно объемным множеством обратно выводимых значений (отложенных палиндромов глубины 286 и более, проходящих через число 105956506309091459564960). На случай, если рекорд не будет найден на этом этапе, программа продолжает работу, беря другое — более «тяжелое» по времени расчета — начальное значение, что видно на скриншоте.
Результат работы моей программы:

Таким образом:

Числа 13968441660506503386020 и 13568441660506503386420 являются отложенными палиндромами глубины 289

Применив «школьную максимизацию», можно получить следующие числа, также являющиеся отложенными палиндромами глубины 289:

15999771990503200073000 — наибольшее
10037000230509917799950 — наименьшее

Использование в нашей реализации метода неопределенного перебора процедур R21, R22 и R23, восстанавливающих 21-23-хзначные 0-возвратные и 22-24-хзначные 1-возвратные значения, гарантирует, что из числа 105956506309091459564960 невыводим ни один отложенный на 290 и более шагов палиндром. Более того, все 289-ишаговые решения, проходящие через число 105956506309091459564960, оказываются непосредственно выводимы из числа 16937872231012117762051 при помощи 0-возвратной ветки процедуры R23 — вывод 0-возвратного 23-хзначного числа из другого 0-возвратного 23-хзначного.

Послесловие

Теория чисел долгое время не считалась полноценной математической дисциплиной, поэтому сегодня математики легко справляются со сложнейшими задачами дифференциальной алгебры, топологий, но практически беспомощны перед проблемами элементарных свойств десятичных чисел. Математический анализ позволяет эффективно искать числа, критерий проверки для которых задан функционально. Но операция «перевернуть и сложить» в десятичной системе исчисления из-за объективных причин, таких как перенос единицы при превышении десятка в поразрядной сумме, не может быть описана функционально.
Занимаясь поиском отложенных палиндромов, необходимо уделять больше внимания разработке новых методов вывода и проверки решений, а не численным рекордам как таковым. В моей работе были предложены не только наибольшие из известных сегодня решений, но и новый алгоритм для работы с «отложением» как со строгой математической операцией. Так я вношу свой скромный вклад в методологию решения численных задач в целом.

Ссылки

Оригинальное видео о проблеме 196 от Numberphile
Регулярно обновляемая сводка рекордов
Википедия — самая полная версия статьи о числах Лишрел
Мой рекорд на 289 шагов
Помочь автору