Количество троек в 540!

[maxmatem]

Добрый день.

Сколько троек содержится в числе $540!$.

Как решать задачу по взрослому, я понимаю.
Теорема


Пусть $n$ натуральное и $p$ простое, тогда $n!$ делится на $p^q$,где $q=\sum\limits_{i=1}^{n}\left \lceil{\frac{n}{q^i}}\right \rceil $ и $n$ не делится на $p^{q+1}$

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

Может кто подскажет более простой способ... может комбинаторный.

[mihiv]

В формуле для $q$ ошибка, должно быть: $q=\sum \limits_{i=1}\lfloor {\frac {n}{p^i}}\rfloor $.

[dgwuqtj]

А чем "взрослый" способ не устраивает? Будет всего 5 слагаемых.

[wrest]

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

Пусть $n$ натуральное и $p$ простое, тогда $n!$ делится на $p^q$,где $q=\sum\limits_{i=1}^{n}\left \lceil{\frac{n}{q^i}}\right \rceil $ и $n$ не делится на $p^{q+1}$

Там сумма не до $n$ а до $\lfloor \log _p (n) \rfloor$ и в случае $n=540$ слагаемых всего $5$
Ну и слагаемые округляем до целого вниз, а не вверх.
Текст на Pari/gp
? pfact(n,p)=my(max=floor(log(n)/log(p)),s=0);for(i=1,max,s=s+n\(p^i));return(s);
? pfact(540,3)
%2 = 268
Количество троек (степень вхождения тройки в разложение на простые множители) в числе $(10^9)!$ считается за ноль времени:
? pfact(10^9,3)
%3 = 499999993
? ##
*** last result computed in 0 ms.
?

[maxmatem]

mihiv
да да спс опечатка...

-- Вс апр 27, 2025 13:43:41 --

wrest
я когда вручную считал, по формуле просто доходил до момента когда целая часть равно нулю.... и да я имел в виду просто целая часть а написал как верхнее округление ....

-- Вс апр 27, 2025 13:44:56 --

Цитата:

Текст на Pari/gp
? pfact(n,p)=my(max=floor(log(n)/log(p)),s=0);for(i=1,max,s=s+n\(p^i));return(s);
? pfact(540,3)
%2 = 268
Количество троек (степень вхождения тройки в разложение на простые множители) в числе $(10^9)!$ считается за ноль времени:
? pfact(10^9,3)
%3 = 499999993
? ##
*** last result computed in 0 ms.
?

я в программировании слаб.....


Ответ у меня получился 268 троек

[wrest]

То есть

mihiv в сообщении #1683918 писал(а):

должно быть: $q=\sum \limits_{i=1}\lfloor {\frac {n}{p^i}}\rfloor $.

В итоге правильная формула:

$$q=\sum \limits_{i=1}^{\lfloor \log _p (n)\rfloor}\left \lfloor {\frac {n}{p^i}}\right \rfloor $$

-- 27.04.2025, 12:50 --

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

Ответ у меня получился 268 троек

Ну ответ правильный. Только доходить (чтобы не вычислять логарифм) до момента когда целая часть равна нулю - не обязательно т.к. этот момент известен заранее.
Ну и если хотите доходить, то вместо проверки целой части на ноль быстрее проверять что числитель стал меньше знаменателя, делить уже не надо.
Тогда формула

$$q=\sum \limits_{i=1}^{p^i \le n}\left \lfloor {\frac {n}{p^i}}\right \rfloor $$

И код
pfact(n,p)=my(i=1,s=0,pi=p);while(pi<=n,s=s+n\(p^i);i++;pi=p^i);return(s)

[maxmatem]

wrest

Цитата:

В итоге правильная формула:

$$q=\sum \limits_{i=1}^{\lfloor \log _p (n)\rfloor}\left \lfloor {\frac {n}{p^i}}\right \rfloor $$

спасибо что поправили .

так интересно можно ли простыми школьными методами?

[wrest]

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

так интересно можно ли простыми школьными методами?

Для какого класса школы?
Ну логарифм я убрал там, осталась только целочисленная арифметика.

[maxmatem]

wrest
8 класс )))

[wrest]

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

8 класс )))

Ну не знаю... Основная теорема арифметики наверное в более поздних классах.
Если только в качестве магии, что типа вот такая формула "работает" и всё на этом.
Новый оптимизированный код
pfact(n,p)=my(s=0,p_i=p);while(p_i<n,s+=n\(p_i);p_i*=p);return(s)