快速寻找梅森数的最小素因子

yangchuanju · 发表于 2022-11-18 13:26

本帖最后由 yangchuanju 于 2022-11-18 18:16 编辑

yangchuanju 发表于 2022-11-18 11:25
假定3.322*10^8+7=332200007是一个稍大于3.322亿的素数，
梅森数2^332200007-1如果是一个合数，则它的最小 ...

曾一时错误地把7楼的条件设定为：假定3.322*10^(10^8)+7是一个最小的3.322亿位素数，
梅森数2^[3.322*10^(10^8)+7]-1如果是一个合数，则它的最小素因子是8k*[3.322*10^(10^8)+7]+1, (8k+2)*[3.322*10^(10^8)+7]+1, (8k+6)*[3.23*10^(10^8)+7]+1
型的奇数中的模8余1和余7的数字(k=1,2,3…)；
当然可以只用其中的模8余1和模8余7的数字去试除，模8余3的一大类数字不用再试除了。
1/lg(2)=3.321928095, 100000000/lg(2)=3.321928095*10^8，近似地取作3.322*10^8.

10^8是一个最小的9位数字，10^10^8则是一个最小的1亿零1位数字；
3.322*10^8=332200000是一个9位数字，3.322*10^10^8也是一个1亿零1位数字。
2^100000000是一个3030万位数字，2^332200000是一个亿位数字，7楼原命题没有大错误。

请问：上述梅森数的位数有多少？
答案也很简单，10^10000000=10^10^8位呗！——1亿零1位
10^10^8位大数仍然是有限数字，离无穷大还差的远呢！

yangchuanju · 发表于 2022-11-18 16:19

本帖最后由 yangchuanju 于 2022-11-18 16:20 编辑

某梅森数的第1素因子（设为m）找到后，可用同样的方法继续寻找第2素因子；
注意第2素因子（设为t）不会小于等于第1个素因子，可从第1素因子与梅森指数的比值以后开始试除，而且试除时不用试除到2^p-1的平方根，只试除到(2^p-1)/m的平方根即可。
接下去，寻找第3素因子（设为y）应从第2素因子的倍数后进行试除，直至试除到(2^p-1)/m/t的平方根即可。
……

yangchuanju · 发表于 2022-11-18 17:21

请用试除法寻找2^29-1的最小素因子。
指数29模4余1，
当指数模4余1时，只有第1素因子模24余7、17和23的，没有模24余1的；
模24余7、17和23的奇数有：
7,17,23；31,41,47；55,65,71；79,89,95；
103,113,119；127,137,143；151,161,167；175,185,191；（上一行加100再减4）
199,209,215；223,233,239；247,257,263；271,281,287；……

因第1素因子减1与梅森数指数的比值（都是整数），
都等于2，6，8，10，14，16，18，……；没有比值是4,12,20，……8n+4的。
故只需考虑上述奇数中的29的2,6,8；10,14,16；18,22,24；……倍数+1中的素数即可。
29的2,6,8；10,14,16；18,22,24；……倍数+1数有：
59,175,233；291,407,465；523,639,697；
755,871,929；987,1103,1161；……
上述两组数中同时有的奇数有：175,233，……
175明显的不是素数，第1次试除就用233，一除即出现整除奇迹，2^29-1的第一个素因子被找到！

如嫌比较繁琐，只用第1组数字中的奇素数或第2组数字中的奇素数试除未免不可。
单用第2组数字要比单用第1组数字快的多。

2^29-1-536870911, 536…/233=2304167, 230…^0.5=1517.94,
接下来用第2组数字233以后的数字进行试除，等试除到1103时，奇迹（整除）又出现了，第2素因子被找到！

2304167/1103=2089 ，经检验2089是素数，分解结束。
2^29-1=233*1103*2089。

yangchuanju · 发表于 2022-11-18 22:02

本帖最后由 yangchuanju 于 2022-11-18 22:06 编辑

110个第1素因子是指数2倍加1的梅森数（第2素因子不大于10的15次方）：
第1素因子减1除以梅指都等于2，第2素因子减1除以梅指都是整数，第2素因子减1除以第1素因子减1也都是整数。
分解态指数位数第1素因子第2素因子 2因减1/梅指 2因减1/1因减1
FF 11 4 23 89 8 4 ——发现了吗：最后一个比值是倒数第2个比值的一半，下同
FF 23 7 47 178481 7760 3880
FF 179 54 359 1433 8 4
FF 191 58 383 7068569257 37008216 18504108
FF 239 72 479 1913 8 4
FF 251 76 503 54217 216 108
FF 359 109 719 855857 2384 1192
FF 419 127 839 903780021613921 2156992891680 1078496445840
FF 431 130 863 3449 8 4
FF 443 134 887 207818990653657 469117360392 234558680196
FF 491 148 983 7707719 15698 7849
FF 719 217 1439 772207 1074 537
FF 743 224 1487 1219280833 1641024 820512
FF 911 275 1823 26129303 28682 14341
FF 1019 307 2039 75407 74 37
FF 1031 311 2063 435502649 422408 211204
FF 1223 369 2447 31799 26 13
CF 1439 434 2879 46049 32 16
CF 1451 437 2903 174121 120 60
CF 1511 455 3023 3828330041 2533640 1266820
CF 1583 477 3167 189961 120 60
CF 1931 582 3863 50207 26 13
CF 2039 614 4079 572478534119 280764362 140382181
CF 2063 622 4127 53639 26 13
CF 2339 705 4679 299393 128 64
CF 2399 723 4799 5201033 2168 1084
FF 2699 813 5399 307687 114 57
CF 2903 874 5807 60457879 20826 10413
CF 2963 892 5927 1374833 464 232
CF 3299 994 6599 19873177 6024 3012
CF 3779 1138 7559 2086009 552 276
CF 3803 1145 7607 3816820103 1003634 501817
CF 3863 1163 7727 1120271 290 145
CF 4019 1210 8039 829167929 206312 103156
CF 4211 1268 8423 92271433 21912 10956
CF 4271 1286 8543 1595303921 373520 186760
CF 4919 1481 9839 2872697 584 292
CF 4943 1488 9887 128519 26 13
CF 5003 1507 10007 1050631 210 105
CF 5039 1517 10079 122498341951 24310050 12155025
CF 5231 1575 10463 41849 8 4
CF 5279 1590 10559 929178169951 176014050 88007025
CF 5303 1597 10607 6024209 1136 568
CF 5399 1626 10799 5272458239 976562 488281
CF 5639 1698 11279 2447327 434 217
CF 5903 1777 11807 15489473 2624 1312
CF 6491 1954 12983 69440719 10698 5349
CF 6551 1973 13103 4238492663239 646999338 323499669
CF 6563 1976 13127 26777041 4080 2040
CF 6899 2077 13799 23429893156919 3396128882 1698064441
CF 6983 2103 13967 13630817 1952 976
CF 7043 2121 14087 88159606251751 12517337250 6258668625
CF 7079 2131 14159 56633 8 4
CF 7151 2153 14303 2864483907497 400571096 200285548
CF 7211 2171 14423 57689 8 4
CF 7691 2316 15383 23104702303 3004122 1502061
CF 7823 2355 15647 35370380236001 4521332000 2260666000
CF 7883 2374 15767 441449 56 28
CF 8111 2442 16223 41917649 5168 2584
FF 8243 2482 16487 4207243687 510402 255201
CF 9059 2728 18119 30293297 3344 1672
CF 9371 2821 18743 7281660583 777042 388521
CF 9479 2854 18959 48532481 5120 2560
CF 9539 2872 19079 243552125824687 25532249274 12766124637
CF 9791 2948 19583 536076833 54752 27376
CF 10091 3038 20183 484369 48 24
CF 10271 3092 20543 1568045550713 152667272 76333636
CF 10331 3110 20663 268607 26 13
CF 10691 3219 21383 10200069281 954080 477040
CF 10799 3251 21599 1024263553 94848 47424
CF 10883 3277 21767 7574569 696 348
CF 11171 3363 22343 501913031 44930 22465
CF 11471 3454 22943 144075761 12560 6280
CF 11699 3522 23399 561553 48 24
CF 11783 3548 23567 25451281 2160 1080
CF 11831 3562 23663 24583043351 2077850 1038925
CF 12011 3616 24023 838097312281 69777480 34888740
CF 12119 3649 24239 8570677991 707210 353605
CF 12671 3815 25343 99847481 7880 3940
CF 12899 3883 25799 28480993 2208 1104
CF 12923 3891 25847 261251369 20216 10108
CF 12959 3902 25919 570507017 44024 22012
CF 13451 4050 26903 107609 8 4
CF 13463 4053 26927 5497131383 408314 204157
CF 13619 4100 27239 790496415854569 58043646072 29021823036
CF 13763 4144 27527 908359 66 33
CF 14303 4306 28607 715151 50 25
CF 14783 4451 29567 4523599 306 153
CF 14831 4465 29663 38708911 2610 1305
CF 14879 4480 29759 119033 8 4
CF 14939 4498 29879 8276207 554 277
CF 15803 4758 31607 1696358907119 107344106 53672053
CF 16091 4844 32183 675823 42 21
CF 16823 5065 33647 2422513 144 72
CF 16883 5083 33767 12054463 714 357
CF 16931 5097 33863 3657097 216 108
CF 17159 5166 34319 1609426654783 93794898 46897449
CF 17183 5173 34367 721687 42 21
CF 17291 5206 34583 142339513 8232 4116
CF 17351 5224 34703 4615367 266 133
CF 17579 5292 35159 20798838409049 1183163912 591581956
CF 17939 5401 35879 143513 8 4
CF 18443 5552 36887 85317319 4626 2313
CF 18731 5639 37463 2526437281 134880 67440
CF 19163 5769 38327 443240191 23130 11565
CF 19391 5838 38783 2909929807 150066 75033
CF 19559 5888 39119 996922231 50970 25485
CF 19751 5946 39503 1480402430791 74953290 37476645
CF 19919 5997 39839 956113 48 24
CF 19991 6018 39983 133262924687 6666146 3333073

yangchuanju · 发表于 2022-11-20 03:55

梅森数都是模8余7型的奇数；
梅森因子都是模24余1,7,17,23型的奇素数，或者说都是模8余1和7型的奇素数。

梅森因子都是指数p的偶数倍加1型的奇素数；
倍数值只能是2,6,8；10,14,16；18,22,24；……
梅森因子减1除以指数“必定是整数”，进一步“必定是偶数”！

梅森因子减1除以最小素因子减1，可以是整数（整除），也可以是分数（不整除）！
这里的梅森因子可以是梅森数的素因子，也可以是它的复合因子。

yangchuanju · 发表于 2022-11-20 03:57

本帖最后由 yangchuanju 于 2022-11-20 04:01 编辑

太阳先生不要自己打自己的嘴巴吆！
2^317-1<96>=
9511*587492521482839879<18>*4868122671322098041565641<25>*9815639231755686605031317440031161584572466128599<49>
令m=9511, t=587492521482839879,
y=486...641*981...599
=47783735877628479268387358731593427074361197756454306800348746288005866959
ty=587…879*477…959
=28072587476617996036103218722657345634038278340298769450465797600439224658035965592773657961
(t-1)/(m-1)=61776290376744.4666…
(y-1)/(m-1)=
5024577905113404760082792716255880870069526577965752555241718852576852.4666…
(ty-1)/(m-1)=
2951901942862039541125469897230004798531890466908387954833417202990454748479071040249596（整数）
0.46666…=7/15
k=15,d=7,f=7,
d=f“不符合题意”吆！

太阳先生经过繁琐的检验，最终确定2^317-1的y因子是合数。
y是两个素数的乘积，“必定是合数”——还有你再检验吗？
如果允许d=f，这样的梅森数还有好多呢？
我送给你的第二发“炮弹”——113不是被你销毁了吗？
317与113不是一个娘生的“俩傻瓜”吗？

yangchuanju · 发表于 2022-11-20 05:16

本帖最后由 yangchuanju 于 2022-11-20 07:57 编辑

梅森因子都是模8余7和1型的素数，3除外；
其中模8余7的占大多数，在前10000个梅森因子中，
模8余1的只有1575个，模8余7的有8424个。
两类梅森因子都只是素数中对应类的一部分，
模8余1的梅森因子中没有素数17,41,73,97,113,137,193……；
模8余7的梅森因子中没有素数71,79,103,151,191,199……。

梅森数中没有平方、立方等多重素因子；
一个梅森因子只能是某一个梅森数的素因子，
不会是2个，3个梅森数的因子。

在多素因子梅森数中，模8余7的素因子个数应是1个，3个，5个……，必须是单数，不然的话不能保证梅森数都是模8余7的。

yangchuanju · 发表于 2022-11-20 10:05

在现有计算工具可以计算的梅森数中，满足(t-1)/(m-1)是整除的倒是不少，除(t-1)/(m-1)是整除外，另两个比值也都是整数（三整数）；
如要求第1个除式是整数，第2个除式不是整数，我还没有找到；恐怕太阳先生找到很多吧！
请发表出来，供大家欣赏呀！

如要求第2个除式是整数，第1、第3个除式不是整数的，有p=29，p=883的，但他俩的y因子都不是素数吆！

yangchuanju · 发表于 2022-11-20 10:06

本帖最后由 yangchuanju 于 2022-11-20 14:17 编辑

满足(t-1)/(m-1)是整除的倒是不少，除(t-1)/(m-1)是整除外，另两个比值也都是整数（三整数），
其中p=179,443,577,683,719是3素因子梅森数，y因子必定是素数；其余的y因子必定是合数！
指数p 素因子个数
179 3
191 5
233 4
239 6
251 5
359 6
419 5
431 8
443 3
461 4
491 7
557 5
577 3
659 4
683 3
719 3
743 7
911 4
1019 5

yangchuanju · 发表于 2022-11-20 11:58

具有2不整除+1整除的梅森数有p=73,113,317,397,499，……
花费几个日日夜夜，找到了几个“太阳素数”的副产品，其中y是素数的只有p=73一个，其余的都是合数：
指数p       素因子个数       分数1       分数2
73       3       0.6666       0.6666
113       5       0.8666       0.8666
317       4       0.4666       0.4666
397       9       0.6666       0.6666
499       3       0.285714       0.428571
601       4       0.6666       0.6666
761       5       0.3333       0.3333
937       5       0.3333       0.3333
1013       4       0.3333       0.3333

用户名		自动登录	找回密码
密码			注册