积性函数

因子和

6的因子是1,2,3,6;6的因子和是 s(6)=1+2+3+6=12;

20的因子是1,2,4,5,10,20;20的因子和是 s(20)=1+2+4+5+10+20=42;

2的因子是1,2;2的因子和是 s(2)=1+2=3;

3的因子是1,3;3的因子和是 s(3)=1+3=4;

4的因子和是 s(4)=1+2+4=7;

5的因子和是 s(5)=1+5=6;

s(6)=s(2)*s(3)=3*4=12;

s(20)=s(4)*s(5)=7*6=42;

这是巧合吗？

再看 s(50)= 1+2+5+10+25+50=93=3*31=s(2)*s(25),s(25)=1+5+25=31.

这在数论中叫积性函数，当gcd(a,b)=1时 s(a*b)=s(a)*s(b);

如果p是素数

s(p^n)=1+p+p^2+...+p^n= (p^(n+1)-1) /(p-1)