Количество троек в 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)

[maxmatem]

Всем большое спасибо, тема, как по мне , исчерпана.

-- Пн апр 28, 2025 08:40:43 --

dgwuqtj
Школьнику 8 класса сложновато

[мат-ламер]

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

Школьнику 8 класса сложновато

Школьнику 8 класса можно полученную формулу расписать не в общем виде, а конкретного для нашего случая. Причём он может это сделать сам, не исходя из общей формулы, а чисто интуитивно. В числе $540!$ содержится $540/3=180$ множителей, делящихся на $3$. Плюс $540/9=60$ множителей, делящихся на $9$. Плюс $540/27=20$ множителей, делящихся на $27$. Плюс $[540/81]=6$ множителей, делящихся на $81$. Плюс $[540/243]=2$ множителя, делящихся на $243$. Итого имеем $268$ троек.

[Евгений Машеров]

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

Цитата:

Представь выписанное на доске это произведение из 540 сомножителей. Некоторые из них делятся на 3, стало быть, каждый делящийся на 3 сомножитель даёт одну тройку.
Какие из них делятся на три? Надо ли пробовать делить или можно понять без этого?
- Три, шесть, девять... Каждый третий!
Правильно, можно узнать, сколько их будет?
- Поделить 540 на три! Нацело, с остатком.
А есть ли ещё вклад троек? Вот, скажем, число 9...
- Получается, что каждое девятое число даёт две тройки в произведение!
А надо ли их считать, как две? Или мы уже что-то учли?
- Нет, надо только дополнительную тройку учитывать!
А ещё что-то может добавить троек?
- Ещё 27, 81, 243 и... И всё.
Так сколько всего троек?

[wrest]

Евгений Машеров в сообщении #1684092 писал(а):

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

Но перед этим надо рассказать про основную теорему арифметики, т.к. на ней же всё стоит. А это не такая уж самоочевидная для 8-классника теорема, как мне кажется.

[dgwuqtj]

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