Вопрос по ТЧ

[maxmatem]

Итак пусть $k,n$-натуральное.

Допустим, что

$$k! =2^{\alpha_{1}}p_2^{\alpha_{2}}p_3^{\alpha_{3}}p_4^{\alpha_{4}}\cdots p_n^{\alpha_{n}} $$

Можно ли зная $\alpha_{1}$ и при том что другие $p_i^{\alpha_{i}}$ ,где $i\geq 2$ нам неизвестны, определить $k$ однозначно ?

Поработав руками я все таки думаю да можно, но это получалось для конкретных примеров типа $\alpha_{1}=7$

Интересно существует ли алгоритм восстановления $k$ ?

[lel0lel]

maxmatem в сообщении #1538684 писал(а):

Можно ли зная $\alpha_{1}$ и при том что другие $p_i^{\alpha_{i}}$ ,где $i\geq 2$ нам неизвестны, определить $k$ однозначно ?

Однозначно нельзя, так как $100!$ и $101!$ имеют одинаковое $\alpha_1$. А вот определить два варианта можно достаточно просто.

[maxmatem]

Цитата:

А вот определить два варианта можно достаточно просто.

и как если не секрет?

[lel0lel]

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

[nnosipov]

Имеют место неравенства $k-\log_2{(k+1) \leqslant \alpha_1 \leqslant k-1$, откуда для данного $\alpha_1$ можно найти возможные значения $k$.

[lel0lel]

Начал считать, а оказалось, что уже посчитано до нас A011371

[maxmatem]

спасибо вопрос снят

-- Чт ноя 11, 2021 20:36:14 --

nnosipov


кстати откуда они взялись ? это стандартные факты? если да то где можно о них почитать?

[nnosipov]

maxmatem в сообщении #1538697 писал(а):

это стандартные факты?

Да, вытекают из формулы (Лежандра, кажется) для показателя $\alpha$, с которым простое $p$ входит в каноническое разложение $n!$:

$$\alpha=\frac{n-s_p(n)}{p-1},$$

где $s_p(n)$ --- сумма цифр числа $n$ в системе счисления с основанием $p$.

[maxmatem]

nnosipov
спасибо