Самопростые числа

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

Цифросложение и порождённые числа

Рассмотрим основную процедуру, которую Капрекар называет цифросложением. Выберем любое целое число и прибавим к нему сумму его цифр. Например, если мы выберем число 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. С тех пор Капрекару удалось открыть, как он предполагает, наименьшие числа-соединения с 5 и 6 генераторами.

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

Самопорождённое число — это число, у которого нет генератора, по словам Капрекара, «оно порождает самое себя». Существует бесконечно много самопорождённых чисел, но встречаются они гораздо реже, чем порождённые числа. В пределах первой сотни имеется всего 13 самопорождённых чисел: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86 и 97. Простые самопорождённые числа называются самопростыми числами. Хорошо известное «циклическое» число 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¹⁶.

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

Ссылки

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