本文主要基于xtx的讲稿 加上自己学习的一些体会

首先,我们考虑这样的一个表达式

 

F(1)=f(1)

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

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

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

试试用F(1)~F(n)来表示f(n)?

f(1)=F(1)

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

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

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

回顾一下f(n)的表达式,显然有这种表示方法

 

μ(x)就是Mobius函数,有

 

性质1    :

证明:

x=1 显然成立

x>1,不妨设

有                                              

要是看不懂就是公式没记下来——-xtx             ORZ

性质2

φ(n)表示欧拉函数

证明

令F(n)=n,f(n)=φ(n),有

利用Mobius反演得证

至于  的证明,引入积性

函数概念

积性函数:

对于f(n)(定义域N*),(x,y)=1=>f(xy)=f(x)f(y),则称f(n)是积性函数

完全积性函数:满足f(p^k)=f(p)^k的积性函数

常见积性函数:

φ(n),μ(n),d(n)(正因子个数),σ(n)(正因子之和)…

积性函数性质:

若f(n)为积性函数,有

1.f(1)=1

2.积性函数的约数和也为积性函数

积性函数的前缀和呢?

这是一类问题。。。

如何证明:

n=1显然成立

考虑数学归纳法

n>1,设n=p^t*q (q,p)=1

若q>1,由积性函数性质2,得证

若q=1,φ(1)+φ(p)+φ(p^2)+…φ(p^t)=p^t=n

 

 

 

 

 

分类: 莫比乌斯

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论

电子邮件地址不会被公开。 必填项已用*标注