произведение сумм своих простых делителей

[maxal]

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

Пример:

$$150 = 2\cdot 3\cdot 5^2 = (2+3+5+5)\cdot(2+3+5)$$

[ИСН]

Красота какая. Нетривиальных - только 16 и 27 ещё, что ли? Хм. Почему...

[provincialka]

Ну, ясно, что левая часть растет гораздо быстрее, чем правая. Так что нужно рассмотреть только малые степени. Но вот где граница этой "малости"?

[ИСН]

Малые степени - довольно многочисленный народец; левая часть меньше правой у любого числа вида $pq$, и даже $2pq$ и $4pq$, и вообще у тупо любого числа, домноженного на достаточно большое простое. Граница тут хитрая.
Сама по себе делимость как на такую, так и на другую сумму простых - штука довольно частая. Попадаются числа, у которых левая часть больше правой ровно в два или в три раза. Они тоже образуют маленькое и разнородное семейство.

[maxal]

Предлагаю начать с доказательства того, что количество простых делителей с учётом кратности у такого числа не превышает 10.

[provincialka]

Я пока пытаюсь разобрать случаи небольшого числа простых делителей. Случай одного делителя разобран выше. Два делителя быть не могут (их сумма взаимно проста с ними). Для трех делителей я показала, что степень большего не может быть больше 2.

Вообще большое подозрение, что не может быть двух простых делителей в степени, большей 1. То есть все делители в первой степени, и разве что один - в квадрате. Но как это доказать? Неужели только перебором (при условии, что всех делителей менее 10)?

[maxal]

ИСН в сообщении #718182 писал(а):

Красота какая. Нетривиальных - только 16 и 27 ещё, что ли? Хм. Почему...

Приоткрою еще немного карты: я доказал, что кроме указанных трёх решений ещё только могут быть решения вида $2\cdot 3^2\cdot p\cdot q$, где $q>p>3$ -- простые, удовлетворяющие уравнению Пелля:

$$(7\cdot (p+q)-13)^2 -63\cdot (p-q)^2 = 729.$$

Например, пара $(p,q)=(209,3317)$ удовлетворяет этому уравнению, и поэтому мы имеем:

$$2\cdot 3^2\cdot 209\cdot 3317 = (2+3+209+3317)\cdot (2+3+3+209+3317)$$

Только вот, к сожалению, $209$ и $3317$ не являются простыми.

Как доказать, что таких простых пар $(p,q)$ не существует, я не знаю (вполне возможно, что задача по сложности сродни задаче о простых в последовательности чисел Фибоначчи).

Как бы там ни было, предлагаю передоказать этот результат (ну или усилить)...

[EtCetera]

В случае $2\cdot 3^2\cdot p\cdot q$ сумма делителей должна равняться $3^2\cdot p$ ($3q$ будет слишком большой, а $3p$ оставляет слишком много сумме с учетом кратности). Но тогда сумма с учетом кратности равна $2q$, что все равно слишком много, поскольку $p=\frac{q+5}{8}$ (а нужно закрыть "брешь" шириной $q-8$).
Мне кажется, что четырех различных простых делителей у искомых чисел вообще быть не может.

(Нестрогие соображения на этот счет)

Четыре делителя не могут быть все нечетными. Значит, среди них есть двойка, поэтому сумма делителей нечетна и равна произведению двух средних делителей (произведению второго по величине делителя и наибольшего она быть уже не может; средние делители не могут иметь степени, большие 1). Но тогда сумма делителей с учетом кратности должна быть равна произведению 2 и наибольшего делителя, что не проходит по соображениям четности.

[maxal]

EtCetera в сообщении #719259 писал(а):

В случае $2\cdot 3^2\cdot p\cdot q$ сумма делителей должна равняться $3^2\cdot p$ ($3q$ будет слишком большой, а $3p$ оставляет слишком много сумме с учетом кратности). Но тогда сумма с учетом кратности равна $2q$, что все равно слишком много, поскольку $p=\frac{q+5}{8}$ (а нужно закрыть "брешь" шириной $q-8$).

Хороший аргумент. Его его аккуратно формализовать, то можно получить полное доказательство.

EtCetera в сообщении #719259 писал(а):

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

Это верно, так как выполняется для чисел 16, 27, 150. ;)

Предлагаю-таки дать полное доказательство - все основные идеи уже озвучены.

[TOTAL]

$2\cdot 3^2\cdot p\cdot q=(5+p+q)(8+p+q)$
Либо $5+p$ делится на $q,$ либо $8+p$ делится на $q,$ поэтому $q=p+8,$ поэтому
$2\cdot 3^2\cdot p\cdot q=(13+2p) \cdot 2 \cdot q$, поэтому $13+2p=9p$

[maxal]

Ладно, давайте закроем тему.

Пусть $m=p_1^{k_1} \cdots p_n^{k_n}$ - искомое, где $p_1 < \dots < p_n$ - простые, $k_i\geq 1$.

Если $n=1$, то имеем уравнение $m=p^k = kp^2$, откуда $m=2^4$ или $3^3$.

Пусть $n\geq 2$. Обозначим:
$K=k_1+\dots+k_n$,
$s_j = p_1 + \dots + p_j$,
$S_j = k_1\cdot p_1 + \dots + k_j\cdot p_j$.
Тогда

$$0\equiv m = s_n \cdot S_n \equiv s_{n-1}\cdot S_{n-1} \pmod{p_n},$$

что в виду простоты $p_n$ влечет $p_n \leq S_{n-1}$.

Рассмотрим два случая:

1) $k_n=1$. В этом случае имеем $s_n \leq S_n = S_{n-1} + p_n \leq 2\cdot S_{n-1}$. Откуда

$$m = s_n \cdot S_n \leq 4 S_{n-1}^2 \leq 4 (K-1)^2 p_{n-1}^2$$

и поэтому:

$$m' = \tfrac{m}{p_{n-1}p_n} \leq 4(K-1)^2 \frac{p_{n-1}}{p_n} < 4(K-1)^2,$$

причём $m'$ - целое число.
С другой стороны, количество простых делителей у $m'$ с учётом кратности равно $K-2$ и поэтому $m' \geq 2^{K-2}$. Откуда $2^{K-2} < 4(K-1)^2$, что влечёт $K\leq 10$ и $m' < 4(10 - 1)^2 = 324$.

Нетрудно перебрать все такие $m'$, положить $m=m'\cdot p\cdot q$ для простых $p<q$ и "обработать" его по методу, указанному EtCetera и TOTAL.

2) $k_n > 1$. В этом случае $m = s_n\cdot S_n \leq S_n^2 \leq (K\cdot p_n)^2$. Тогда

$$m' = \frac{m}{p_n^2} \leq K^2,$$

причём $m'$ - целое число.
С другой стороны, $m' \geq 2^{K-2}$ и поэтому $2^{K-2} \leq K^2$, откуда $K\leq 8$ и $m'\leq 64$.

Нетрудно перебрать все такие $m'$, положить $m=m'\cdot p^2$ и составить и решить квадратное уравнение относительно $p$ (которое должно быть простым, большим простых делителей $m'$). Или, альтернативно, можно просто перебрать все простые $p$ делящий произведение сумм простых делителей $m'$ с учётом и без учёта кратности.

Так и получается, что 16, 27 и 150 - единственные решения.

[maxal]

maxal в сообщении #719641 писал(а):

Нетрудно перебрать все такие $m'$, положить $m=m'\cdot p\cdot q$ для простых $p<q$ и "обработать" его по методу, указанному EtCetera и TOTAL.

Приведу детали в общем виде.

Если $p$ делит $m'$ (т.е. $k_{n-1}>1$), то все такие $p$ легко находятся, а $q$ обязано делить произведение сумм простых делителей числа $m\cdot p$ без учёта и с учётом кратности.

Если $p$ не делит $m'$ (т.е. $k_{n-1} = 1$), то обозначим через $s$ и $S$ суммы простых делителей числа $m'$ без учёта и с учётом кратности соответственно. Тогда $q$ делит произведение $(s+p)\cdot (S+p)$. Возможны два случая:

1) $q = s+p$ или $q = S+p$. В этих случаях $p$ обязано делить число $2sS(s+S)$.

2) $q$ - собственный делитель $S+p$ или $s+p$. В этом случае $p<q\leq \tfrac{S+p}{2}$, то есть $p\leq S$. И снова $q$ обязано делить произведение сумм простых делителей числа $m\cdot p$ без учёта и с учётом кратности.

Таким образом, задача сводится к конечному перебору.

P.S. См. также A073396