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

yangchuanju

wlc1 发表于 2022-1-26 20:52
时空伴随者 发表于 2021-12-22 11:08

2^7897466719774591 -1 没有10亿以内的素因子；

时空伴随者        2^7897466719774591 -1 没有10亿以内的素因子
wlc1        我的断言：2^7897466719774591 -1 没有10^16 以内的素因子
wlc1        我的断言：2^7897466719774591 -1 没有10^17 以内的素因子
时空伴随者        2^7897466719774591 -1 没有10^22 以内的素因子！
太阳        2^7897466719774591-1 试除法14次才能判断有没有10^17 以内的素因子
时空伴随者        一次也不需要验证2k×7897466719774591 + 1没有10^17以下的素数！

7897466719774591是一个16位素数，用p表示之；
2^7897466719774591-1是一个梅森数。
这个梅森数如果是合数，则它的素因子都是2kp+1形式的素数，
太阳先生说试除14次即可判断它有没有10^17以内的素因子，实则令k=1-6试除6次即可；
时空先生说一次试除也不需要，因为k=1-6时2kp+1都不是素数。
若要判断10^22以内有没有素因子，k要取到633115，并用其中的素数试除一遍才行；
时空先生不会计算出63万多个2kp+1，并用其中的素数试除之；
时空先生肯定还有奥妙隐藏在其中。

yangchuanju

太阳 发表于 2022-1-27 09:23
素数7897466719774591
2^7897466719774591-1 试除法14次才能判断有没有10^17 以内的素因子

时空伴随者        2^7897466719774591 -1 没有10亿以内的素因子
wlc1        我的断言：2^7897466719774591 -1 没有10^16 以内的素因子
wlc1        我的断言：2^7897466719774591 -1 没有10^17 以内的素因子
时空伴随者        2^7897466719774591 -1 没有10^22 以内的素因子！
太阳        2^7897466719774591-1 试除法14次才能判断有没有10^17 以内的素因子
时空伴随者        一次也不需要验证2k×7897466719774591 + 1没有10^17以下的素数！

7897466719774591是一个16位素数，用p表示之；
2^7897466719774591-1是一个梅森数。
这个梅森数如果是合数，则它的素因子都是2kp+1形式的素数，
太阳先生说试除14次即可判断它有没有10^17以内的素因子，实则令k=1-6试除6次即可；
时空先生说一次试除也不需要，因为k=1-6时2kp+1都不是素数。
若要判断10^22以内有没有素因子，k要取到633115，并用其中的素数试除一遍才行；
时空先生不会计算出63万多个2kp+1，并用其中的素数试除之；
时空先生肯定还有奥妙隐藏在其中。

yangchuanju

k        2^p-1        2kp+1
—        7897466719774591        7.89747E+15
1        15794933439549183        1.57949E+16
2        31589866879098365        3.15899E+16
3        47384800318647547        4.73848E+16
4        63179733758196729        6.31797E+16
5        78974667197745911        7.89747E+16
6        94769600637295093        9.47696E+16
7        110564534076844275        1.10565E+17
8        126359467516393457        1.26359E+17
9        142154400955942639        1.42154E+17
10        157949334395491821        1.57949E+17
100        1579493343954918201        1.57949E+18
1000        15794933439549182001        1.57949E+19
10000        157949334395491820001        1.57949E+20
100000        1579493343954918200001        1.57949E+21
600000        9476960063729509200001        9.47696E+21
633115        10000009284580180361931        1E+22

太阳

太阳

\(例1:方程\left( 29x+1\right)\times\left( 29y+1\right)-2^{29}-1＝0\)
\(正整数解:\begin{cases}
x=8\\
y=79454
\end{cases}，\begin{cases}
x=38\\
y＝16784
\end{cases}，\begin{cases}
x＝72\\
y＝8862
\end{cases}，\begin{cases}
x＝79454\\
y＝8
\end{cases}，\begin{cases}
x＝16784\\
y＝38
\end{cases}，\begin{cases}
x＝8862\\
y＝72
\end{cases}\)
\(2^{29}-1=233\times1103\times2089\)
\(试除法:方程找到1亿位大素数\)

太阳

\(例2:方程\left( 71x+1\right)\times\left( 72y+1\right)-2^{71}-1＝0\)
\(试除法，y＞x，找到一组正整数解\begin{cases}
x=2998392\\
y＝156215665098
\end{cases}，素数71\times2998392+1\)
按照这样方法找到1亿位大素数

yangchuanju

太阳 发表于 2022-1-31 09:36

二元一次方程判断梅森素数
已知：素数a>0，未知数x和y，(ax+1)×(ay+1)-2^a+1=0，方程没有正整数解
结论：2^a-1必定是素数。

解：
(ax+1)×(ay+1)-2^a+1=0不是二元一次方程，而是二元二次方程。
如果给定x(或y)，则对于y(或x)方程变成一元一次方程。

梅森数2^a-1不论是不是素数，都可表示成2ki*a+1或2ki*a+1的乘积；
式中a是素数，ki是≥1的正整数，i是有限数，等于1,2，……i。
如果该梅森数不是梅森素数，不论它有几个素因子，都可表示成(2k1*a+1)×(2k2*a+1)=(ax+1)×(ay+1)的形式，式中x=2*k1, y=2*k2都是非0正整数；
如果该梅森数是梅森素数，硬它表示成(2k1*a+1)×(2k2*a+1)=(ax+1)×(ay+1)的形式，式中x=2*k1, y=2*k2必有一个等于0。

如果方程有正整数解，即有正整数x和y使得方程成立，2^a-1便不是素数；
反之如果方程没有正整数解，即没有正整数x和y使得方程成立，2^a-1便是素数；
即找到了一个梅森素数。

yangchuanju

下一步是如何找到这个方程没有正整数解的问题了。
令a=31，
y=[(2^a-1)÷(ax+1)-1]÷a=[(2^31-1)/(31x+1)-1)/31
=(2147483647/(31x+1)-1)/31
x的取值范围是1-1494，即需1494次试除都不是方程的正整数解，才能确定2^31-1是素数。
式中1494等于2147483647^0.5/31=1494.869向下取整值。

又令a=7897466719774591（16位素数）
y=[(2^a-1)÷(ax+1)-1]÷a
x的取值要达到(2^a-1)的平方根除以a，约等于10^48758326-10^16，
计算量：
1次求幂数，1次减1；
10^48758326-10^16次除法，10^48758326-10^16次减1；
再加10^48758326-10^16次除法，判断每一次除法的商是不是整数；
总计约需4*10^48758326次计算。
试问太阳先生这种试除法有没有实用价值？

yangchuanju

改令a=100000007（最小的过亿素数）
y=[(2^a-1)÷(ax+1)-1]÷a
x的取值要达到(2^a-1)的平方根除以a，约等于10^30103002-10^8，
计算量：
1次求幂数，1次减1；
10^301030002-10^8次除法，10^30103002-10^8次减1；
再加10^301030002-10^8次除法，判断每一次除法的商是不是整数；
总计约需4*10^30103002次计算。
尚若100万个梅森数中有一个梅森素数，试除总次数平均为400*10^300000000次。
如此看来要找到第52号素数也确实不是一件容易事呀！
（现用的Lucas Lehmer判定法肯定比太阳试除法简单快捷的多）

太阳

\(例1:方程\left( 29x+1\right)\times\left( 29y+1\right)-2^{29}-1＝0\)
\(正整数解:\begin{cases}
x=8\\
y=79454
\end{cases}，\begin{cases}
x=38\\
y＝16784
\end{cases}，\begin{cases}
x＝72\\
y＝8862
\end{cases}，\begin{cases}
x＝79454\\
y＝8
\end{cases}，\begin{cases}
x＝16784\\
y＝38
\end{cases}，\begin{cases}
x＝8862\\
y＝72
\end{cases}\)
\(2^{29}-1=233\times1103\times2089\)
\(估计2^{29}-1含有最少两个素数因子大于1000，\frac{1000}{29}\approx34.4827，取x\ge34\)
\(方程\left( 29x+1\right)\times\left( 29y+1\right)-2^{29}-1＝0，y＞x，x\ge34，试除法，x＝38\)
\(按照这样做法找到2^{29}-1含有素数因子1103\)
试除法:找到1亿位大素数