Факториал как сумма степеней

[Ktina]

В общем виде задача выглядит следующим образом. Для каждого $n\in\mathbb{N}$ требуется определить, какое наименьшее количество степеней числа $n$ (с показальным натурателем) нужно сложить, чтобы получить факториал натурального числа?

Ясно, что достаточно одной степени единицы или одной степени двойки, так как числа 1 и 2 являются факториалами.

Степеней тройки уже потребуется как минимум две, так как все степени тройки нечётны, а получившийся факториал будет не меньше 3, а значит, чётным: $3^1+3^1=3!$

Степеней четвёрки нужно уже как минимум 3 (по аналогичной причине): $4^2+4^1+4^1=4!$

А вот четырьмя степенями пятёрки, кажется, уже не обойтись (меньше четырёх нельзя, так как получившийся факториал будет делиться на 5, а значит и на 4, а степень пятёрки даёт остаток 1 при делении на 4). Например, чтобы получить $5!=120$, их нужно не менее 8. Число $6!=720$ тоже менее чем 8-ю степенями пятёрки не получишь. Короче, там уже становится интересненько.

Степень шестёрки снова нужна всего одна, так как шестёрка - факториал.

Степеней семёрки, по-моему, нужно уже не менее 12 (теоретически нельзя меньше 6)...

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

[daniel starodubtsev]

Для 7! меньше чем двенадцатью действительно не обойтись. Можно $7^1 + 7^1 + 7^1 + 7^1 + 7^1 + 7^1 + 7^2 + 7^2 + 7^2 + 7^2 + 7^4 + 7^4$

[daniel starodubtsev]

Вряд ли существует универсальный алгоритм выражения факториала как сумму степеней, поскольку тогда можно было бы (с использованием алгоритма возведения в степень по модулю) вычислить факториал по модулю, а мне совсем недавно объяснили, что это вряд ли возможно эффективно сделать

[Ktina]

daniel starodubtsev в сообщении #1364546 писал(а):

... а мне совсем недавно объяснили, ...

Если не секрет, расскажите поподробнее, можно в личку.

[kotenok gav]

Ktina в сообщении #1364634 писал(а):

Если не секрет, расскажите поподробнее, можно в личку.

topic131978.html