2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Количество троек в 540!
Сообщение27.04.2025, 11:37 
Аватара пользователя


15/08/09
1485
МГУ
Добрый день.

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

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


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

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

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

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение27.04.2025, 12:12 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение27.04.2025, 12:23 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение27.04.2025, 12:24 


05/09/16
12470
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.
?

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение27.04.2025, 12:40 
Аватара пользователя


15/08/09
1485
МГУ
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 троек

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение27.04.2025, 12:46 


05/09/16
12470
То есть
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)

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение27.04.2025, 13:00 
Аватара пользователя


15/08/09
1485
МГУ
wrest
Цитата:
В итоге правильная формула:
$$q=\sum \limits_{i=1}^{\lfloor \log _p (n)\rfloor}\left \lfloor {\frac {n}{p^i}}\right \rfloor  $$


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

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

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение27.04.2025, 13:06 


05/09/16
12470
maxmatem в сообщении #1683936 писал(а):
так интересно можно ли простыми школьными методами?

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

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение27.04.2025, 13:13 
Аватара пользователя


15/08/09
1485
МГУ
wrest
8 класс )))

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение27.04.2025, 13:23 


05/09/16
12470
maxmatem в сообщении #1683941 писал(а):
8 класс )))

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

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение28.04.2025, 07:39 
Аватара пользователя


15/08/09
1485
МГУ
Всем большое спасибо, тема, как по мне , исчерпана.

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

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

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение28.04.2025, 08:24 
Заслуженный участник
Аватара пользователя


30/01/09
7429
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$ троек.

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение28.04.2025, 08:31 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение28.04.2025, 09:45 


05/09/16
12470
Евгений Машеров в сообщении #1684092 писал(а):
Собственно, эта формула в изложении для школьника младших классов (предполагая, что он знаком с делением и понятием делимости, а про факториал ему специально скажут).

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

 Профиль  
                  
 
 Re: Количество троек в 540!
Сообщение28.04.2025, 10:07 
Заслуженный участник


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

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

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



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

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


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

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