Самовлюблённые числа, известные также как числа Армстронга, представляют собой натуральные числа, которые в точности равны сумме своих цифр, каждая из которых возведена в степень, соответствующую общему количеству цифр в числе. Классический пример — 153, что легко проверить:
Выдающийся математик Годфри Харди весьма скептично относился к подобным объектам, называя их лишь занятными курьезами для досуга, неспособными привлечь внимание серьезного исследователя.
Так ли бессодержательны эти числа на самом деле? Попробуем разобраться в этом вопросе далее.
Математическая природа нарциссизма
Разберем основные свойства этих чисел.
Первое и наиболее очевидное: статус числа зависит от используемой системы счисления. Тот же 153 — «самовлюбленный» в десятичной записи, но в восьмеричной он выглядит как 231₈, и его сумма кубов цифр уже не вернет исходное значение.
Второе свойство: любая однозначная цифра в любой системе счисления формально является самовлюбленным числом, так как она равна самой себе в первой степени.
Третье: в унарной (единичной) системе счисления любое число — «самовлюбленное», поскольку оно состоит из суммы единиц.
Более содержательное утверждение: во всех системах счисления, кроме унарной, количество самовлюбленных чисел конечно. В десятичной системе, например, минимальное n-значное число — 10^(n-1), тогда как максимальная сумма n-х степеней цифр — n * 9^n. С ростом n первое значение растет экспоненциально быстрее, поэтому после определенного предела (n=61 для десятичной системы) существование таких чисел математически невозможно.
В конечном итоге, Харди был прав: за этими числами не стоит глубокой теории, это скорее случайный продукт правил позиционных систем счисления.
Алгоритмический подход
Тем не менее, для программистов поиск этих чисел стал классическим упражнением. Наивный перебор всех кандидатов — задача неподъемная из-за огромного пространства поиска. Поэтому решение требует изящных оптимизаций.
Главная стратегия
Ключевая идея состоит в том, что результат функции суммы степеней цифр не зависит от их порядка. Вместо проверки каждого числа, мы оперируем «наборами цифр» (мультимножествами).
Если мы кодируем набор цифр массивом их количеств, мы можем перебирать только уникальные комбинации, что радикально сокращает количество итераций. При увеличении длины числа количество таких комбинаций растет несоизмеримо медленнее, чем количество самих чисел, превращая невыполнимую задачу в вычислимую за разумное время.
Дополнительные приемы
Помимо фундаментального подхода с наборами цифр, профессионалы применяют ряд вспомогательных техник:
- Lookup-таблицы: Предварительное вычисление степеней цифр избавляет от необходимости возводить их в степень при каждой проверке.
- Отсечение (pruning): Использование граничных условий для быстрого пропуска неперспективных ветвей перебора.
- Признаки делимости: Сравнение остатков от деления на 9 (аналог в других системах) позволяет мгновенно отбросить заведомо неподходящие комбинации.
- Эффективная арифметика: Учитывая работу с большими числами, оптимизация низкоуровневых операций (сложение/умножение массивов) дает существенный прирост скорости.
- Встречная проверка (meet-in-the-middle): Разделение числа на две части и сопоставление их промежуточных состояний — наиболее сложный, но эффективный метод для экстремальных вычислений.
Пусть сами по себе самовлюбленные числа не несут фундаментальной научной ценности, но поиск способов их эффективного обнаружения — блестящая иллюстрация того, как спорная или «бесполезная» задача стимулирует развитие алгоритмической мысли и оптимизации.
