Самовлюблённые числа: когда нарциссизм и бесполезность вдохновляют

Самовлюблённые числа (они же числа Армстронга, в оригинале Narcissistic numbers) — это числа, равные сумме своих цифр, возведённых в степень количества этих цифр. Например, 153 — самовлюблённое число, потому что 

Известный математик Г. Харди отзывался об этом свойстве так: «Всё это забавные факты, весьма подходящие для газетных колонок с головоломками, способные позабавить любителей, но ничего в них не затронет сердце математика». 

Но действительно ли самовлюблённые числа настолько бесполезны? Чтобы узнать ответ, зайдите под кат.

Математика нарциссизма

Поговорим о математических свойствах самовлюблённых чисел. 

Первое свойство довольно очевидно. Факт, что число является или не является самовлюблённым, зависит от системы счисления. Например, число 153 самовлюблённое в обычной (десятичной) системе счисления. Но в восьмеричной системе оно записывается как 231₈.

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

Второе очевидное свойство: всякое число, состоящее из одной цифры (в данной системе счисления), самовлюблённое.

и так далее.

Третье очевидное свойство: в единичной (унарной) системе счисления любое число самовлюблённое, поскольку записывается количеством единиц, равным самому числу. Например:

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

Самое маленькое n-значное число — это единица с (n-1) нулями, то есть 10^(n-1).

Самое большое значение, которое может принимать сумма энных степеней цифр — это .

При увеличении количеством цифр на единицу к самому маленькому числу с этим приписывается ноль, то есть оно увеличивается в 10 раз. А самое большое значение суммы степеней цифр становится  (n+1)*9^(n+1), то есть оно увеличивается в раз. Поначалу и второе число, и скорость его роста выше. Но довольно быстро становится меньше десяти. С этого момента разрыв начинает сокращаться, и в какой-то момент оказывается, что сумма степеней цифр даже не сможет иметь столько же цифр. А значит, самовлюблённые числа с таким (и большим) количеством цифр невозможны.

Если конкретнее, этот момент наступает при n = 61:

В последнем числе 60 цифр (можете пересчитать). Значит, в десятичной системе счисления самовлюблённое число может иметь не более 60 цифр. А следовательно, количество таких чисел конечно.

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

Второе неочевидное свойство самовлюблённых чисел состоит в том, что… его нет. В каком-то смысле Харди был прав. За этими числами не стоит какой-то глубокой и интересной математической теории. Просто в некоем божественно-математическом ГИБДД им выдали козырные номера. 

На этом статью можно было бы закончить. И всё же она не заканчивается. 

Самовлюблённое программирование

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

И в этом качестве самовлюблённые числа вызвали у программистов интерес. Почему? Из-за огромной размерности задачи. Наивное и неинтересное решение — перебрать все числа-кандидаты и для каждого из них проверить, является ли оно самовлюблённым. Но верхняя граница для самовлюблённых чисел в десятеричной системе счисления — 10^60, а значит, чисел-кандидатов очень много. Если каждую наносекунду проверять по триллиону триллионов чисел, то для завершения перебора понадобится в два триллиона миллиардов раз больше времени, чем текущий возраст Вселенной.
 
 Когда неинтересное решение не подходит, программистам становится интересно, и они начинают выдумывать разные хитрости. О них и пойдёт речь в оставшейся части статьи.

 

Главная хитрость

 

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

Рассмотрим маленький и удобный пример: пусть мы ищем самовлюблённые числа из трёх цифр в четверичной системе счисления. Если действовать простым перебором, то потребуется перебрать чисел:

100₄

101₄

102₄

103₄

110₄

…

329₄

330₄

331₄

332₄

333₄

 

Для каждого из них нам потребуется вычислить функцию:

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

Наборы цифр можно кодировать массивами из четырёх чисел:

[количество нулей, количество единиц, количество двоек, количество троек]

Можно посчитать, что существует всего 18 наборов из трёх четверичных цифр:

[3, 0, 0, 0]
[2, 1, 0, 0]
[2, 0, 1, 0]
[2, 0, 0, 1]
[1, 2, 0, 0]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 1, 1]
[1, 0, 0, 2]
[0, 3, 0, 0]
[0. 2, 1, 0]
[0, 2, 0, 1]
[0, 1, 2, 0]
[0, 1, 1, 1]
[0, 0, 3, 0]
[0, 0, 2, 1]
[0, 0, 1, 2]
[0, 0, 0, 3]

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

1. Начинаем с набора из одних нулей. В нашем примере это [3, 0, 0, 0]

2. Чтобы получить следующий набор, идём по массиву справа налево и находим первый элемент, из которого можно взять единицу и «переложить» направо. Например, в наборе [0, 2, 0, 1] этим элементом будет двойка. Единица не подходит, поскольку она уже в крайней правой позиции, из неё нельзя ничего переложить направо. Правый нуль не подходит, потому что из него нельзя взять единицу.

3. Если мы нашли такой элемент, берём из него единицу и перекладываем направо, а затем к этой же единице перекладываем всё, что есть в последнем элементе. Например, [0, 2, 0, 1] превращается в [0, 1, 2, 0].

4. Если же такого элемента не нашлось, значит мы закончили перебор.

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

Итак, с помощью Главной хитрости™ мы сократили перебор с 48 до 18 итераций. Точнее, на самом деле до 17 (набор из одних нулей заведомо не подходит). Но всё равно это меньше чем втрое. Звучит не очень круто. Одна треть вечности — это всё равно вечность, так? 

Но всё начинает звучать намного круче, если увеличить количество цифр. Количество наборов цифр растёт намного медленнее, чем количество чисел из этих цифр. Количество наборов десятичных цифр выражается следующей формулой: , где n — количество цифр. И эта функция растёт намного медленнее, чем 10^n - 10^(n-1) (количество чисел с n цифрами). Например, количество наборов из девяти цифр — 92 378, что примерно в 10 000 раз меньше, чем количество чисел из девяти цифр (900 000 000). Количество наборов из 60 цифр — 56 672 074 888. Жалкие 56 миллиардов. 

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

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

Хитрости поменьше

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

Использование lookup-таблицы

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

Быстрое отсечение по величине

Если мы вычислили сумму степеней, и оказалось, что она больше или меньше 10^(n-1) — сразу понятно, что в ней неправильное количество цифр. Можно пропустить этап с разбором на цифры и сравнением наборов цифр.

Быстрое отсечение ветвей

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

Быстрое отсечение по признаку делимости

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

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

Эффективная «длинная арифметика»

Большинство не-программистов (и даже некоторые программисты, чего уж греха таить) не задумываются об этом, однако компьютер не умеет нативно работать с очень длинными числами. Он внутренне представляет их как массивы более маленьких чисел, а при выполнении арифметических действий применяет к этим массивам специальные алгоритмы. Время работы этих алгоритмов зависит от длины чисел. Например, сложение 60-значных чисел вдвое медленнее, чем сложение 30-значных. А умножение и деление замедлятся даже более чем вдвое.

Разбор конкретных техник работы с большими числами выходит за рамки данной статьи (на эту тему написано много толстых книг), но, так или иначе, эффективная реализация «длинной арифметики» даёт ускорение ещё в несколько раз.

Параллельные вычисления, SIMD, GPU и прочее

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

«Встретимся посередине»

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

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

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