2014 dxdy logo

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

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




 
 Сумма по делителям
Сообщение25.02.2013, 19:26 
Здравствуйте!

Чему равно такая сумма $$\sum \limits_{d \mid n}\mu(d)\varphi\left(\frac{n}{d}\right)$$
Помогите пожалуйста

 
 
 
 Re: Сумма по делителям
Сообщение25.02.2013, 19:36 
Аватара пользователя
Про Möbius Transform слышали когда-нибудь, например?

 
 
 
 Re: Сумма по делителям
Сообщение25.02.2013, 19:46 
ИСН
Да слышал. Попытался, но ничего не вышло.
Пусть данная сумма равна $F(n)$, тогда из обращения Мебиуса имею, что $\varphi(n)=\sum \limits_{d\mid n}F(d)$

 
 
 
 Re: Сумма по делителям
Сообщение25.02.2013, 19:51 
Аватара пользователя
Упс... Это в другую сторону оно хорошо, а в эту плохо.

 
 
 
 Re: Сумма по делителям
Сообщение25.02.2013, 19:57 
Узнать, чему равна сумма, можно, спросив у суммы. Вычислите ее в нескольких точках. Чему равно $S(2), S(3), S(p), S(pq)$? ($p,q$ - простые)

 
 
 
 Re: Сумма по делителям
Сообщение25.02.2013, 19:58 
Аватара пользователя
Короче, она выражается через разложение n на простые, примерно как сама фи, только чуть хитрее.

-- Пн, 2013-02-25, 21:01 --

Всё, что сказал Sonic86, сделайте сначала для нечётных. да.

 
 
 
 Re: Сумма по делителям
Сообщение25.02.2013, 20:13 
Вообще такая сумма $$\sum \limits_{d \mid n}\mu(d)\varphi\left(\frac{n}{d}\right)$$
есть свертка мультипликативных функций. Любая свертка мультипликативных функций сама является мультипликативной, т.е. достаточно их вычислить для значений $n=p^k$.

 
 
 
 Re: Сумма по делителям
Сообщение25.02.2013, 20:14 
Аватара пользователя
Можно наверное еще так:
Ваша сумма есть не что иное, как свертка Дирихле функций $\mu(n)$ и $\varphi(n)$. Ну пусть Ваша сумма есть $F(n)$, тогда она мультипликативна так как функции Мебиуса и Эйлера мультипликативны.
Очевидно, что $F(1)=1$ (из мультипликативности).
Пусть $n>1$ тогда $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Значит, $$F(n)=F(p_1^{\alpha_1})F(p_2^{\alpha_2})\dots F(p_k^{\alpha_k})$$ Ну посчитаем для $\alpha>1$ $$F(p^{\alpha})=\sum \limits_{d \mid p^{\alpha}}\mu(d)\varphi\left(\frac{p^{\alpha}}{d}\right)=\mu(1)\varphi(p^{\alpha})+\mu(p)\varphi(p^{\alpha-1})+\dots+\mu(p^{\alpha})\varphi(1)=p^{\alpha-2}(p-1)^2$$ Нетрудно убедиться, что $F(p)=p-2$
Здесь я также пользуюсь тем, что $\mu(p^n)=0$ при $n\geqslant 2$
Осталось их перемножить и все

(Оффтоп)

Руст опередил меня

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group