|
Вывести формулу зависимости количества правильных дробей от $%n$%, которые невозможно сократить, где числитель находится в промежутке $%1..n$%, а знаменатель равен $%n$%. Как подойти к решению такой задачки? задан 28 Апр '15 12:20 
Isaev |
|
Думаю, можно использовать Функцию Эйлера Например, $%n=24$% $$\varphi (24)=8$$ $$\frac{1}{24}; \frac{5}{24}; \frac{7}{24};\frac{11}{24};\frac{13}{24};\frac{17}{24};\frac{19}{24};\frac{23}{24}$$ В общем виде: $$\varphi (n)=n \prod_{p|n}\left ( 1-\frac{1}{p} \right )$$ отвечен 28 Апр '15 12:29 
Роман83 Но если знаменатель кратен какому-либо простому числу, то должно отсеиться больше дробей?
(28 Апр '15 12:42)
Isaev
Наоборот, в случае простого $%p$% $$\varphi (p)=p-1$$ Пример, $%p=3, \varphi (3)=3-1=2$% $$\frac{1}{3}; \frac{2}{3}$$
(28 Апр '15 12:45)
Роман83
т.е. в любом случае нужно найти все простые числа в промежутке и посчитать их количество? Или для количества есть какая-то отдельная формула? Имеется в виду общий случай, для простого числа то понятно.
(28 Апр '15 13:11)
Isaev
1
Общий случай: $$n=p_{1}^{\alpha_1}\cdot p_{2}^{\alpha_2} \cdot p_{k}^{\alpha_k}$$ $$\varphi(n)=n(1-1/p_1)(1-1/p_2)...(1-1/p_k)$$
(28 Апр '15 13:35)
Роман83
"где $%p$% — простое число и пробегает все значения, участвующие в разложении $%n$% на простые сомножители." Вот это я упустил, потому и туплю) Спасибо, работает!
(28 Апр '15 13:49)
Isaev
|
Сначала немного не правильно сформулировал.
Да, тут функция Эйлера в чистом виде: несократимость означает взаимную простоту числителя и знаменателя.