素数·派

π 节（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]];}。

转了一圈，终于回到了古希腊：）