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

yangchuanju · 发表于 2022-11-27 03:40

本帖最后由 yangchuanju 于 2022-11-27 05:38 编辑

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

梅森数因子的最小指数比是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 · 发表于 2022-11-27 05:12

指数指数比因子比模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 · 发表于 2022-11-28 05:11

指数5万以内2p+1是第1素因子的梅森数334个，
其中因子比是第2素因子减1与第1素因子减1之比，“#VALUE!”表示第2素因子已经大于10^50：
指数指数比因子比指数模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
31319 2 9 3
38231 2 9 3
46199 2 9 3
28559 2 12 3
42719 2 12 3
1223 2 13 3
1931 2 13 3
2063 2 13 3
4943 2 13 3
10331 2 13 3
41603 2 13 3
1439 2 16 3
27143 2 16 3
43691 2 16 3
47363 2 16 3
16091 2 21 3
17183 2 21 3
20771 2 21 3
25703 2 21 3
31151 2 21 3
10091 2 24 3
11699 2 24 3
19919 2 24 3
14303 2 25 3
23819 2 25 3
36191 2 25 3
38459 2 25 3
7883 2 28 3
24611 2 28 3
13763 2 33 3
1019 2 37 3
28643 2 45 3
31799 2 49 3
2699 2 57 3
34439 2 57 3
1451 2 60 3
1583 2 60 3
2339 2 64 3
39419 2 69 3
16823 2 72 3
20411 2 73 3
32843 2 73 3
32771 2 81 3
37379 2 84 3
30323 2 93 3
20963 2 97 3
5003 2 105 3
251 2 108 3
16931 2 108 3
34283 2 108 3
17351 2 133 3
27743 2 141 3
36923 2 141 3
3863 2 145 3
14783 2 153 3
20759 2 165 3
33023 2 172 3
26879 2 177 3
32159 2 181 3
35831 2 189 3
32003 2 205 3
45263 2 208 3
5639 2 217 3
22259 2 217 3
2963 2 232 3
42359 2 232 3
26459 2 252 3
3779 2 276 3
14939 2 277 3
4919 2 292 3
22943 2 340 3
10883 2 348 3
16883 2 357 3
33119 2 361 3
25643 2 373 3
28751 2 396 3
719 2 537 3
5303 2 568 3
40763 2 577 3
42611 2 664 3
38303 2 873 3
46523 2 925 3
6983 2 976 3
11783 2 1080 3
2399 2 1084 3
12899 2 1104 3
359 2 1192 3
48131 2 1288 3
14831 2 1305 3
5903 2 1312 3
22079 2 1441 3
33179 2 1660 3
9059 2 1672 3
6563 2 2040 3
18443 2 2313 3
25523 2 2365 3
9479 2 2560 3
8111 2 2584 3
38183 2 2773 3
23459 2 2925 3
3299 2 3012 3
23 2 3880 3
12671 2 3940 3
21803 2 4017 3
44543 2 4020 3
17291 2 4116 3
37991 2 4441 3
6491 2 5349 3
38891 2 6229 3
11471 2 6280 3
40343 2 6960 3
491 2 7849 3
12923 2 10108 3
37619 2 10369 3
2903 2 10413 3
48563 2 10537 3
4211 2 10956 3
19163 2 11565 3
911 2 14341 3
30983 2 17308 3
29483 2 19176 3
12959 2 22012 3
11171 2 22465 3
19559 2 25485 3
9791 2 27376 3
47279 2 30561 3
45971 2 33816 3
46703 2 36036 3
10799 2 47424 3
45119 2 57144 3
21179 2 64201 3
18731 2 67440 3
28403 2 67936 3
19391 2 75033 3
25799 2 84477 3
4019 2 103156 3
34883 2 107116 3
22751 2 110409 3
29363 2 129016 3
45131 2 129985 3
41243 2 158101 3
20939 2 160021 3
35111 2 183309 3
4271 2 186760 3
13463 2 204157 3
1031 2 211204 3
8243 2 255201 3
12119 2 353605 3
32531 2 387709 3
9371 2 388521 3
10691 2 477040 3
5399 2 488281 3
3803 2 501817 3
37871 2 601524 3
743 2 820512 3
35291 2 902248 3
28859 2 1021216 3
11831 2 1038925 3
1511 2 1266820 3
43943 2 1391205 3
7691 2 1502061 3
21011 2 1587765 3
37139 2 1591045 3
39443 2 2249905 3
19991 2 3333073 3
23339 2 4717092 3
47639 2 5662441 3
49463 2 6070117 3
5039 2 12155025 3
191 2 18504108 3
46751 2 20170801 3
20879 2 23056881 3
12011 2 34888740 3
19751 2 37476645 3
48479 2 38746572 3
48239 2 45808192 3
17159 2 46897449 3
42023 2 52695012 3
15803 2 53672053 3
49559 2 73635561 3
10271 2 76333636 3
5279 2 88007025 3
2039 2 140382181 3
7151 2 200285548 3
33623 2 239712901 3
27479 2 259257229 3
6551 2 323499669 3
24551 2 346911001 3
23099 2 589514401 3
17579 2 591581956 3
29339 2 617505265 3
30671 2 1184145733 3
6899 2 1698064441 3
49811 2 1934765496 3
7823 2 2260666000 3
27539 2 2636396197 3
7043 2 6258668625 3
44111 2 11162266321 3
9539 2 12766124637 3
13619 2 29021823036 3
42131 2 49427294544 3
13883 2 1.35212E+11 3
443 2 2.34559E+11 3
47543 2 2.92017E+11 3
46619 2 4.63055E+11 3
35099 2 5.0584E+11 3
3911 2 6.39197E+11 3
6131 2 9.8574E+11 3
419 2 1.0785E+12 3
9419 2 1.22592E+12 3
34631 2 1.52967E+12 3
2003 2 1.64469E+12 3
3851 2 1.84079E+12 3
39239 2 1.93288E+12 3
42071 2 2.63581E+12 3
21611 2 4.85525E+12 3
6323 2 8.41639E+12 3
22343 2 9.65855E+12 3
41231 2 3.18375E+13 3
1811 2 1.37971E+14 3
36383 2 1.95944E+14 3
46643 2 3.9665E+14 3
21419 2 4.61877E+14 3
26891 2 8.58015E+14 3
39659 2 4.25909E+15 3
659 2 8.74615E+15 3
24971 2 1.25404E+16 3
6263 2 1.36108E+16 3
4391 2 3.90951E+16 3
40283 2 1.19002E+18 3
38723 2 3.8453E+18 3
49103 2 4.44252E+18 3
36251 2 1.44603E+19 3
83 2 3.48871E+20 3
2939 2 1.55881E+21 3
1103 2 1.8704E+21 3
19319 2 2.64827E+21 3
36083 2 5.38703E+21 3
24203 2 6.86657E+21 3
49499 2 1.12486E+22 3
49331 2 2.04696E+22 3
2543 2 2.09064E+22 3
22271 2 1.72479E+23 3
2459 2 2.34689E+23 3
36563 2 5.03735E+23 3
15923 2 1.27521E+24 3
27983 2 2.59639E+24 3
3623 2 2.77613E+24 3
31859 2 6.6423E+24 3
35999 2 1.29451E+25 3
23603 2 2.13765E+25 3
39551 2 5.75868E+25 3
15791 2 2.92301E+27 3
12203 2 2.99426E+27 3
20063 2 7.93146E+27 3
40823 2 1.02097E+28 3
4871 2 1.48386E+28 3
18131 2 3.36246E+29 3
45599 2 3.67996E+29 3
12263 2 2.55279E+30 3
5711 2 2.23149E+32 3
21383 2 3.19801E+33 3
131 2 3.95068E+34 3
27551 2 1.10396E+36 3
2819 2 3.52869E+38 3
1499 2 1.33573E+44 3
683 2 #VALUE! 3
1559 2 #VALUE! 3
2351 2 #VALUE! 3
3023 2 #VALUE! 3
3359 2 #VALUE! 3
3491 2 #VALUE! 3
3539 2 #VALUE! 3
5051 2 #VALUE! 3
5171 2 #VALUE! 3
7103 2 #VALUE! 3
7643 2 #VALUE! 3
8663 2 #VALUE! 3
8951 2 #VALUE! 3
10163 2 #VALUE! 3
11519 2 #VALUE! 3
11579 2 #VALUE! 3
11939 2 #VALUE! 3
12791 2 #VALUE! 3
14159 2 #VALUE! 3
14699 2 #VALUE! 3
16811 2 #VALUE! 3
18191 2 #VALUE! 3
18803 2 #VALUE! 3
18899 2 #VALUE! 3
23279 2 #VALUE! 3
24239 2 #VALUE! 3
24683 2 #VALUE! 3
25919 2 #VALUE! 3
28571 2 #VALUE! 3
29531 2 #VALUE! 3
29723 2 #VALUE! 3
31019 2 #VALUE! 3
33191 2 #VALUE! 3
33479 2 #VALUE! 3
34319 2 #VALUE! 3
36791 2 #VALUE! 3
38039 2 #VALUE! 3
38639 2 #VALUE! 3
39971 2 #VALUE! 3
39983 2 #VALUE! 3
41399 2 #VALUE! 3
42743 2 #VALUE! 3
42923 2 #VALUE! 3
44651 2 #VALUE! 3
44879 2 #VALUE! 3
46691 2 #VALUE! 3

yangchuanju · 发表于 2022-11-28 05:12

指数5万以内6p+1是第1素因子的梅森数194个，
其中因子比是第2素因子减1与第1素因子减1之比，“#VALUE!”表示第2素因子已经大于10^50：
指数指数比因子比指数模4余
761 6 1.333333333 1
5717 6 1.333333333 1
23957 6 1.333333333 1
46601 6 1.333333333 1
10973 6 2.333333333 1
28517 6 2.333333333 1
38237 6 2.333333333 1
46073 6 2.333333333 1
397 6 2.666666667 1
4597 6 2.666666667 1
8377 6 2.666666667 1
11701 6 2.666666667 1
20101 6 2.666666667 1
32653 6 2.666666667 1
48337 6 2.666666667 1
6373 6 3.666666667 1
2593 6 4 1
17657 6 4 1
48353 6 4 1
6977 6 5 1
10457 6 5 1
35977 6 5 1
26681 6 5.333333333 1
25037 6 6.333333333 1
3181 6 6.666666667 1
37957 6 6.666666667 1
38461 6 6.666666667 1
3037 6 8 1
7901 6 9.333333333 1
14593 6 10.66666667 1
16561 6 11.66666667 1
15461 6 12 1
23053 6 12 1
42901 6 13 1
11833 6 16 1
16741 6 19.66666667 1
33073 6 20 1
12757 6 24 1
12037 6 28 1
30893 6 29.33333333 1
36341 6 41.33333333 1
45953 6 50.33333333 1
6353 6 57 1
17033 6 61 1
25693 6 90.66666667 1
233 6 97 1
22853 6 105 1
15601 6 139.6666667 1
27457 6 147.6666667 1
48533 6 160 1
1321 6 176 1
23873 6 192 1
49261 6 199.6666667 1
46861 6 211.6666667 1
3593 6 282.3333333 1
23497 6 334.6666667 1
1361 6 416 1
30133 6 471.6666667 1
22717 6 546.6666667 1
16481 6 645.3333333 1
5197 6 647.6666667 1
12421 6 718.6666667 1
2621 6 820 1
32693 6 869.3333333 1
21433 6 902.6666667 1
22073 6 1538.333333 1
6841 6 1582.666667 1
26633 6 2197 1
45481 6 2345 1
9613 6 2541 1
13577 6 2546.333333 1
8353 6 3075.666667 1
13997 6 3474.333333 1
25373 6 4397.333333 1
10733 6 4817.333333 1
73 6 5246.666667 1
7853 6 5412 1
5801 6 5752 1
24337 6 6399.666667 1
557 6 6581 1
14657 6 6940 1
17317 6 7454.666667 1
32441 6 11976 1
1993 6 13580 1
43801 6 14871.66667 1
41621 6 15454.33333 1
601 6 17987.66667 1
4273 6 28047.66667 1
6277 6 30890.66667 1
32713 6 63204 1
19081 6 68841 1
40693 6 71350.66667 1
40597 6 96885 1
42101 6 111973.3333 1
4933 6 122907.6667 1
15913 6 198495.6667 1
47017 6 208475.6667 1
46153 6 405676 1
19213 6 455975.6667 1
27701 6 597954.3333 1
41981 6 1071708 1
21493 6 1197989 1
18077 6 2215814.333 1
37 6 2776208 1
20173 6 4345310.667 1
18217 6 9645999.667 1
30637 6 13174730.67 1
4001 6 17361298.33 1
20521 6 20429436 1
23917 6 49896984 1
27697 6 51143167.67 1
39877 6 55815211.67 1
1381 6 55859677 1
29501 6 172638989.3 1
41737 6 411812191.7 1
3457 6 607935671.7 1
46457 6 732305213.3 1
7573 6 1461282540 1
26921 6 1942746706 1
14033 6 2297509073 1
30197 6 2403431888 1
34253 6 2417514214 1
20177 6 2419431914 1
11813 6 2934212792 1
18041 6 3126931574 1
29881 6 3633621723 1
49277 6 4022601969 1
25601 6 4496045192 1
28573 6 6006974672 1
14537 6 10633478269 1
1013 6 11761559657 1
25153 6 14611452225 1
47981 6 21038601741 1
577 6 38216572593 1
24821 6 1.77333E+11 1
13177 6 2.32653E+11 1
15661 6 3.17138E+11 1
1453 6 7.43233E+11 1
1777 6 1.20347E+12 1
4441 6 1.60079E+12 1
33773 6 2.46261E+12 1
26513 6 5.43742E+12 1
2417 6 6.59437E+12 1
5557 6 1.76464E+13 1
41333 6 1.8868E+13 1
47513 6 3.85438E+13 1
4813 6 6.46331E+13 1
461 6 1.29512E+14 1
34877 6 3.8849E+14 1
4861 6 5.11715E+14 1
39241 6 5.77345E+14 1
29921 6 9.57531E+14 1
35677 6 1.11325E+15 1
13697 6 3.30317E+15 1
36433 6 8.3808E+18 1
47533 6 1.70982E+21 1
43573 6 5.68084E+22 1
30781 6 1.42703E+23 1
4517 6 3.37376E+23 1
37181 6 6.25391E+23 1
6173 6 2.14062E+24 1
46993 6 2.20224E+24 1
30341 6 4.22318E+24 1
18757 6 1.73953E+25 1
1693 6 3.30962E+26 1
10321 6 2.38699E+27 1
39161 6 2.71993E+32 1
18013 6 4.11883E+32 1
34061 6 3.78528E+35 1
2897 6 #VALUE! 1
3581 6 #VALUE! 1
4801 6 #VALUE! 1
5393 6 #VALUE! 1
10357 6 #VALUE! 1
10853 6 #VALUE! 1
13841 6 #VALUE! 1
15073 6 #VALUE! 1
16193 6 #VALUE! 1
17681 6 #VALUE! 1
26113 6 #VALUE! 1
26393 6 #VALUE! 1
26701 6 #VALUE! 1
29221 6 #VALUE! 1
29297 6 #VALUE! 1
32717 6 #VALUE! 1
34313 6 #VALUE! 1
35797 6 #VALUE! 1
36677 6 #VALUE! 1
38653 6 #VALUE! 1
39581 6 #VALUE! 1
40277 6 #VALUE! 1
42397 6 #VALUE! 1
44201 6 #VALUE! 1
49957 6 #VALUE! 1

yangchuanju · 发表于 2022-11-28 05:19

试除法判定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 · 发表于 2022-11-28 05:20

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

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

yangchuanju · 发表于 2024-8-6 07:10

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

		自动登录	找回密码
密码			注册