Сумма степеней своих цифр

[Руст]

Найти все числа которые в десятичной записи представляются в виде суммы первой циры (цифры при старшем разряде, отличной от нуля) в первой степени плюс второя цифра во второй степени плюс третья цифра в третьей степени и т.д. (до последней цифры включительно).

[maxal]

A032799

[Руст]

Для каких натуральных n, существуют натуральные числа х, равные сумме n - ых степеней своих цифр(в десятичной записи)?

[juna]

Для начала отметим очевидное ограничение:
если $k$ - количество разрядов числа $x$, то $\frac{ln(\frac{10^k-1}{k})}{ln9}\leqslant n\leqslant 1+\frac{ln10^{k-1}}{ln2}$
Если $x=1$,то $n$ - любое

[Руст]

Конечно х=0 и х=1 является решением при любом натуральном n (которых можно назвать тривиальными решениями). Однако я имел ввиду нетривиальные решения, например $407=4^3+0^3+7^3$ или
3009336689622424785094591221547283824126694123199598 являющееся суммой 53 -их степеней своих цифр.

[juna]

Должно быть $k=n$

[Руст]

Если k=n получается ограничение на число разрядов, последнее решение с таким свойством:
115132219018763992565095597973971522401, являющейся суммой своих цифр в 39 -ой степени.

[juna]

Вообще-то да, ограничение $\frac{ln(\frac{10^k-1}{k})}{ln9}\leqslant k$ нарушается при к>33. Просто 52 разряда предыдущего монстра неправильно посчитал.
Руст, а существует аналитическое решение - или это подвиги железных братьев?

[Руст]

Артамонов Ю.Н. писал(а):

Вообще-то да, ограничение $\frac{ln(\frac{10^k-1}{k})}{ln9}\leqslant k$ нарушается при к>33. Просто 52 разряда предыдущего монстра неправильно посчитал.
Руст, а существует аналитическое решение - или это подвиги железных братьев?

Ваше ограничение не верное если число имеет к разрядов и равно сумме n-тых степеней, обозначив количество 9 через к9, число 8 -к к8,... получаем уравнение:

$$x=\sum_{i=1}^9 k_i^n, \sum_{i=1}^9 k_i\le k.$$

Соответственно k=n возможно, если $k*9^k>10^{k-1}$ или $10k*0.9^k>1$ А это ограничение выполняется вплоть до k=59. На самом деле, число из одних девяток не является решением. Соответственно максимальное решение с этим свойством 39 ти значное. А у монстра k=52 n=53.
Аналитической формулы для вычисления таких чисел конечно нет. Тем не менее, можно существенно сократить вычисление, предварительно подсчитав числа $9^n,8^n,7^n,6^n,5^n,4^n,3^n,2^n$. Для разных наборов k9,k8,... считаем соответствующую сумму и подсчитываем количество девяток m9, количество восьмерок m8, и т.д. Это дает отображение из девятимерного пространства целочисленных векторов в себя. Неподвижные точки являются решениями. На самом деле, я использовал ещё некоторые тонкости, сокращающие вычисление, связанное с чётностью и делением на 3 и на 9.

[maxal]

http://www.nsu.ru/phorum/read.php?f=29&i=4791&t=4791

[juna]

Ограничение не совсем точное. Для того, чтобы оценить нижнее ограничение для $k$ разрядов берем число из одних девяток, как дающее максимальную сумму $n$ - х степеней $k9^n=10^k-1$ - и получаем искомое ограничение. Но на самом деле из-за неоднородности цифр возможно и меньшее $n$ - поскольку, хотя число из одних девяток и дает максимальную сумму $n$-х степеней, оно в тоже время дает и максимально возможное число $k$ разрядов. Эту противоречивую тенденцию можно уравновесить введением поправки в числитель. Например, хорошо согласуется с экспериментом такая формула $\frac{ln(\frac{10^k-1}{1.7k})}{ln9}$

[Руст]

Для ограничения лучше не к девяток, а чуть меньше например k-1 или k-2, тогда в первом случае возможно $2$10^{k-1}-1=1+(k-1)*9^n$, а во втором $11$10^{k-2}-1=1+(k-2)9^n$. Однако эти уточнения ничего существенного не дают.

[maxal]

Руст писал(а):

Если k=n получается ограничение на число разрядов, последнее решение с таким свойством:
115132219018763992565095597973971522401, являющейся суммой своих цифр в 39 -ой степени.

Такие числа называются числами Армстронга. См.
http://mathworld.wolfram.com/NarcissisticNumber.html
A023052
и далее по ссылкам.

[Руст]

А вообще то первоначальный вопрос звучал, при каких n существуют числа, являющиеся суммой n - ых степеней своих цифр. При этом если n>39 то количество разрядов будет меньше n (хотя их так же можно считать n разрядными, у которых первые цифры нули). Конечно или бесконечно множество таких чисел. К сожалению ответа на эти вопросы по этим ссылкам не удалось найти. Конечно хорошо, что узнали название для чисел с (n=k) - числа Армстронга.

[juna]

По предыдущей ссылке maxalа

Рустем писал(а):

Если ограничиваться условием равенства числа знаков n со степенью к, таких чисел будет немного. Единственное число для которого n больше к (исключая 0 и1) это 194979 являющееся суммой 5 ых степеней своих цифр. А чисел с n=к несколько десятков, например ещё 38 значное число
12815792078366059955099770545296129367. Числа когда n меньше к так же можно рассматривать как к значные добавляя спереди нули (как при подсчёте счастливых чисел). Тогда рассматривая решения при любом к, исключая 0 и 1 получаем, что не при всех к существует решения. Далее, рассматривая целочисленный вектор $m[i],i=1,2,...,9$, обозначающий количество цифр i в искомом числе отображаем целочисленные вектора в себя по формуле ${m[i]}$ в ${n[i]}$, где $n[i],i=1,2,...,9$ определяется как количество цифр $i $у числа сумма$(m[i]*i^k),i=1,...9$. Неподвижные точки этого отбражения дают эти числа. Тут проявляется не случайный характер этого отображения (у случайного отображения количество неподвижных точек было бы гораздо больше и быстро бы росло с ростом к, а здесь К(37)=К(38)=3). Одно ограничение получается по модулю 9 сумма$(m[i]*(i^k-i))=0(mod9)$. Откуда в частности получается, что количество цифр 2,5,8 в сумме должно делится на 3 при чётном к. Я написал программу для получения таких чисел с учётом этих особенностей для ускорения подсчёта. Представленное 21 значное число продукт 15 минутной работы.

А первоначальные значения вектора $m[i]$ как задаются? Ведь найденные неподвижные точки будут зависить от этого и нельзя гарантировать, что найдены все.