登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

富贵而名摩灭不可胜记,唯俶傥非常之人生焉

世有大勇者,猝然临之而不惊,无故加之而不怒,此其所挟持者甚大,而其志甚远也

 
 
 

日志

 
 

 莫比乌斯函数,数论中的战斗机  

2012-07-23 03:11:54|  分类: 应用逻辑科学技术 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  莫比乌斯函数,数论函数,由德国数学家和天文学家莫比乌斯(August Ferdinand Möbius ,1790–1868)提出。梅滕斯(Mertens)首先使用μ(n)作为莫比乌斯函数的记号。而据说,高斯(Gauss)比莫比乌斯早三十年就曾考虑过这个函数。莫比乌斯函数在数论中有着广泛应用。

设f为算术函数,F为f的和函数,有F(n)=sigma[f(d)],d|n。我们现在要做的事是如何根据F求出f。

例如:

F(1)=f(1)

F(2)=f(1)+f(2)

F(3)=f(1)+f(3)

F(4)=f(1)+f(2)+f(4)

F(5)=f(1)+f(5)

F(6)=f(1)+f(2)+f(3)+f(6)

F(7)=f(1)+f(7)

F(8)=f(1)+f(2)+f(4)+f(8)

利用解方程,我们得到:

f(1)=F(1)

f(2)=F(2)-F(1)

f(3)=F(3)-F(1)

f(4)=F(4)-F(2)

f(5)=F(5)-F(1)

f(6)=F(6)-F(3)-F(2)+F(1)

f(7)=F(7)-F(1)

f(8)=F(8)-F(4)

观察发现,f(n)等于形式为+/-F(n/d),d|n,所以我们推论出莫比乌斯反演公式:

f(n)=sigma[u(d)*F(n/d)](一定要记住这个形式呀,否则后面你就不好理解了)。

现在试着确定u函数:

例如,对于上面的例子有u(1)=u(6)=1, u(2)=u(3)=u(5)=u(7)=-1,u(4)=u(8)=0。

继续观察:

若p是素数

F(p)=f(1)+f(p)=>f(p)=F(p)-F(1),那么u(p)=-1。

继续观察:

F(p^2)=f(1)+f(p)+f(p^2)=>f(p^2)=F(p^2)-(F(p)-F(1))-F(1)=F(p^2)-F(p),这又有u(p^2)=0。

同理我们推出f(p^3)=F(p^3)-F(p^2),这又有u(p^3)=0,就这样推下去,我们有当k>1,有u(p^k)=0。

继续观察:

设p1,p2为素数

F(p1*p2)=f(p1*p2)+f(p1)+f(p2)+f(1)=>f(p1*p2)=F(p1*p2)-F(p1)-F(p2)+F(1)。

这里有u(1)=1, u(p2)=-1,u(p1)=-1,u(p1*p2)=1。

如果不嫌累,你就在继续推,以下直接给出莫比乌斯函数了(要是一一列举得累死我)。

u(n) = 1 如果n=1

= (-1)^r 如果n=p1*p2*......pr,其中pi为各不相同的素数

= 0 其它

行了,莫比乌斯函数有很多性质呢。就不证明了,只给出这些性质吧。

(1)莫比乌斯函数是乘性函数

(2)设F(n)=sigma[u(d)],d|n,如果n=1,则F(n)=1,若n>1则等于0。

至于如何去验证莫比乌斯函数确实能够达到反演的大家就自己研究吧。

并且若f的和函数F是乘性的,我们可以根据莫比乌斯反演推出f也是乘性的。

好了,看看利用莫比乌斯反演公式能得到什么好玩的。

设f1(n)=n,f2(n)=1

F1(n)=sigma(f1(d)), d|n1

F2(n)=sigma(f2(d)), d|n2

那么根据反演公式有

n=sigma[u(n/d)*F1(d)]

1=sigma[u(n/d)*F2(d)]

很神奇,是吧。

还有呢

若f是欧拉函数,则f(n)=n*(sigma[u(d)/d]),d|n。

省略的证明有点多,因为我有点懒。

  评论这张
 
阅读(2696)| 评论(2)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018