马林梅森
在只能手工计算的时代,人们就开始了对梅森素数的寻找,直到19世纪末,人们只找到了12个梅森素数。p值分别是:2,3,5,7,13,17,19,31,61,89,107,127。
在计算机诞生以后,人们搜索梅森素数的速度加快,直到1996年为止,数学家使用了超级计算机Cray-T94,发现了第34个梅森素数。
进入互联网时代,一个更加精妙的方法诞生了。1996年1月,美国数学家及程序设计师乔治·沃特曼(George Woltman)编写了一个梅森素数计算程序。他把程序放在网页上供数学家和数学爱好者免费使用,这就是最初的互联网梅森素数大搜索计划了(Great Internet Mersenne Prime Search,GIMPS)。任何拥有个人电脑的人都可以加入GIMPS,成为一名素数猎人。
从1997年至今,所有新的梅森素数都是通过GIMPS分布式计算项目发现的。这个项目成功聚集了数十万台计算机进行一个问题的计算,它的计算能力已经远远超出我们的想象。
其中,最新第50个梅森素数的发现,就是美国一位普通的电气工程师Jonathan Pace,用一台普通的家庭计算机,CPU型号是i5-6600,幸运地通过GIMPS发现了这个梅森素数,不仅在数学史上留下了自己的名字,而且得到了3000美元的奖励。(大家如果有兴趣,可以下载一个试试,第一个找到超过1亿位数梅森素数的人,奖励15万美元)
素数的寻找方法
素数行踪不定,分布未知,怎么样才能找到素数?
在公元前2世纪希腊数学家埃拉托斯特尼(Eratosthenes),就已经提出了一个非常简单而且有效的素数筛法,我们称之为埃拉托斯特尼筛法(Sieve of Eratosthenes)。核心是:要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。
一个埃拉托斯特尼筛法的例子
具体的筛法如下:
第1步:确定需要筛选素数的范围,确定范围的最大值,比如是120。第2步:根号120的结果为10.95,所以只需要利用11以内所有素数的倍数来剔除120以内的数字,剩下的就是素数。首先剔除以2为倍数的数字,11以内剔除掉4,6,8,10这几个数字,同时剔除掉120以内所有以2为倍数的数字。第3步:最小的未被剔除的数字为3,剔除以3为倍数的数字,11以内剔除9这个数字,同时剔除掉120以内所有以3为倍数的数字。第4步:最小的未被剔除的数字为5,剔除以5为倍数的数字,11以内不需要剔除数字,同时剔除掉120以内所有以5为倍数的数字。……如此类推,可以将120以内的所有素数完全找到。
不得不说,古人的智慧实在是太让人佩服。
普及完素数知识,超模君忽然发现,第50和51位梅森素数都是在12月被发现!
而新的一年即将到来,是否第52位梅森素数将被发现了? 就让我们拭目以待吧。