На сколько нулей оканчивается (n!)!?

[Aether]

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

Я там примерчики привёл. Удобно программируется. Для строгого вывода формулы у меня не хватит терпения и внимательности. Специалисты же в теории чисел наверняка знают какие-то более общие теоремы. В OEIS я видел нечто похожее, но со степенями двойки (то есть завершающие нули в двоичной записи), Там какие-то спецфункции приводятся. Увы мне
Да, Вы правы. Надо делить $(n!)!$ до упора. Но это то же самое.

Для меня важно понять почему это то же самое.

[gris]

Ну вот пример: $(8!)! =(40320)! =1\cdot 2\cdot 3\cdot 4\cdot5\cdot6...\cdot40319\cdot40320$.
Числа, кратные $5:\,5,10,15,20,...40320$ дадут (пока) по одной пятёрочке в разложение. Их $40320:5=8064$ штуки. Среди них $[8064:5]=1612$ чисел, которые делятся на $25$ и дадут нам по ещё одной пятёрке. Среди них $[1612:5]=322$ числа, которые делятся на $125$ и дадут нам по ещё одной пятёрке. Среди них $[322:5]=64$ числа, которые делятся на $625$ и дадут нам по ещё одной пятёрке. Среди них $[64:5]=12$ чисел, которые делятся на $5^5$ и дадут нам по ещё одной пятёрке. Среди них $[12:5]=2$ числа, которые делятся на $5^6$ и дадут нам по ещё одной пятёрке. А $5^7$ уже больше $8!$ и не даст нам больше пятёрок.
Итак, $8064+1612+322+64+12+2=10076$ и есть количество хвостовых нулей у $(8!)!$. Попробуйте на бумажке столько раз разделить на $5$ Да и первоначальное делимое в общую тетрадь не поместится.
Хотя это не принципиально, конечно.

[Aether]

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

Их $40320:2=8064$

$40320:5=8064$

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

Среди них $[8064:5]=1612$ чисел, которые делятся на $25$ и дадут нам по ещё одной пятёрке. Среди них $[1612:5]=322$ числа, которые делятся на $125$ и дадут нам по ещё одной пятёрке. Среди них $[322:5]=64$ числа, которые делятся на $625$ и дадут нам по ещё одной пятёрке. Среди них $[64:5]=12$ чисел, которые делятся на $5^5$ и дадут нам по ещё одной пятёрке. Среди них $[12:5]=2$ числа, которые делятся на $5^6$ и дадут нам по ещё одной пятёрке.

Спасибо.

Вот это дадут еще по одной пятерке непонятно, ведь делением $40320:5=8064$ мы уже определили все пятерки, непонятно, почему мы должны брать среди них кратные степеням пятерки. 8064 нуля мы уже получили, использовав при этом все пятерки, почему еще раз можно их использовать? Я понимаю, что формула верная, но не пойму, что значит "Дадут нам ещё по одной пятерке".

[Aether]

Именно для $n!$, умножая его на каждое из чисел < n! и кратное 25 мы получим 2 нуля. На каждое из чисел, кратное 125 - 3 нуля, на каждое из чисел кратное $5^k$ - k нулей. Если бы мы брали факториал не от факториала, то это свойство не выполнялось бы. Непонятно, почему оно выполняется для факториалов.

Возьмем 40320 и умножим на 25, получим 1008000, очевидно, что к исходному числу добавилось 2 нуля, в то время как если взять число 40420 и умножить на 25, получим 1010500, здесь видим прибавление лишь одного нуля. Т.е. любое число, являющееся факториалом, при умножении на кратное 25 дает 2 нуля, при умножении на 125- 3 нуля, при умножении на $5^k$ -$ k $нулей - это свойство факториалов. Откуда оно берется - непонятно. Для чисел не являющихся факториалами, оно может как выполняться так и не выполняться. Для чисел являющихся факториалами- выполняется всегда.

[atlakatl]

Aether в сообщении #1196978 писал(а):

Откуда оно берется

В факториале на каждую пятёрку приходится аж $2, 4, 6, 8$ - 4 числа, дающих в произведении ноль.
Для произвольных "нефакториалов" это происходит не всегда.
Дальше сложнее. Для "нейтрализации" 25 нужно уже 2 чётных числа. Для 625 их ещё хватает. А для 3125 и больше приходится занимать у младших собратьев. Но чётных множителей в факториале всегда будет достаточно.

[Yadryara]

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

Конечно, "целая часть" не удобна для анализа,

ПМСМ, "целую часть", то есть "пол" лучше обозначать только нижними засечками: $\lfloor {\,}\rfloor$ , а не $[\,]$.

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

$N((n!)!)=\sum[n!/5^k]$

То бишь более подробно:

$$N((n!)!)=\sum_{k=1}^{\lfloor \log_5{n!}\rfloor}\lfloor {n!/5^k}\rfloor$$

[Aether]

$(n!)!$ можно представить в виде :$(n!)^2\cdot\prod\limits_{k=n+1}^{n!}k$

рассмотрим произведение:$\prod\limits_{k=n+1}^{n!}k$, факторизуем в этом произведении все числа и сгруппируем затем попарно так, чтобы произведение пар представляло собой квадраты. Простые числа > $\sqrt{n!}$ не будут иметь пар, простые числа <$\sqrt{n!}$ могут также не иметь пар, если их количество в разложении нечетное. Исключим все пары(квадраты) из этого разложения и рассмотрим получившееся произведение. Оно будет состоять только из простых чисел, представленных в единственном экземпляре. Очевидно, что невозможно сгруппировать попарно сомножители так, чтобы они представляли собой квадраты, из чего можно заключить, что $(n!)!$ непредставимо в виде квадрата. Теперь домножим это произведение на $5^k$, разложив степень 5-ки в произведение. Какое бы k мы не взяли, не удастся сгруппировать члены произведения попарно так, чтобы все пары были квадратами. Соответственно, количество нулей возникающих в хвосте $(n!)!$ не может быть квадратом.

Не уверен, что ошибок нет.

[grizzly]

Aether в сообщении #1197036 писал(а):

Не уверен, что ошибок нет.

В слове "неудасться" две ошибки.

[Aether]

grizzly в сообщении #1197038 писал(а):

В слове "неудасться" две ошибки.

Спасибо -поправил. Был поглощен решением настолько, что забыл про такие элементарные вещи как "не с глаголами" и "что сделает?".

Но Вы всё-таки проверьте на всякий случай на ошибочность рассуждений и решение.

[grizzly]

Aether в сообщении #1197041 писал(а):

Но Вы всё-таки проверьте на всякий случай на ошибочность рассуждений и решение.

А чего там проверять? Возьмите $n=4$ и сами проверяйте -- проще простого.

[atlakatl]

Aether в сообщении #1197036 писал(а):

домножим это произведение на $5^k$, разложив степень 5-ки в произведение

Это как? Оно уже разложено на k пятёрок.
Да и зачем? Мы уже выяснили, что в оставшемся произведении не больше одной пятёрки.

Aether в сообщении #1197036 писал(а):

Соответственно

Почему?

[Aether]

Aether в сообщении #1197036 писал(а):

Соответственно, количество нулей возникающих в хвосте $(n!)!$ не может быть квадратом.

Вывод неверный.

-- 04.03.2017, 15:02 --

atlakatl в сообщении #1197045 писал(а):

Это как? Оно уже разложено на k пятёрок.

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

-- 04.03.2017, 15:17 --

Необходимо доказать, что количество пятерок в таком разложении не будет равно $m^2$. А я вроде доказал, что каким бы ни было количество 5 в таком разложении и на какое количество 5 его ни умножай, сам $(n!)!$ никогда не будет квадратом, аналогично кубом и любой другой степенью натурального числа.

[Aether]

Представим $(n!)!$ как произведение: $1\cdot2\cdot3\cdot4\cdot5\cdot.....\cdot n!$. Количество пятерок(степень пятерки) в факторизации этого произведения - есть искомая величина. Определим среди сомножителей данного произведения количество всех чисел, кратных 5-ти: $\frac{n!}{5}$. Каждое из них даст в факторизации как минимум одну 5-ку, но числа кратные $5^2$ дадут 2 пятерки в факторизации, но так как одну их пятерку мы уже учли, то останется учесть еще по одной пятерке от каждого такого числа и их общее количество будет: $\frac{n!}{5^2}$, но среди кратных 5-ти и $5^2$, могут быть и числа кратные более высоким степеням, каждое такое число, будет давать дополнительную 5-ку в факторизации, после того как учтены его кратности низших степеней. Таким образом общее количество 5 в факторизации членов произведения равно:

$$N((n!)!)=\sum_{k=1}^{\lfloor \log_5{n!}\rfloor}\lfloor {n!/5^k}\rfloor$$

Наконец-таки понял, что эта формула и свойство $(n!)!$ берутся из рассмотрения факторизации числа $(n!)!$.

[gris]

Засада в том, что $n!/4$ это недостижимая верхняя граница для $N((n!)!)$. Из того, что $n!/4$ не может быть квадратом, вовсе не следует, что $N$ не квадрат. Вот пример:
$N((20!)!)=608225502044159990$, а $20!/4=608225502044160000$, что больше всего на $10$. Относительная ошибка аппроксимации $10^{-17}$. Но вдруг какой-нибудь квадрат или степень подберётся так близко? В данном случае, до ближайшего меньшего квадрата почти полмиллиарда
И чем дальше, тем расстояние от факториала до ближайшей степени неумолимо увеличивается.

[Aether]

Да, я понимаю, что это ещё далеко не доказательство.