В мир информатики # 86 (16–28 февраля).
Задачник

Задачи о порожденных
и самопорожденных числах

Г.В. Трофимов,
учитель информатики лицея № 1
г. Балаково Саратовской обл.

В газете-вкладке “В мир информатики” № 80 (“Информатика” № 21/2006) была опубликована заметка, связанная с “постоянной Капрекара”, названной так в честь открывшего ее индийского математика Д.Капрекара. В 1949 году Капрекар открыл один замечательный класс чисел, которые назвал самопорожденными числами.

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

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

Рассмотрим ряд задач.

3. Найти сумму первых n элементов последовательности, порожденной из заданного числа.

Для решения задач целесообразно разработать функцию расчета суммы цифр заданного числа. На школьном алгоритмическом языке она выглядит так1:

алг цел СуммаЦифр(арг цел n)

нач цел m, сумма, посл_цифра

m := n |m – аналог числа n

сумма := 0

нц пока m > 0

|Определяем последнюю цифру числа m

посл_цифра := mod(m, 10)

|Учитываем ее в сумме цифр

сумма := сумма + посл_цифра

|Отбрасываем последнюю цифру

m := div(m, 10)

кц

знач := сумма |Значение функции

кон

— где mod и div — функции, определяющие соответственно остаток и целочисленное частное от деления первого аргумента на второй (в программах на других языках программирования для этого используются не функции, а специальные операции).

С использованием функции СуммаЦифр программы решения задач 1 и 2 могут быть оформлены следующим образом:

алг Задача_1

нач цел генератор, порожденное

вывод нс, "Задайте число-генератор"

ввод генератор

порожденное := генератор +

СуммаЦифр(генератор)

вывод нс, "У этого генератора "

вывод "порожденное число равно ",

порожденное

кон

алг Задача_2

нач цел а, n, генератор, порожденное, i

вывод нс, "Задайте исходное число-генератор"

ввод а

вывод нс, "Задайте количество чисел "

вывод "в последовательности "

ввод n

|Принимаем исходное число в качестве

|генератора

генератор := а

вывод нс, "Последовательность порожденных

чисел: "

нц для i от 1 до n

|Определяем очередное порожденное число

|порожденное := генератор +

|СуммаЦифр(генератор)

вывод порожденное

|Принимаем его в качестве генератора

|для определения следующего

|порожденного числа

генератор := порожденное

кц

кон

Может ли порожденное число иметь более одного генератора? Да, но лишь в том случае, если оно превышает 100. Наименьшее число, имеющее более одного генератора (Капрекар назвал такие числа соединениями), равно 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 знаков: единица, после которой следует 21 нуль, и число 102.

Капрекар ввел также понятие “самопорожденное число” — число, у которого нет генератора. По словам математика, “оно порождает самое себя”. Существует бесконечно много самопорожденных чисел, но встречаются они гораздо реже, чем порожденные числа. В пределах первой сотни натуральных чисел имеется всего 13 самопорожденных чисел: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86 и 97. Самопорожденными являются, например, такие числа, как 11 111 111 111 111 111 111 и 3 333 333 333.

Никто пока не открыл нерекуррентную формулу2, позволяющую получать все самопорожденные числа, но проверить любое число на “самопорожденность” (то есть установить, является ли данное число самопорожденным или нет) можно с помощью программы. При этом заметим, что алгоритм, основанный на переборе всех возможных генераторов заданного числа n (они могут находиться в диапазоне от 1 до n –13 включительно), является неэкономным — при больших n будет происходить много расчетов. Оптимальный алгоритм выглядит так:

1) найти цифровой корень4 заданного числа n;

2) если цифровой корень нечетный, то прибавить к нему 9 и разделить на 2, в противном случае — разделить его на 2 (полученное частное обозначим через c);

3) вычесть c из n;

4) проверить, не порождает ли полученная разность число n. Если нет, то вычесть 9 из последнего результата и проверить снова. Продолжать вычитать девятку k раз (k — число цифр знаков в числе n) или до того момента, когда будет порождено число n.

Если за k шагов генератор числа n не получен, то n — самопорожденное число.

Соответствующая программа:

алг Проверка_на_самопорожденность

нач цел n, c, цифр_корень, k, разность, p

вывод нс, "Задайте число n"

ввод n

|Определяем количество цифр k в нем

k := КоличЦифр(n)

|Находим цифровой корень числа n

цифр_корень := ЦифровойКорень(n)

|Определяем частное С

если mod(цифр_корень, 2) = 1

то

C := div((цифр_корень + 9), 2)

иначе

C := div(цифр_корень, 2)

все

разность := n – c

p := 1 |Число проверок

нц пока Порожденное(разность) <> n и p <= k

разность := разность – 9

p := p + 1

кц

если p > k

то

вывод нс, "Число n – самопорожденное"

иначе

вывод нс, "Число n самопорожденным

не является"

все

кон

— где КоличЦифр — функция, определяющая количество цифр в числе n; она во многом аналогична описанной ранее функции СуммаЦифр;

— цифр_корень — цифровой корень числа, он рассчитывается с помощью функции ЦифровойКорень:

алг цел ЦифровойКорень(арг цел n)

нач

если mod(СуммаЦифр(n), 9) = 0

то

знач := 9

иначе

знач := mod( СуммаЦифр(n), 9)

все

кон

— величины c и k описаны в алгоритме;

— разность — величина, определяемая на этапе 3 алгоритма.

Задания для самостоятельной работы

1. На известном вам языке программирования разработайте программы решения задач 1–3 (см. с. 37), а также задачи 4 “Среди трехзначных чисел найти все те, у которых два генератора” и задачи 5 “Найти все самопорожденные числа в заданном промежутке”.

Определите искомые величины для следующих условий:

2. Установите правило определения суммы всех цифр в последовательности, порождаемой цифросложением, по известным значениям первого и последнего числа последовательности.