О количестве проверяемых чисел при
поиске отложенных палиндромов

26 октября 2021
Время на чтение: 9 минут

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

Он предполагает, что мы будем проверять каждое натуральное число, начиная от 1 и далее. Так, в каждом диапазоне мы должны будем проверить 9×10N-1 чисел, где N — номер диапазона (он же длина его чисел или количество знаков в них). А именно: 9 чисел в однозначном, затем ещё 90 — в 2-значном, потом 900 — в 3-значном и так далее.

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

Вот очень простой расчёт. Предположим, что мы проверяем любые числа со средней скоростью 1 миллион в секунду. К слову, это очень хорошая скорость. При такой скорости проверка всех 9-значных чисел (9×108), заняла бы всего 15 минут. Для проверки всех 12-значных нам понадобится уже в 1000 раз больше времени: 10 суток и ещё 10 часов.

Проверка всех 18-значных чисел, даже если её делать на 500 компьютерах параллельно, потребовала бы при скорости 1 миллион чисел на каждом из них примерно 57 лет вычислений! Но, к счастью, всё не так плохо! И на самом деле мы можем проверять в тысячи и миллионы раз меньше чисел!

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

Диапазон Количество чисел Отношение
1-значные 9 1.0
2-значные 18 5.0
3-значные 180 5.0
4-значные 342 26.3
5-значные 3,420 26.3
6-значные 6,498 138.5
7-значные 64,980 138.5
8-значные 123,462 729.0
9-значные 1,234,620 729.0
10-значные 2,345,778 3.8·103
11-значные 23,457,780 3.8·103
12-значные 44,569,782 2.0·104
13-значные 445,697,820 2.0·104
14-значные 846,825,858 1.1·105
15-значные 8,468,258,580 1.1·105
16-значные 16,089,691,302 5.6·105
17-значные 160,896,913,020 5.6·105
18-значные 305,704,134,738 2.9·106
19-значные 3,057,041,347,380 2.9·106
20-значные 5,808,378,560,022 1.5·107
21-значные 58,083,785,600,220 1.5·107
22-значные 110,359,192,640,418 8.2·107
23-значные 1,103,591,926,404,180 8.2·107

Таким образом, среди 18-значных чисел нам понадобится проверить лишь одно число из каждых 2.9 миллиона чисел, а для 23-значных — одно из 82 миллионов! И те самые 57 лет вычислений можно будет выполнить всего за 10 минут и 11 секунд! Очень неплохо!

• • •

Но почему мы можем так поступить? Ответ на этот вопрос кроется в самом определении отложенного палиндрома! Согласно ему, отложенный палиндром — это такое число, которое в результате многократного выполнения над ним операции Перевернуть-И-Сложить становится палиндромом. Нам интересна только самая первая операция этого увлекательного процесса.

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

Для 2-значных чисел интереснее: у нас две цифры, формирующие одну пару. На примере числа 14 можно показать, что результат одной операции Перевернуть-И-Сложить (14 + 41 = 55) будет таким же и для чисел 23, 32, 41 и 50! Легко заметить, что у всех этих чисел сумма двух цифр одна и та же и равна 5! И это самое важное!

При сложении числа с его обратной копией мы фактически складываем пары цифр, симметричных относительно его центра. И нам важны не столько сами цифры, сколько их сумма. Возможных вариантов которой всего 19: от 0 (для цифр 0 и 0), до 18 (для цифр 9 и 9). Так как первая цифра числа не может быть нолём, то всего комбинаций двух цифр здесь будет 9×10=90, тогда как вариантов их суммы — только 18 (все, кроме нулевой)!

Если теперь из всех 2-значных чисел, проверяя подряд каждое, мы будем выписывать только самое первое число, дающее уникальную сумму его цифр, то у нас получится следующий ряд: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 29, 39, 49, 59, 69, 79, 89 и, наконец, 99. Все 18 чисел этого ряда являются каноническими, то есть наименьшими возможными числами (для соответствующих сумм их пар цифр).

У 3-значных чисел по-прежнему всего одна пара цифр (это первая и последняя цифра). А также цифра, стоящая в середине, которая может принимать любые значения. Поэтому для каждого из 18 вариантов пары у нас будет по 10 вариантов средней цифры, то есть 18×10=180 комбинаций.

При переходе к 4-значным числам, центральная цифра превращается в центральную пару цифр. Но так как тут обе цифры могут быть любыми, их сумма будет иметь не 18 вариантов (как у крайних цифр), а все 19. То есть здесь мы получим 18×19=342 комбинации двух пар.

Каждое из этих 342 4-значных чисел будет давать уникальный результат после одной операции Перевернуть-И-Сложить. Для остальных 8,658 чисел результат одной операции будет совпадать с результатом одного из этих 342 канонических чисел в силу того, что будут совпадать соответствующие суммы пар симметричных цифр.

Иными словами, проверив, что, например, число 1,697 превращается в палиндром 881188 за 5 итераций, мы можем быть уверены, что все 8×4=32 числа, исходное и полученные путём изменения пар симметричных цифр так, чтобы их сумма оставалась неизменной, являются отложенными палиндромами, разрешающимися за 5 итераций, и дают в результате палиндром 881188. Всё потому, что уже после первой операции Перевернуть-И-Сложить все они дают одинаковый результат, а значит этот процесс полностью совпадает и далее вплоть до получения палиндрома.

Таким образом, из этих 32 чисел нам достаточно проверить только каноническое (наименьшее возможное) число 1,697, а 31 оставшееся — пропустить, и тем самым значительно увеличить скорость поиска!

• • •

Эти рассуждения справедливы в той же степени и для чисел Лишрел. Отличие лишь в том, что для них процесс никогда не заканчивается. Но, начиная со второй операции Перевернуть-И-Сложить и далее, также полностью совпадает. В этом можно убедиться, взяв любое число Лишрел, например 7,059, и поменяв его цифры: 8,328 (суммы пар у обоих чисел соответственно равны 16 и 5).

Продолжая увеличивать длину числа далее, мы приходим к закономерности: при повышении количества знаков от чётного к нечётному, количество чисел, которое необходимо проверить, увеличивается в 10 раз. А при переходе от нечётного количества цифр к чётному — в 1.9 раза. Исключение в этом правиле — лишь переход от 1-значных чисел к 2-значным, когда 9, увеличиваясь ровно в 2 раза, становится 18.

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

Так, если проверка всех 21-значных чисел заняла бы 7 недель, то проверка всех чисел следующего диапазона при тех же задействованных мощностях (в среднем 13.72 миллиона проверяемых чисел в секунду) потребовала бы ровно 3 месяцев. Все 23-значные числа удалось бы проверить лишь за 2.55 года! А все 25-значные — не менее, чем за 48 лет!