Software & Systems

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

НЛ. Красовский.

Задача "найти целые числа, равные сумме некоторых степеней их цифр" [3], на первый взгляд, проста.

Вот два ее решения [4]:

153 = I3 + 53 + З3 , 1634 = I4 + б4 + З4 + 44.

Каждое приведенное число равно сумме некоторой степени его цифр (показатель степени 3 для числа 153 и показатель степени 4 для числа 1634). Просмотрев все числа, приведенные в [3, 4, 5], видим, что математическая формулировка задачи такова: "найти целые числа, удовлетворяющие равенству

при целом к .

А вот число 135 не удовлетворяет равенству [3] ( 135 ^ lk + 3* +5к при любом целом значении к) и, следовательно, не является решением задачи. Но число 135 интересно тем, что оно удовлетворяет формулировке, приведенной в [3], так как 135 = I1 + З2 + 53. В дальнейшем формулировкой задачи будем полагать условие, содержащее формулу (1).

Хронология решения задачи такова. После опубликования задачи и некоторых достигнутых результатов в [5] некоторые читатели стали использовать ЭВМ для нахождения новых решений. Так, в [4] находим сообщение, что с помощью ЭВМ БЭСМ-6 были проверены числа в интервале от 1 до 1000000 и для степеней от 1 до 19. Это позволило найти четыре новых решения задачи.

Следующей оказалась ЭВМ СМ-4 ([3]), с помощью которой были проверены числа в интервале от 1 до 1000000000 для степеней 7, 8, 9. В результате этого удалось получить еще девять новых решений задачи.

Может возникнуть вопрос, вынесенный в заголовок [1] (правда, а [1] дело посерьезней — затрачено 3000 часов машинного времени суперЭВМ "Крей-1" для доказательства отсутствия конечных плоскостей проекций 10-го порядка). Думаю, мало найдется людей, которые усомнятся в правильности решений, найденных с помощью ЭВМ. Но почему бы и не усомниться?!

Критерием для уменьшения количества проверяемых на соответствие формуле (1) чисел послужили два соображения.

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

то есть в записи числа вида а ... а п = 6. Ми-

1                   и

нимальное такое число L = 100000, макси-

mln

мальное L = 999999. Максимальным чис-лом, полученным после суммирования возведенных в некоторую степень к цифр числа, будет число S = 6-9*. Понятно, что любое к,

тая

претендующее быть решением, должно удовлетворять неравенству L < S , то есть 100000 < 6-9 ; решая это неравенство, находим, что для шестизначных чисел при показателе степени, меньшем 5, решений не существует. Число L , как и следующее за ним число

min

L + 1 (то есть 100001), решением задачи не

mm

является. Следующее за ними число L           =

minim

L +2 (то есть 100002). Минимальным чис-

mln             ч                                               '

лом, полученным после суммирования возве денных в некоторую степень к цифр числа, бу дет число S           = 1Ь + 2к. Понятно, что любое

minim

к, претендующее быть решением, должно удовлетворять неравенству L  > S , то есть

г.ппппъ  «к                               nk                            maI                                               minim

999999 > 1 + 2 ; решая неравенство, находим, что для шестизначных чисел при показателе степени, большем 19, решений не существует. Таким образом, для шестизначных чисел в ра венстве (1) к может принимать только зна чения,                         удовлетворяющие               неравенству 5 < к < 19.

Во-вторых, была определена зависимость количества отдельных цифр в числе от значнос-ти числа. Пусть нас по-прежнему интересуют шестизначные числа, а рассматриваемым показателем степени будет число S. Максимальным количеством цифры 5 в таких числах будет число [999999/58] ([ ] — целая часть числа), то есть 2. Ведь не имеет смысла искать шестизначное число, содержащее более двух цифр 5 при показателе степени 8, так как 2-5 < 999999, а (2 + 1).58 > 999999.

Вооружившись современными счетами (калькулятором "Искра-ШМ", максимальная разрядность 12 цифр), удалось найти следующие новые решения задачи:

—  для седьмой степени — 14459929;

—  для девятой степени — 146511208.

Интересно, что эти решения должна была найти ЭВМ СМ-4, но она их почему-то не нашла . . .

Удалось найти решения и там, где еще "не ступала нога" ЭВМ:

—  для десятой степени — 4679307774;

—  для одиннадцатой степени — 94204591914;

—  для тринадцатой степени — 564240140138.

На пути поиска новых решений встретилось, на первый взгляд, непреодолимое препятствие — разрядность калькулятора. Но, ознакомившись с [2] и используя предложенную там методику, удалось преодолеть ограничение разрядности и на двенадцатиразрядном калькуляторе найти 14-разрядное решение задачи — 28116440335967 при показателе степени 14 (прием был использован очень простой — число представляется как сумма двух чисел по формуле а ... а = а ... а -10 +а ...а).

J „ 1                   п          1           п-10                    л-9           п'

Но самыми красивыми решениями задачи являются числа 0 и 1. Всем известно еще со школьной скамьи, что единица (ноль) в любой целой степени равна единице (нулю). Сюда же

относится и -1, равное, правда, самому себе только при нечетном показателе степени. Резюме простое:

•    доверяйте ЭВМ;

•    берегите ЭВМ, не перегружайте ее — поду майте над алгоритмом счета;

•    проверяйте результаты;

•    если найдена ошибка, не вините в ней ЭВМ.

СПИСОК ЛИТЕРАТУРЫ

1.     Верить — не верить? // Информатика и образование. 1989. NS.

2.     Как оперировать с тысячезначнымн числами и зачем это нужно // В мире науки. 1984. N6.

3.     Математические неожиданности // Наука и жизнь. 1982. N5.

4.     Математические неожиданности // Наука н жизнь. 1981. N10.

5.     Математические неожиданности // Наука и жизнь. 1972. N1.