趣味无穷的梅森数和梅森因子

yangchuanju

太阳 发表于 2022-11-26 20:55
判断素数十分困难，也找不到规律，素数公式可能真的不存在

寻找梅森因子的分布规律——从而找到梅森数的分解方法，是我探讨的宗旨；
当然研究梅森数的因子比也可能有一定的帮助，故我跟随太阳先生花费了大量的精力；
但我不会继续研究太阳的那些不可能成立的“素数公式”。

梅森数因子的最小指数比是2，什么样的梅森数具有2p+1型的素因子呢？
什么样的梅森数具有6p+1型的素因子呢？
太阳先生不妨把精力转到这里来！
初步查明，具有指数比等于2的梅森数指数都是模4余3的，指数5万以内、第1素因子10^50以内共334个；
指数比等于6的梅森数指数都是模4余1的，指数5万以内、第1素因子10^50以内共194个。

太阳先生正在对具有4c-3型因子比进行研究，可继续研究下去！
（4c-3实际上就是4k+1。）
初步查明在指数5万以内、第1，2素因子10^50以内梅森数中，第2、第1素因子比等于4的如下：
指数比为2的有：11,179,239,431,5231,7079,7211,……共22个；
指数比为6的有：2593,17657,48353。总数不算多。

yangchuanju

指数        指数比        因子比        模4余
11        2        4        3
179        2        4        3
239        2        4        3
431        2        4        3
5231        2        4        3
7079        2        4        3
7211        2        4        3
13451        2        4        3
14879        2        4        3
17939        2        4        3
26111        2        4        3
28019        2        4        3
28499        2        4        3
30851        2        4        3
36479        2        4        3
39779        2        4        3
40559        2        4        3
43391        2        4        3
44699        2        4        3
45179        2        4        3
48731        2        4        3
49919        2        4        3
2593        6        4        1
17657        6        4        1
48353        6        4        1

yangchuanju

试除法求1亿位大素数。

梅森数2^23-1的素因子是模8余7和余1的素数，因子至少是指数的2倍加1，
47是一个模8余7的素数，等于23*2+1，试除知它是梅森数的一个素因子。

以下选定继续试除上限：2^23-1=8388607，除以47等于178481，平方根等于422，除以23等于18；
下一步看23乘6,8,10；14,16,18加1是不是它的素因子？
首先看它们是不是素数，不是素数的肯定不是；
再看各个素数模8的余数，不是7和1的也不是。
倍数加1中只有一个素数139，它又是模8余3的不用再试；
当然找到要试除的素数后，还可以查看一下它是不是其它梅森数的素因子，若是亦可免试除，
不过比对并不容易，还不如直接试除爽快一些。

至此已经知道，2^23-1除以47之商的平方根内没有其它素因子；
该梅森数的另一个素因子便是8388607/47=178481。
(178481-1)/23=7760，7760模8余0；178481模8余1，故2^23-1=47*178481。
一个6位小素数被找到！

倍数k        23k+1        模8余数        素性
2        47        7        素数
6        139        3        素数
8        185        1        合数
10        231        7        合数
14        323        3        合数
16        369        1        合数
18        415        7        合数
7760        178481        1        素数

yangchuanju

给太阳先生提供20个最大的梅森数余因子。

r序号        素数                                                        位数
1        (2^106391-1)/286105171290931103        32010
2        (2^87691-1)/806957040167570408395443233        26371
3        (2^86371-1)/41681512921035887        25984
4        (2^86137-1)/2584111/7747937967916174363624460881        25896
5        (2^84211-1)/1347377/31358793176711980763958121/3314641676042347824169591561        25291
6        (2^82939-1)/883323903012540278033571819073        24938
7        (2^78737-1)/1590296767505866614563328548192658003295567890593        23654
8        (2^63703-1)/42808417        19169
9        (2^58199-1)/237604901713907577052391        17497
10        (2^57131-1)/61481396117165983261035042726614288722959856631        17152
11        (2^53381-1)/15588960193/38922536168186976769/155991271597169062945033668006103        16008
12        (2^51487-1)/57410994232247/17292148963401772464767849635553        15455
13        (2^41681-1)/1052945423/16647332713153/2853686272534246492102086015457        12495
14        (2^41521-1)/41602235382028197528613357724450752065089        12459
15        (2^41263-1)/(1402943*983437775590306674647)        12395
16        (2^35339-1)
/490988430384989040283954404/86235033667674267835480981233904512709297747031041        10562
17        (2^32531-1)/(65063825225122959)        9778
18        (2^32611-1)
/15148007312464299210917787487318/99943932296901864652928732838910515860494755367311         9736
19        (2^29473-1)/(5613392570256862943*24876264677503329001)        8835
20        (2^28771-1)/104726441        8653
（数据摘自网络）

yangchuanju

再来一组最大的10个素数。
               
序号    素数                                              位数
1        2618163402417·2^1290000-1        388342
2        18543637900515·2^666667-1        200701
3        183027·2^265440-1        79911
4        648621027630345·2^253824-1        76424
5        620366307356565·2^253824-1        76424
6        1068669447·2^211088-1        63553
7        99064503957·2^200008-1        60220
8        12443794755·2^184516-1        55555
9        21749869755·2^184515-1        55555
10        14901867165·2^184515-1        55555
（数据来自网络）

yangchuanju

2^67-1=193707721*761838257287 你可以用baidu计算器验算一下. 1903年,在纽约的一次数学报告会上,数学家科乐上了讲台,他没有说一句话,只是用粉笔在黑板上写了两数的演算结果,一个是2的67次方－1,另一个是193707721×761838257287,两个算式的结果完全相同,这时,全场爆发出经久不息的掌声.这是为什么呢? 因为科乐解决了两百年来一直没弄清的问题,即2是67次方－1是不是质数?现在既然它等于两个数的乘积,可以分解成两个因数,因此证明了2是67次方－1不是质数,而是合数. 科尔只做了一个简短的无声的报告,可这是他花了3年中全部星期天的时间,才得出的结论.在这简单算式中所蕴含的勇气,毅力和努力,比洋洋洒洒的万言报告更具魅力.

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个梅森数是合数。质数排列得这样杂乱无章，也给人们寻找质数规律造成了困难。

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年方能找到它的一个小素因子。

yangchuanju

接续
选取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的素因子。      

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