The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

积性函数的一些证明(转)

在数论中的积性函数。对于正整数n的一个算术函数f(n),当中f(1)=1且当a,b互质,f(ab)=f(a)f(b),在数论上就称它为积性函数。

证明: f(n) = ∑g(d)^3 (d | n, g(d)表示d的约数个数)

求证: f(n) 是积性函数,即f(1) = 1, f(ab) = f(a) * f(b); a,b互质

(1)f(1) = g(1)^3 = 1 ^ 3 = 1

(2)f(n) = f(a) * f(b);

f(n) = ∑g(d)^3 (d | n, g(d)表示d的约数个数)

f(a) = ∑g(p)^3 (d | a, g(p)表示p的约数个数)

f(b) = ∑g(q)^3 (d | b, g(q)表示q的约数个数)

证明f(n) = f(a) * f(b)即证明∑g(d)^3  = ∑g(p)^3 * ∑g(q)^3

假设 d = p * q; //d为n中的某个约数,p为a中的某个约数,q为b中某个约数,总存在d = p * q

现需证明g(d)^3 = g(p)^3 * g(q)^3;

g(p)^3 * g(q)^3 = (g(p) * g(q)) ^ 3

////////////////////////////////////////////

将d质因数分解: d = p1^a1 * p2^a2 ……pj^aj

将p质因数分解: p = p1^b1 * p2^b2 ……pj^bj

将q质因数分解: q = p1^c1 * p2^c2 ……pj^cj

其中a1 = b1 + c1 , a2 = b2 + c2,…… aj = bj + cj;

因为p,q互质,所以ai = bi + ci中要么(bi == ai && ci == 0) ||  (ci == ai && bi == 0)这两种情况

g(d) = (a1 + 1) * (a2 + 1) * ……*(aj + 1);

g(p) = (b1 + 1) * (b2 + 1) * ……*(bj + 1);

g(q) = (c1 + 1) * (c2 + 1) * ……*(cj + 1);

所以g(d) = g(p) * g(q);

==> g(d)^3 = g(p)^3 * g(q)^3;

==> ∑g(d)^3  = ∑g(p)^3 * ∑g(q)^3

==> f(n) = f(a) * f(b)

从而得证f(n)是积性函数

f(n) = f(p1^a1) * f(p2 ^ a2) * f(p3 ^ a3) …… * f(pj^aj);

f(p1^a1) = ∑g(d)^3 (d | p1 ^ 3) 由p1是质因数

所以d的取值为p1^0, p1 ^ 1, p1^2, ……,p1^a1

g(p1^i) = i + 1;

故f(p1^a1) = (0 + 1) ^ 3 + (1 + 1) ^ 3 + …… + (a1 + 1) ^ 3 = (a1 + 1)^2 * (a1 + 2)^2 / 4;

以此类推,

所以最终f(n) = f(p1 ^ a1) * f(p2 ^ a2) * …… * f(pj ^ aj)

            = ((a1 + 1)^2 * (a1 + 2) ^2 / 4) * ((a2 + 1)^2 * (a2 + 2)^2 / 4) * …… *

                ((aj + 1)^2 * (aj + 2)^2 / 4);

将n质因数分解后进行统计即可。(本人代码效率不行,如果谁有更有效率的代码麻烦给我一个,让我学习学习)。

////////////////////////////////////////////////////////////////


转自:http://blog.sina.com.cn/s/blog_5c95cb070100ej4c.html

posted on 2009-11-02 18:30 abilitytao 阅读(235) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理