素数公式，寻找1亿位素数

yangchuanju

雪球牛人系列——天地侠影
来自施洛斯008的雪球专栏
梅森曾于1644年断言：“2的67次方-1是个素数.”当时,人们对其断言深信不疑,连德国大数学家莱布尼兹和哥德巴赫都认为它是对的.也许这是因为梅森的名气太大了,因此没有人敢对其断言表示怀疑。

1930年（应为1903年）,在美国数学协会的年会上,数学家科尔（1861-1926）作了一次精彩的演讲,他提交的论文题目是“关于大数的因子分解”.在“演讲”过程中,他始终一言不发,只默默地在黑板上进行计算.他先算出2的67次方-1的结果,再算出193707721×761838257287的结果,两个结果完全一样.科尔第一个否定了“2的67次方-1是个素数”这一自梅森断言以来一直被人们相信的结论,其“演讲”赢得了全场听众起立热烈鼓掌和齐声喝彩.这个“一言不发的演讲”成了科学史上的佳话。

会后,人们问科尔：“你花费多少时间来研究这个问题?”他静静地说：“三年的全部星期天.”后来,这一传奇的“演讲”使他当选为美国数学协会的会长.他去世后,该协会专门设立了“科尔奖”,用于奖励作出杰出贡献的数学家。

【附注：文中括号内的数字为笔者根据其它资料增补的。】

yangchuanju

质数的性质  
被称为“17世纪最伟大的法国数学家”费尔马，也研究过质数的性质。他发现，设Fn=2^(2^n)+1，则当n分别等于0、1、2、3、4时，Fn分别给出3、5、17、257、65537，都是质数，由于F5太大（F5=4294967297），他没有再往下检测就直接猜测：对于一切自然数，Fn都是质数。但是，就是在F5上出了问题！费尔马死后67年，25岁的瑞士数学家欧拉证明：F5=4294967297=641*6700417，并非质数，而是合数。  

更加有趣的是，以后的Fn值，数学家再也没有找到哪个Fn值是质数，全部都是合数。目前由于平方开得较大，因而能够证明的也很少。现在数学家们取得Fn的最大值为：n=1495。这可是个超级天文数字，其位数多达10^10584位，当然它尽管非常之大，但也不是个质数。质数和费尔马开了个大玩笑！  



质数的假设  
17世纪还有位法国数学家叫梅森，他曾经做过一个猜想：2^p-1代数式，当p是质数时，2^p-1是质数。他验算出了：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2^p-1是质数。 p＝2，3，5，7时，Mp都是素数，但M11＝2047＝23×89不是素数。  

还剩下p=67、127、257三个梅森数，由于太大，长期没有人去验证。梅森去世250年后，美国数学家科勒证明，2^67-1=193707721*761838257287，是一个合数。这是第九个梅森数。20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。质数排列得这样杂乱无章，也给人们寻找质数规律造成了困难。

费尔马1

谢谢杨老师演讲！

yangchuanju

试除法判定2^67-1不是素数，至少要试除多少次？
2^67-1=1 4757 3952 5896 7641 2927，平方根约等于121 4800 2000，除以67约等于1 8131 3463。
只取倍数2k等于2,6,8,10,14,16,18……181313462（最大倍数模8余6）加1之奇数，共（除以2*4乘3等于）6799万个奇数；
若不排除其中的合数，不排除其中的模8余3和5的奇数，还是6799万个待试除之数。

在121.48亿内的全部素数共约52316万，分率4.3%，按奇数计分率8.6%；
6799万奇数乘以0.086等于586万，即需要试除的素数586万个。

由于2^67-1的较小素因子是193707721，约等于平方根的16%，按正比例减少需试除素数约为94万素数，
实际上，前部素数密度大，按需试除100万次计，试除到193707721，并确定它是素数。

3年内共约160个星期天，每天约需试除6250个素数，每小时625素数（按每天工作10小时计），每分钟要试除10个以上的素数。
在上面的估算中，没有计算寻找符合要求的奇数，再从中挑出素数等辅助用时。
据此估算，要用试除法分解2的67次方减1，每个星期天试除6250个素数，试除3年方能找到它的一个小素因子。

太阳

如果不使用计算器，一天也不能试除6250个素数

太阳

\(\sqrt{2^{67}-1}＝\)12148001999.90419876...，12148001999从大到小试除，
12148001999，11位数，193707721，9位数，试除奇数尾数是1，奇数尾数是7
2^67-1=147573952589676412927

太阳

\(试除\frac{2^{67}-1}{12148001999-8-10x}，奇数尾数是1，\frac{2^{67}-1}{12148001999-2-10y}，奇数尾数是7\)
这样试除也不行，试除好多次了

yangchuanju

yangchuanju 发表于 2022-11-27 19:48
试除法判定2^67-1不是素数，至少要试除多少次？
2^67-1=1 4757 3952 5896 7641 2927，平方根约等于121 480 ...

接续
选取10万内的倍数2k，只取2,6,8,10,14,16,18，……共37500个，
其中模8余1，余3，余7的各12500个，模8余3的不是需要试除的奇数，可去掉。
经查对于67来说，模8余3的倍数2k都是6+8n，据此选取2k时亦可直接取2+8n、6+8n，这样10万内的倍数2k还有25000个。
排序，删除模8余3的奇数，还剩25000个。

下一步，挑选其中的素数（用分解软件），25000个待试除奇数之中有素数3432个，占比13.728%；
再往后只能挨个试除喽——
2^67-1大于10的15次方，在16位的Excel中做除法得不到真实商，将大数分成a*10^12+b两部分，
2的67次方减1等于147573952 589676412927，分组后a=147573952，b=589676412927；
分别计算a除以p和b除以p，取a/p的小数部分乘以10^12加上b/p，看和数是不是整数。

如果用32位软件可不分组，但对于16位软件来说上述分组法还是不行的；
求和数时a/p的小数部分本该取12位以上乘以10的12次方，再与b/p相加才行，
实际上a/p的小数部分乘以10的12次方后只有3位数字还有效，
最终因计算误差竟出现4个能整除的假素因子——
假素因子        试除商
1673393        88188460564658.9969
2066951        71396928417595.0049
4706081        31358141219769.9982
5607097        26319136727914.0013
再用大素数计算软件计算，它们都不是2^67-1的素因子。       

太阳先生，不要再想往着能用试除法寻找到大素数了吧，与试除法告别吧！
试除——拜拜！

费尔马1

yangchuanju 发表于 2022-11-27 17:16
雪球牛人系列——天地侠影
来自施洛斯008的雪球专栏
梅森曾于1644年断言：“2的67次方-1是个素数.”当时, ...

台上一分钟，台下十年功！科尔是采用什么方法判断这个非梅森素数的呢？

费尔马1

yangchuanju 发表于 2022-11-27 17:16
雪球牛人系列——天地侠影
来自施洛斯008的雪球专栏
梅森曾于1644年断言：“2的67次方-1是个素数.”当时, ...

学生估计科尔的方法是，先确定这个待定数的个位数，把这个数开平方，然后，再把所得到的平方根开平方，再继续开平方根的平方，把待定数的“可能小因子”缩小到一定范围，再加灵活运用，……
2的67次方-1= 193707721×761838257287
其中193707721是素数，761838257287也是素数，
谢谢杨老师指点，我采用网上的素数计算器，这个计算器的位数达不到，所以，显示761838257287是合数。