素数·派

π 节(3月14日)已经过去了,所以现在写 π 就当是向魔幻圆周率致敬吧。其实数学的发展最需要牛人,就像祖冲之,冷不丁的从历史里给你扔出一个 355/113 (=3.1415929204) 来,等你回过神来,这个 355/113 是如何得到的已经湮没在历史的尘埃中了,所以牛人之后还需要不太牛的传承者。也是因为中国的数学研究一直缺乏传承(后来很大一部分因为科举),在元朝时数学大跃进之后,到了明朝,就大踏步的倒退到了简单算术(虽然珠算得到了很大的发展)。

相比较而言,欧洲的数学一直到十六世纪初都不过尔尔(古希腊的数学传统到那时已经断掉),但是在突然冒出了笛卡尔,莱布尼茨,牛顿,伯努利等人以后,数学的发展风驰电掣,而到了欧拉,简直是神一样的人物了。

莱布尼茨给出了一个用无穷级数求π的方法:

pi= 4*sum (-1)^n/(2n+1)

在 Q 里快速的实现一下:

 {sum raze 4%(1 -1)*/:(0N,2)#1+2*til x} 1000000
 3.1415916536

上例一共用了一百万项,精度略低于祖冲之的密率。

然后是欧拉用 p-级数的方法:

pi = sqrt( 6 * sum (1/n^2))

在Q里快速实现一下:

` {sqrt 6 * sum 1 % {x*x} 1_til x} 1000000 3.1415916987

同样一百万项,收敛速度和莱布尼茨的无穷级数差不多,但是作为大神,欧拉进一步证明了上述p-级数与素数乘积的关系:

sum 1/n^s = prd 1/(1- p^-s)   p 是所有素数

当 s = 2 时, 我们就可以得到

prd 1/(1-p^-2) = sum 1/n^2 = pi^2 /6 

这等同于

如果我们从 1 到 N 的N个自然数中随意抽取两个数,那么这两个数互质(最大公约数为一)的概率在当 N 趋近于正无穷的时候趋近于 6 / pi ^ 2

以上推论的证明很简单,如果两个数互质,那么它们没有共同的素数因子。任意一个自然数被一个素数 p整除的概率是 1/p,譬如,能被5 整除的数字每间隔5个出现一次。任意两个自然数能被 p 整除的概率是 1/p^2. 至少一个不能被整除的概率是 1-1/p^2。把这个结论扩展到任意的 p,那么这个概率就是 prd (1- 1/p^2) for all p。 简单的变形,我们知道这个概率是 6/pi^2

简单的蒙特卡洛一下:

{sqrt 6% avg 1={$[y=0;:x;:.z.s[y;x mod y]];}./:(0N;2)#(1+ x?x)} 1000000
3.1431107401

从一百万个自然数中随机选取50万对,然后算互质的概率。上述模拟中求最大公约数时用的是欧几里得算法:{$[y=0;:x;:.z.s[y;x mod y]];}

转了一圈,终于回到了古希腊:)

Blog分类: