梅森数探索点滴 广义梅森素数表

yangchuanju

大傻8888888 发表于 2022-2-17 10:26
对不起，106楼的帖子其中符号有误，现更正如下：
如果2^p-1有素因子，则这些素因子都是2np+1形式的素数  ...

仍以2^41-1=2199023255551<13>=13367*164511353为例，
2199023255551的平方根=1482910，1482910内共112957个素数，
其中2*41*n+1型素数2815个，它们是：83,739,821,1231,…,13367,…,1482907；
按前面的计算1482910/83≈17866.4，（计算式应改为（1482910-1）/82≈18084）该数值实际上是2*41*n+1型奇数的个数，
它们不都是素数，所以计算值与2815差别甚远。
实际上13367是上述2*41*n+1型素数列的第40个素数，
前面说试除到163次得到小素数13367，其中包括了不是素数的2*41*n+1型奇数，
如果老老实实地挑出适宜的素数，试除到40次即可。
然而从148万多个正整数中先筛除11万多个素数，再筛出2815个素数非常困难，
因而我说：实际操作中从中挑素数并不容易，亦可直接用它们一除了之。

若设√（2^p-1）=x，则x内的素数个数约为x/ln(x)=104360，其值相当于112957个素数；
由于x数值较小，故计算值与实际值偏差较大。
但若设√[（2^p-1）/（2p+1）]=x，则x不再有具体的数学含义，进而x/ln(x)更没有具体的数学含义。
我们所分解的梅森数都不是非常大的，套用无穷型的素数定理计算式必然产生较大偏差。

yangchuanju

第4000贴——半梅森素数
素数的概念对您来说不会生疏，但半素数是什么数？您可能就不那么熟悉了！
坦率告诉您，半素数不是素数，它是一个只含有两个素因子的二合数，
如6=2*3,10=2*5,9=3*3都是半素数。

仿照半素数的定义，不妨把只有两个素因子的梅森合数称之为“半梅森素数”，
如2^11-1=2047=23*89，2^23-1=8388607=47*178481，等等。
据统计，在前9592个梅森数中共有28个梅森素数，
320个已完全分解的梅森数中有65个只有两个素因子的梅森合数（半梅森素数）。
（素因子最多的为9个）

梅森数，包括梅森素数、半梅森素数和其它梅森合数即特别又普通。
说它普通是因为它们可以素数，也可以含两个或多个素因子的合数，它的两个素因子可以相差很远也可以相差很近；
说它特别是说它的两个素因子不可能相等，即梅森数中没有平方因子。

已知的65个半梅森素数（二因子梅森数）如下：
指数        第1因子        第2因子
11        23        89
23        47        178481
37        223        616318177
41        13367        164511353
59        179951        3203431780337<13>
67        193707721        761838257287<12>
83        167        57912614113275649087721<23>
97        11447        13842607235828485645766393<26>
101        7432339208719<13>        341117531003194129<18>
103        2550183799<10>        3976656429941438590393<22>
109        745988807        870035986098720987332873<24>
131        263        10350794431055162386718619237468234569<38>
137        32032215596496435569<20>        5439042183600204290159<22>
139        5625767248687<13>        123876132205208335762278423601<30>
149        86656268566282183151<20>        8235109336690846723986161<25>
167        2349023        79638304766856507377778616296087448490695649<44>
197        7487        2682880399...33<56>
199        164504919713<12>        4884164093883941177660049098586324302977543600799<49>
227        26986333437777017<17>        7992177738...31<52>
241        22000409        1606194743...39<66>
269        13822297        6862598850...63<74>
271        15242475217<11>        2489277578...91<72>
281        80929        4800921529...19<80>
293        40122362455616221971122353<26>        3966452270...47<63>
347        14143189112952632419639<23>        2027034530...93<83>
373        25569151        7524403464...41<105>
379        180818808679<12>        6809649408...53<103>
421        614002928307599<15>        8819779591...49<112>
457        150327409        2475539419...19<130>
487        4871        8203321996...37<143>
523        1601887783...63<69>        1714176918...89<90>
727        1760629171...27<98>        4009949972...01<122>
809        4148386731...37<61>        8229761617...03<183>
881        26431        6099757718...21<261>
971        2391710497...13<53>        8344823973...19<240>
983        1808226257914551209964473260866417929207023<43>        4520983959...09<254>
997        1675608165...07<57>        7993430605...53<244>
1061        4681722635...33<143>        5277396428...47<177>
1063        1485761479<10>        6651755792...33<311>
1427        19054580564725546974193126830978590503<38>        1948966701...09<393>
1487        24464753918382797416777<23>        1750099338...51<426>
1637        81679753        7481496656...07<485>
1657        1078842615...83<56>        5939429366...37<444>
2357        6674719305...11<62>        5049713899...61<648>
2927        1217183584262023230020873<25>        1070141538...99<858>
3079        25324846649810648887383180721<29>        2936363555...47<899>
3259        21926805872270062496819221124452121<35>        5197332446...47<947>
3359        6719        2150061062...73<1008>
4111        1081996892...31<56>        3162905096...37<1183>
4243        101833        1829713380...79<1273>
4729        61944189981415866671112479477273<32>        6009646362...07<1392>
5689        919724609777<12>        3944459715...43<1701>
6043        11155520642419038056369903183<29>        1193366805...29<1792>
6679        3206486298...21<54>        1183890815...47<1958>
7331        458072843161<12>        1548687051...27<2196>
7757        233293220467553594643512097574361<33>        5269558706...11<2303>
10169        10402314702094700470118039921523041260063<41>        1435145450...97<3022>
14561        8074991336582835391<19>        2458242926...61<4365>
17029        418879343        4146743936...77<5118>
26903        1113285395642134415541632833178044793<37>        3659037295...99<8063>
28759        226160777        9273165544...31<8649>
28771        104726441        8202550324...67<8653>
58199        237604901713907577052391<24>        1857215297...57<17497>
63703        42808417        7625786008...71<19169>
86371        41681512921035887<17>        4383409247...81<25984>

从表中容易看到，梅森数M137、M523、M1061的大小二素因子非常接近，它们很难找到；
而M11、M23、M83、M131的小因子仅为指数的2倍加1。
半梅森素数（二合数梅森数）的小素因子可以是指数的2倍加1，也可以接近于梅森数的平方根；
多因子梅森数的最小素因子可以是指数的2倍加1，最大素因子可以大于梅森数的平方根，也可以小于梅森数的平方根。
如M47=2^47-1=140737488355327=2351*4513*13264529，13264529>140737488355327^0.5=11863283。
又M29=2^29-1=536870911=233*1103*2089，2089<536870911^0.5=23170；

在用试除法分解梅森数时，还是应试除到所要分解的梅森数的平方根内的最大的2np+1那个素数，
才好确定这个梅森数到底是素数，还是合数；若是合数则在试除到平方根内最大的2np+1素数时， 分解完全。
（采用其它判断和分解方法另当别论。）

yangchuanju

试除法分解M41试除表（0表示不整除）               
n        2199023255551         附注
1        0       
2        0       
3        0       
163        164511353        2*41*163+1=13367是素数
326        0       
489        0       
18084        0        试除结束
2006236        13367       

18084次以后的试除完全没有必要，这里只是说明试除到最后究竟需要多少次，
n=163以后的试除也不是必须的，第一个素因子找到后，用M41值除以13367得164511353，
(114511353^0.5-1)/82=130.5，已小于163，试除即可结束。

上述试除法是最原始的、最笨的，除用于判断一些小素数和分解一些小合数时外，没人再使用它；不过它是各种判断和分解方法的基础。
前段时间太阳先生极力推销他的试除法寻找大素数，实际上是不可能的。

大傻8888888

yangchuanju 发表于 2022-2-17 13:59
仍以2^41-1=2199023255551=13367*164511353为例，
2199023255551的平方根=1482910，1482910内共112957 ...

     还是举例说明如下：
     仍以2^41-1=2199023255551<13>=13367*164511353为例，
     2199023255551的平方根=1482910，
    （1482910-1）/82≈18084，该数值实际上是2*41*n+1型奇数的个数，小于18084开方的素数是131，用小于等于131的奇素数筛去2*41*n+1型中 的合数，其中如果n=m时2*41*n+1是3的倍数，那么n=m+3k时2*41*n+1都是3的倍数，以此类推如果n=m时2*41*n+1是p的倍数，那么n=m+pk时2*41*n+1都是p的倍数，最后得出2*41*n+1型素数和部分伪素数，这个值大于等于其中2*41*n+1型素数2815个，如果2^41-1试除这些2*41*n+1型素数和部分伪素数都除不尽，则2^41-1是梅森素数，当然如能除尽，不管是素数还是伪素数，则2^41-1就不是梅森素数。这个方法判断梅森素数虽然也比较麻烦，但是比试除1482910内共112957个素数要容易得多。这是我的一点体会，不当之处难免，请谅！

yangchuanju

兹将本人有关梅森数的一些帖子顶起来，放到一起，供参阅！

yangchuanju

顶起来！