Задача. Системы счисления

Задача

Натуральное десятичное N - значное число называется числом Армстронга, если сумма его цифр, возведенных в степень N, равна самому числу.

Примеры: 153 = 13 + 53 + 33; 1634 = 14 + 64 + 34 + 44.

Найти все числа Армстронга для 1<=N<=9.

Решение

Конечно, данную задачу можно было решить "в лоб", т.е. сделать простой перебор всех 109 чисел и каждое число проверить. При этом на весьма солидной машине программа могла бы работать достаточно долго. Если бы цель задания заключалась только в нахождении чисел Армстронга, а не в составлении универсальной программы, разработка которой могла бы занимать большое время, то конечно, лучше было бы за 10 минут написать и 3 часа подождать.

Идея уменьшения класса исследуемых чисел заключается в следующем: можно делать перебор не самих чисел, а значений, которые могут получаться в результате степенной суммы (т.е. суммы цифр числа, возведенных в степень числа цифр этого числа). Здесь используется следующее свойство: от перемены цифр местами в числе степенная сумма не меняется. Т.е. например, незачем рассматривать все числа из класса: 135, 153, 315, 351, 531 и 513; достаточно рассмотреть одно из них, например, число 135; вычислить его степенную сумму: (135)ст = 153, а потом лишь убедиться в том что число 153 - это число Армстронга. Этот метод снижает число перебираемых чисел почти в N! раз. Сам же перебор осуществляется довольно просто: рассматриваются все числа, у которых любая цифра не меньше предыдущей и не больше последующей. Например: 12, 1557, 333 и т.д.

Итак, вышеописанный метод снизил число перебираемых чисел с 109 до приблизительно 200000. Но это не все на чем стоит останавливаться. Можно применить еще одну хитрость, которая заключается в следующем: можно значительно ускорить вычисление степенной суммы. Можно заметить, что при вычислениях часто приходится многократно возводить некоторое число в некоторую степень. Чтобы это оптимизировать вводится двухмерный массив, в i-ой строке и j-ом столбце которого находится значение степенной суммы i с основанием j (например, Degree[123,j] = 1j + 2j + 3j). Таким образом, используется значение массива Degree[i,j]. Это существенно ускоряет процесс вычисления, если это сравнивать с некоторым процессом, в котором используется функция Degree(i,j), каждый раз вычисляющая значение ij. Для вычисления выражения 10j аналогично используется массив Degree10. Нужно заметить, что такая операция возведения в степень в программе выполняется более 10000 раз; матрица Degree заполняется в начале программы, где операция возведения i в степень j выполняется около 8000 раз.

В промежутке 1<=N<=9 программа находит следующие 32 числа Армстронга:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153.

m-самовлюбленное число - натуральное число, которое равно сумме своих цифр, возведённых в степень m, где m - некоторое натуральное число. Числа Армстронга - частный случай таких чисел.

Число Смита — такое составное число, сумма цифр которого (в данной системе счисления) равняется сумме цифр всех его простых сомножителей. Так, примером числа Смита может служить 202, поскольку 2 + 0 + 2 = 4, и 2 + 1 + 0 + 1 = 4 (202 = 2 * 101). У. Л. МакДэниел доказал, что существует бесконечно много чисел Смита. Насчитывается 29 928 чисел Смита в пределах до 1 000 000. Первые 50 чисел Смита: 4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086.

2. Системы счисления

       Существует много задач на системы счисления. Для их решения нужно уметь переводить числа между системами счисления. При это генерация определённого числа делается с помощью ДП