Числа Мюнхгаузена и анти-Мюнхгаузена

Числом Мюнхгаузена называется натуральное число n, для которого сумма цифр, каждая из которых возведена в степень самой себя, равна n, например, 3435 = 33 + 44 + 33 + 55.

В десятичной системе счисления чисел Мюнхгаузена совсем мало - в пределах до 500 000 000 их всего 4, если считать ноль в нулевой степени равным нулю.

Подумал, что сейчас придуманных чисел анти-Мюнхгаузена, где показатель степени в представлении числа берётся не i, а 9-i, например, 1074 = 19-1 + 09-0 + 79-7 + 49-4 = 18 + 09 + 72 + 45 едва ли будет больше, и впрямь, в тех же пределах счёта нашлось всего 4 числа: 0, 1, 8, 1074.

Потом только дошло, что можно доказать заведомо конечное количество таких чисел в любой позиционной системе счисления.

Ниже прикреплён скрипт на PHP, который проверял задачу на локальном хосте. Для исходных чисел Мюнхгаузена (см. комментарий в коде) скрипт, как и положено, нашёл значения 0, 1, 3435, 438579088.

Мне не пришлось пользоваться библиотекой bcmath, так как с размерностями задачи справится и обычная арифметика, но всё равно даже на нормальном компьютере время выполнения скрипта может составить пару минут.

<?php 
 set_time_limit (0); //не ограничиваем время выполнения
 error_reporting (E_ALL);
 $pwr = array_fill (0, 10, 0);
 for ($i = 1; $i < 10; $i++) {
  $pwr[$i] = pow($i, 9 - $i);
  //поставьте строкой выше $i вместо 9 - $i, будут числа Мюнхгаузена
 }
 $limit =  500000000;
 for ($i = 0; $i < $limit + 1; $i++) {
  $sm = 0;
  $temp = $i;
  while ($temp) {
   $sm += $pwr[($temp % 10)];
   $temp = floor($temp / 10);
  }
  if ($i == $sm) {
   echo $i . '<br>'. PHP_EOL;
  }
 }
?>

13.10.2021, 02:44 [622 просмотра]