Самопорождённые числа

Рассмотрим процедуру, которую Капрекар называет цифросложением. Выберем любое целое число и прибавим к нему сумму его цифр. Например, если мы выберем число 47, то сумма его цифр 4 + 7 = 11 и 47 + 11 = 58. Новое число 58 называется порождённым числом, а исходное число 47 — его генератором. Процесс можно повторять неограниченно, образуя порождаемую цифросложением последовательность 47, 58, 71, 79, …

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

Порождённые числа могут иметь более одного генератора. Наименьшее число, имеющее более одного генератора (Капрекар называет такие числа соединениями), равно 101 и у него два генератора: 91 и 100. Наименьшее число-соединение с тремя генераторами равно 10 000 000 000 001 и порождено числами 10 000 000 000 000, 9 999 999 999 901 и 9 999 999 999 892. Наименьшее число с четырьмя генераторами, открытое Капрекаром 7 июня 1961 года, имеет 25 знаков: 10²⁴ + 102. Таким образом, наименьшие числа, имеющие n=2, 3, … генераторов образуют последовательность:

101, 10000000000001, 1000000000000000000000102, … (последовательность A006064 в OEIS)

Капрекару удалось также открыть, как он предполагает, наименьшие числа-соединения с 5 и 6 генераторами.

Самопорождённое число — это число, у которого нет генератора, по словам Капрекара, «оно порождает само себя». Существует бесконечно много самопорождённых чисел, но встречаются они гораздо реже, чем порождённые числа. Самопорождённые числа образуют последовательность:

1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97, … (последовательность A003052 в OEIS)

Простые самопорождённые числа называются самопростыми числами. Хорошо известное «циклическое» число 142 857 (при умножении его на числа от 1 до 6 всегда получается произведение, записанное теми же 6 цифрами, только переставленными в циклическом порядке) принадлежит к числу самопорождённых чисел. Самопорождёнными являются и такие числа, как 11 111 111 111 111 111 111 и 3 333 333 333.

Самопорождёнными являются некоторые степени числа 10. Число 10 порождено числом 5, число 100 — числом 86, 1 000 — числом 977, 10 000 — числом 9 968 и 100 000 — числом 99959. Однако 1 000 000 является самопорождённым числом, а следующая за миллионом степень десятки, которая является самопорождённым числом, — это 10¹⁶.

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

Самопорождённые числа впервые описаны в 1949 году индийским математиком Д. Р. Капрекаром, который посвятил им несколько книг. Долгое время за пределами Индии самопорождённые числа не были известны, пока в 1974 году о них (под другим названием) не появилась статья в журнале American Mathematical Monthly,[1] в которой доказывалось, что существует бесконечное множество самопорождённых чисел.

Во втором томе «Детской энциклопедии» (СССР), посвящённом математике, есть статья о самопорождённых числах, где они называются «числами-самородками».[2]

• Мартин Гарднер, Самопорождённые числа.
• Метод проверки числа на самопорождённость