2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 02:13 


13/02/17

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


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

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 02:43 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Ну вот пример: $(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$ :-) Да и первоначальное делимое в общую тетрадь не поместится.
Хотя это не принципиально, конечно.

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 03:01 


13/02/17

317
Varanasi
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 нуля мы уже получили, использовав при этом все пятерки, почему еще раз можно их использовать? Я понимаю, что формула верная, но не пойму, что значит "Дадут нам ещё по одной пятерке".

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 04:16 


13/02/17

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

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

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 04:35 
Аватара пользователя


21/09/12

1871
Aether в сообщении #1196978 писал(а):
Откуда оно берется

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

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 06:40 
Аватара пользователя


29/04/13
7130
Богородский
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$$

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 13:35 


13/02/17

317
Varanasi
$(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!)!$ не может быть квадратом.

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

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 13:38 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Aether в сообщении #1197036 писал(а):
Не уверен, что ошибок нет.
В слове "неудасться" две ошибки.

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 13:45 


13/02/17

317
Varanasi
grizzly в сообщении #1197038 писал(а):
В слове "неудасться" две ошибки.


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

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

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 13:50 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Aether в сообщении #1197041 писал(а):
Но Вы всё-таки проверьте на всякий случай на ошибочность рассуждений и решение.
А чего там проверять? Возьмите $n=4$ и сами проверяйте -- проще простого.

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 13:55 
Аватара пользователя


21/09/12

1871
Aether в сообщении #1197036 писал(а):
домножим это произведение на $5^k$, разложив степень 5-ки в произведение

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

Почему?

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 14:00 


13/02/17

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


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

-- 04.03.2017, 15:02 --

atlakatl в сообщении #1197045 писал(а):
Это как? Оно уже разложено на k пятёрок.


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

-- 04.03.2017, 15:17 --

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

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 15:22 


13/02/17

317
Varanasi
Представим $(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!)!$.

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 16:40 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: На сколько нулей оканчивается (n!)!?
Сообщение04.03.2017, 16:53 


13/02/17

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group