Пятые степени цифр

[main.c]

Есть задачка:

Удивительно, но существует только три числа, которые могут быть записаны в виде суммы четвертых степеней их цифр:

$$ 1634 = 1^4 + 6^4 + 3^4 + 4^4 $$

$$ 8208 = 8^4 + 2^4 + 0^4 + 8^4 $$

$$ 9474 = 9^4 + 4^4 + 7^4 + 4^4 $$

$1 = 1^4$ не считается, так как это - не сумма.

Сумма этих чисел равна $1634 + 8208 + 9474 = 19316$.
Найдите сумму всех чисел, которые могут быть записаны в виде суммы пятых степеней их цифр.

Решать можно как угодно, имеется ввиду не обязательно чисто аналитически найти все эти числа, можно и программно. Я так и собираюсь, но мне нужна верхняя оценка этих чисел. Тогда я мгновенно переберу, например, 100 000 чисел и получу ответ. Проблема в том, как мне получить эту самую верхнюю оценку?

-- 03.01.2016, 12:13 --

Хотя для начала стоит как-нибудь вообще доказать, что эта верхняя граница есть.

[arseniiv]

(Оффтоп)

main.c в сообщении #1087721 писал(а):

$1 = 1^4$ не считается, так как это - не сумма.

Нематематично. Чем сумма из одного (или нуля) слагаемых хуже остальных?

[gris]

100000 маловато будет, наверное. Но более, чем шестизначных, уж конечно нет. $6\cdot 9^5=354294$ Ну и так далее.

[Евгений Машеров]

Ну, показать существование верхней границы просто. Число из n разрядов (принимая старший ненулевым) не менее $10^{n-1}$, а сумма девятых степеней его цифр не более $n 9^5=59049n$. То есть существует такое n, что заведомо число выше суммы его цифр. Можно, видимо, получить и более точную оценку, чем $n=7$. Но надо ли? Перебор цифр до миллиона займёт меньше времени, чем написание программы.
Да, и если учитывать и тривиальные решения, чем $0^4=0$ хуже?

[main.c]

Спасибо, я уже нашёл все числа, вот только хочется теперь строго найти верхнюю оценку.
Назовём функцию, которая суммирует все цифры в числе, возведенные в 5 степень $f_1(x)$, а функция $f_2(x) = x$. Тогда:
$f_1(x) \leq g(x) = (\lg_{10}x + 1) \cdot 9^5$
$g'(x) = \frac{9^5}{x\ln10}$
$f_2'(x) = 1
Уже при $x >100000 \quad g'(x) < f_2'(x)$, начиная ровно с $x = 389140 \quad g(x) < f_2(x)$, то есть $\forall x \geq 389140 \quad f_1(x) < f_2(x)$
Вроде бы нигде не ошибся)

[gris]

Раз первая цифра не больше тройки, то оценку можно улучшить до $299999$.

[VAL]

main.c,
посмотрите ММ71

[Someone]

Но постановка задачи там другая…

[VAL]

Someone в сообщении #1088031 писал(а):

Но постановка задачи там другая…

Я и не утверждал, что та же. Но близкая.

[Someone]

Но решений в постановке топикстартера намного больше, и не видно ограничений на степень. Хотя, конечно, его постановка задачи не новая: https://oeis.org/A046761/b046761.txt.

[VAL]

Someone в сообщении #1088083 писал(а):

Но решений в постановке топикстартера намного больше, и не видно ограничений на степень.

Не понял!
Разве постановка ТС не ограничивается частным случаем? А именно числами равными суммам 5-х степеней своих цифр в десятичной системе.

[Someone]

VAL в сообщении #1088119 писал(а):

Разве постановка ТС не ограничивается частным случаем? А именно числами равными суммам 5-х степеней своих цифр в десятичной системе.

Ну, там у него и четвёртая степень упоминается…