Числа с заданным числом делителей как суммы факториалов

[gipokrat]

Обозначим через $d(n)$ количество положительных делителей натурального числа $n$.

Для натурального числа $k \ge 1$ рассмотрим множество чисел, представимых в виде суммы $k$ факториалов:
$n = a_1! + a_2! + \dots + a_k!,$
где все $a_i$ натуральные.

Случай $k = 1$ тривиален: $1! = 1$, и $d(1) = 1$.

Вопрос 1.
Верно ли, что для каждого натурального $k \ge 1$ существует число $n$, представимое в виде суммы $k$ факториалов, такое что
$d(n) = k$?

Иными словами, существует ли для каждого $k \ge 1$ натуральное число с ровно $k$ положительными делителями, которое можно записать в виде суммы ровно $k$ факториалов?

Для малых значений $k$ такие примеры найдены. Например:
$k = 2:\quad 1! + 1! = 2,\ d(2) = 2;$
$k = 3:\quad 1! + 1! + 2! = 4,\ d(4) = 3;$
$k = 4:\quad 2! + 2! + 2! + 2! = 8,\ d(8) = 4;$
$k = 5:\quad 3! + 3! + 2! + 1! + 1! = 16,\ d(16) = 5;$
$k = 6:\quad 3! + 2! + 1! + 1! + 1! + 1! = 12,\ d(12) = 6;$
$k = 7:\quad 4! + 4! + 3! + 3! + 2! + 1! + 1! = 64,\ d(64) = 7.$

Вопрос 2 (уточнение).
Если ответ на вопрос 1 положителен, можно ли получить оценки на минимальное такое число $n = n(k)$ (по росту $n(k)$ в зависимости от $k$)?

[lel0lel]

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

gipokrat в сообщении #1709655 писал(а):

$k = 5:\quad 3! + 3! + 2! + 1! + 1! = 16,\ d(16) = 5;$

получаем
$2^5=3!+3!+3!+3!+2!+2!+1!+1!+1!+1!$ тут есть простор для сворачивания/разворачивания. Например, $2^5=5\cdot 3!+2!=4!+3\cdot 2!+2\cdot 1!$

Только это не к вопросу о наименьших числах, имеющих представление в виде суммы.

[gris]

попробовал найти первые наименьшие примитивным перебором. Думаю, что табличка понятна без лишних символов

 1       1 [1]
 2       2 [1,1]
 3       4 [1,1,2]
 4       6 [1,1,2,2]
 5      16 [1,1,2,3,3]
 6      12 [1,1,1,1,2,3]
 7      64 [1,1,2,3,3,4,4]
 8      24 [1,1,1,1,2,3,3,3]
 9      36 [1,1,1,1,2,2,2,2,4]
10     48 [1,1,1,1,1,1,3,3,3,4]
11   1024 [1,1,1,1,3,3,4,4,5,5,6]
12     60 [1,1,1,1,1,1,1,1,2,2,4,4]
13   4096 [2,2,3,3,5,5,5,5,6,6,6,6,6]
14    192 [1,1,1,1,1,1,2,2,2,3,3,4,4,5]
15    144 [1,1,1,1,1,1,1,1,1,1,1,1,3,3,5]
16    120 [1,1,1,1,1,1,1,1,2,2,3,3,4,4,4,4]
17  65536 [1,1,1,1,1,1,1,1,1,1,3,7,7,7,7,7,8]
18    180 [1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,4,5]
19 262144 [1,1,2,2,2,2,3,4,4,7,7,7,7,8,8,8,8,8,8]
20    240 [1,1,1,1,1,1,1,1,1,1,2,2,2,2,3,4,4,4,4,5]
21    576 [1,1,1,1,1,1,1,1,1,1,1,1,3,3,4,4,4,5,5,5,5]
22   3072 [1,1,1,1,1,1,1,1,1,1,2,2,2,2,3,4,4,5,6,6,6,6]
23 4194304 [1,1,1,1,1,1,1,1,1,1,3,4,4,5,5,6,8,8,8,8,8,9,10]
24    360 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,5,5]

Интересно, что степени двойки появляются на простых суммах. Можно это свойство использовать для проверки на простоту
Впрочем, некоторые другие закономерности прослеживаются и можно начать теоретизировать.

[mihaild]

gris в сообщении #1709671 писал(а):

Интересно, что степени двойки появляются на простых суммах

Потому что число с простым количеством делителей - обязательно степень простого. Ну и раз степень двойки получить можно, то она и будет ответом для простых $k$.
Мне правда не очевидно, что всегда можно будет получить степень двойки.

[lel0lel]

Уже ответили, поэтому убрал в

(Оффтоп)

gris в сообщении #1709671 писал(а):

Интересно, что степени двойки появляются на простых суммах.

Формула количества делителей числа такова, что простым числом $p$ это количество может быть только для степеней простых $q^{p-1}$. Если, например, $n=p_1^{a_1}p_2^{a_2}$, то количество делителей уже составное $(a_1+1)(a_2+1)$. Среди степеней с заданным показателем, наименьшими являются степени двойки.

-- Вт ноя 18, 2025 15:05:49 --

Надо бы вообще посмотреть на наименьшие числа с заданным количеством делителей, не совпадают ли они с численным расчётом gris. Но у меня OEIS перестал работать ещё в начале лета.

-- Вт ноя 18, 2025 15:13:35 --

Вот встроенный в гугл ИИ выдаёт начало последовательности

1, 2, 4, 6, 16, 12, 64, 24, 36, 48, 1024, 60, 4096, 192, 144, 120, 65536, 180, 262144, 240

A005179

[gris]

Интересно, что есть факториальная система счисления, но там цифра не больше своего порядкового номера, а здешняя форма записи даже в виде упорядоченного вектора фиксированного количества факториалов не годится из-за неоднозначности: k=6 s=12 =[1,1,1,1,2,3] = [2,2,2,2,2,2].
Для каждого k есть большое число самых разнообразных решений, красивых типа k=6 s= 873 = [1,2,3,4,5,6]. А вот минимальное всегда чётное. Но посчитать хотя бы до миллиона
Насчёт степени двойки. Конечно, это минимальное решение, но всякую ли к-тую степень двойки можно представить в виде суммы к+1 факториала? Если бы вывести представление...
В общем, есть над чем подумать

+++ то же касается энциклопедической последовательности. Там нет одного пожелания: чтобы k-тый член последовательности был представим в виде суммы k факториалов. Например, обычные числа 25 и 43 нельзя представить суммой 6-ти факториалов. Конкретно они не имеют шести делителей, но ощущение недоказанности есть...
+++ А кажется и нашли контрпример для k=29.

[Dmitriy40]

gris в сообщении #1709671 писал(а):

Интересно, что степени двойки появляются на простых суммах. Можно это свойство использовать для проверки на простоту

mihaild в сообщении #1709709 писал(а):

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

По моему уже $k=29 : 2^{28}$ в сумму 29 факториалов не раскладывается.

-- 18.11.2025, 18:27 --

gris в сообщении #1709713 писал(а):

Насчёт степени двойки. Конечно, это минимальное решение, но всякую ли к-тую степень двойки можно представить в виде суммы к+1 факториала?

Уже $2^{26}$ у меня не получилось представить суммой 27 факториалов.

-- 18.11.2025, 18:49 --

При этом $2^5$ представимо двумя способами,
$2^{7}$ двумя,
$2^{9}$ двумя,
$2^{10}$ двумя,
$2^{13}$ тремя,
$2^{16}$ четырьмя,
$2^{17}$ шестью,
$2^{18}$ двумя,
$2^{19}$ семью,
$2^{20}$ тремя,
$2^{21}$ двумя,
$2^{22}$ десятью,
$2^{23}$ восемью способами.

[lel0lel]

Dmitriy40 в сообщении #1709720 писал(а):

Уже $2^{26}$ у меня не получилось представить суммой 27 факториалов.

Да, всё верно. Факториалы растут слишком быстро, поэтому, максимальный факториал, который может быть использован в разложении, должен удовлетворять условию $m!<2^{k-1}$. Степени двойки становятся всё больше, а вот доступных в разложении факториалов, становится хоть и больше, но прирост очень медленный.

[Dmitriy40]

Но $2^{29}, 2^{33}$ ещё вполне представимы как суммы правильного количества факториалов. Остальные же начиная с $2^{26}$ похоже что нет.

[lel0lel]

Dmitriy40 в сообщении #1709738 писал(а):

Но $2^{29}, 2^{33}$ ещё вполне представимы как суммы правильного количества факториалов. Остальные же похоже что нет.

Это может, с ростом степени появляются новые "доступные факториалы", да и само число меняется -- может повезти и разложиться на малых доступных факториалах.
$2^{24}=2\cdot 2! + 2 \cdot 3! + 4 \cdot 5! + 5 \cdot6! + 2 \cdot 8! + 6 \cdot 9! + 4 \cdot 10!$

[mihaild]

lel0lel в сообщении #1709735 писал(а):

Факториалы растут слишком быстро, поэтому, максимальный факториал, который может быть использован в разложении, должен удовлетворять условию $m!<2^{k-1}$.

Это условие должно быть выполнено независимо от скорости роста факториалов :)
И просто скорости роста для вывода недостаточно - между $\frac{2^{k - 1}}{k}$ и $2^{k - 1}$ факториал найдется.

[lel0lel]

mihaild в сообщении #1709741 писал(а):

Это условие должно быть выполнено независимо от скорости роста факториалов :)

Да, набрал лишнее "поэтому" в сообщении. Хотел сказать, что база "допустимых факториалов" наполняется не слишком быстро по мере роста степеней двойки. Из этого, конечно, каких-то выводов и тем более доказательств не следует.

lel0lel в сообщении #1709735 писал(а):

Да, всё верно.

Это "всё верно" относилось к тому, что я проверил и тоже не нашёл разложения $2^{28}$ в $29$ факториалов, а также $2^{26}$ в $27$ факториалов.

[Dmitriy40]

Что-то с $k=29$ вообще засада, не могу найти решение ни для какого простого $p<10^7$, чтобы $p^{28}$ разложилось в сумму 29 факториалов. Может его и вообще нет, решения то?

Другие простые основания до 100 и степени до 100:

x=3^1: [1, 1], k=2
x=3^2: [1, 1, 1], k=3
x=3^3: [1, 0, 0, 3], k=4
x=3^6: [1, 0, 0, 0, 3, 3], k=7
x=3^8: [1, 2, 0, 3, 1, 1, 1], k=9
x=3^11: [4, 3, 1, 0, 1, 0, 0, 3], k=12
x=3^14: [1, 3, 1, 5, 0, 0, 0, 0, 4, 1], k=15
x=5^3: [1, 0, 0, 2, 1], k=4
x=7^1: [1, 0, 1], k=2
x=7^2: [2, 0, 0, 1], k=3
x=29^2: [1, 1, 0, 0, 0, 1], k=3

В массиве - коэффициенты при факториалах (старшие слева).

[mihaild]

Никакие степени двойки в интервале $[34, 1000]$ не раскладываются. И никакие простые до 20000 решения для $k=29$ не дают.

[lel0lel]

Пока дома тихо, подумал над задачей.
Нужно рассматривать минимальную для заданного числа сумму факториалов. Это разложение по "факториальной" системе счисления. Для данного $n$ старший факториал $m!$ удовлетворяет неравенству $m!\leq n$, решая его находим максимальное целое $m$. Дальше понятно -- отнимаем остаток, делим на сам факториал, ну и повторяем снова с остатком покуда не придём к нулю. Примерно так:

 n = 2^28; ans = {}; x = 0; Do[
 m = Last[Last[Reduce[k! <= n, k, Integers]]]; r = Mod[n, m!]; 
 x = (n - r)/m!; AppendTo[ans, {x, m}]; n = r; If[n == 0, Return[ans]]
 , {i, 1, Ceiling[Log[n]]}]

Out[4]= {{6, 11}, {7, 10}, {9, 9}, {6, 8}, {5, 7}, {2, 3}, {2, 2}}

Минимальное по длине разложение хорошо тем, что оно минимальное по длине. Разменивая большие факториалы на меньшие, их число возрастает. Как видно из примера, минимальное разложение $2^{28}$ имеет $6+7+9+6+5+2+2=37$ факториалов, что больше требуемых $29.$
А вот для $2^{24}$ минимальное разложение

{{4, 10}, {6, 9}, {2, 8}, {5, 6}, {4, 5}, {2, 3}, {2, 2}}

как раз содержит ровно $25$ факториалов.
Понятно, что чтобы существовало разложение в сумму $k$ факториалов, необходимо чтобы минимальное разложение было либо такой же длины, либо меньше.

Dmitriy40 в сообщении #1709738 писал(а):

Но $2^{29}, 2^{33}$ ещё вполне представимы как суммы правильного количества факториалов.

Минимальное для $2^{29}$ имеет $24$ факториала, что менее $30$ факториалов:

{{1, 12}, {1, 11}, {4, 10}, {9, 9}, {4, 8}, {2, 7}, {1, 4}, {1, 3}, {1, 2}}

Минимальное для $2^{33}$ содержит $31$ факториал:

{{1, 13}, {4, 12}, {11, 11}, {2, 10}, {1, 9}, {5, 8}, {4, 5}, {1, 4}, {1, 3}, {1, 2}}