素数·派
Submitted by kzeng on Tue, 2015-03-17 22:20π 节（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]];}。
转了一圈，终于回到了古希腊：）
