梅森质数 - johanzumimvon/Johan-zumimvon-Christianity GitHub Wiki

梅森质数, 又名梅森素数, Mersenne primus, メーセㇴ质数. 是指能够表示成 $\mathrm{(2^{p}−1)}$形式的质数.

亦有广义的梅森质数, 亦名循环质数, 也就是 $\mathrm{\frac{k^{p}−1}{k−1}}$

之所以是p次幂, 是因为当p为合数时, 在k进制中, 会有诸如111111111÷111=1001001这样的情况出现, 比如二进制中的111111111÷111=1001001相当于十进制中的511÷7=73.

十进制

1, 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727

十二进制

1, 3, 7, 27, X7, 48X7, 63X27, 2134X7, 4EE2308X7, 1057E377E1343360X7, 79524577E0E577476E7X8EX27, 82521X179793278231206852X37X27, 2X695925806818735399X37X20X31E3534X7

除了1, 梅森质数都有相应的完美数.

根据质数定理, 第n个梅森数是质数的概率应该超过 $\mathrm{\frac{1}{n\ln(2)}}$, 那么梅森质数的数目实质上就是调和级数. 也就是梅森质数应该有无穷多个, 完美数也应该有无穷多个.

即使是考虑到质数幂, 第n个梅森数是质数的概率也应该超过 $\mathrm{\frac{1}{n\ln(n)}\cdot\frac{1}{\ln(2)}}$, 其中的 $\mathrm{\frac{1}{n\ln(n)}}$经过微积分之後是 $\mathrm{\ln[\ln(n)]}$, 依然说明了有无穷多个梅森质数与完美数.

梅森数的非质数情形的讨论

比如, 以 $\mathrm{2^{11}−1=23\cdot89}$为例, 其中23=2·11+1=22+1, 89=8·11+1=4·22+1။

之所以如此, 是因为对于自然数n, 其倒数的循环节最长为(n−1). 比如以7为例, 十进制中, 其有:

10÷7=1モㇳ3

30÷7=4モㇳ2

20÷7=2モㇳ6

60÷7=8モㇳ4

40÷7=5モㇳ5

50÷7=7モㇳ1

可以看出, 每次除法过程, 其馀数都不会达到7, 即使是十二进制, 其每次的馀数也不会达到7:

10÷7=1モㇳ5

50÷7=8モㇳ4

40÷7=6モㇳ6

60÷7=∗モㇳ2

20÷7=3モㇳ3

30÷7=5モㇳ1

这就意味着, $\frac{1}{7}$的循环节最长为6位, 也就是除了7的倍数_{能够写成7n形式的数, 比如7, 14, 21, 28, 等等}, $\mathrm{{k^{7}-1}}$可以被7整除.

所以, 对于自然数n, 其循环节最长为[n−1].

那么对于 $\mathrm{2^{p}−1}$, 其如果可以被整除, 因子必定是[2np+1]的形式.

对于 $\mathrm{2^{11}−1}$, 其因子为23与89, 其中, 23=2·11+1; 89=8·11+1, 也就是 $\mathrm{2^{11}−1}$的因子必定为[2·11n+1]的形式. 因此其不会被[22n+1]整除的概率为

$\mathrm{(1−\frac{1}{22+1})(1−\frac{1}{44+1})(1−\frac{1}{66+1})(1−\frac{1}{88+1})\approx0.911}$

对于 $\mathrm{2^{p}−1}$, 如果其属于合数, 必定是被[2kp+1]所整除. 因此其不会被(2kp+1)整除的概率为

$\mathrm{(1−\frac{1}{2p+1})(1−\frac{1}{4p+1})(1−\frac{1}{6p+1})(1−\frac{1}{8p+1})etc(1−\frac{2p+1}{2^{p}−1})}$

当p趋于无穷大的时候, 则有

$\mathrm{(1−\frac{1}{2p+1})(1−\frac{1}{4p+1})(1−\frac{1}{6p+1})(1−\frac{1}{8p+1})etc(1−\frac{2p+1}{2^{p}−1})}$

$\mathrm{>(1−\frac{1}{2p})(1−\frac{1}{4p})(1−\frac{1}{6p})(1−\frac{1}{8p})etc}$

以下为梅森数不被整除的概率

这样的话, 第p个梅森数是质数的概率应该不少于 $\mathrm{\frac{10}{p}}$. 经过求和可得2ⁿ以内应该至少有 $\mathrm{10\ln\ln(n)}$个梅森质数.

$\mathrm{10[\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+etc+\frac{1}{n}]=\ln[\ln(n)]+c}$

也就是梅森质数应该有无穷多个, 即时是对于广义梅森质数, 也可以成立.

也就是, 完美数有无穷多个.

n以内全部质数的求和公式

∑ₙ=ln[ln(n)]+0.2614972128476427

十二进制中可写作

∑ₙ=ln[ln(n)]+0;31745#0#54

存在无穷多个偶完美数
利用上面的类似方法可以证明存在无穷多个广义梅森质数(循环质数), 比如十进制中的11, 1111111111111111111, 11111111111111111111111等等 
任意整数进位制中皆有无穷多个回文质数

6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176, etc

完美数必定能表示成 $\mathrm{\frac{M(M+1)}{2}}$ 的形式，其中M是形如 $\mathrm{(2^{p}-1)}$ 的质数，比如 $2^{7}-1=127$ ，则 $\frac{127\cdot128}{2}=8128$ 是完美数。

完美数的十二进制形式

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数：它所有的真因子（即除了自身以外的约数）的和，恰好等于它本身，完全数不可能是楔形数、平方数、佩尔数或费波那契数。

例如：第一个完全数是6，它有约数1、2、3、6，除去它本身6外，其余3个数相加， 1 + 2 + 3 = 6，恰好等于本身。第二个完全数是28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加， 1 + 2 + 4 + 7 + 14 = 28，也恰好等于本身。后面的数是496、8128。

古希腊数学家欧几里得是通过 2ⁿ⁻¹(2ⁿ−1)的表达式发现前四个完全数的。

一个偶数是完美数，当且仅当它具有如下形式: 2ⁿ⁻¹(2ⁿ−1)，其中(2ⁿ−1)是素数，此事实的充分性由欧几里得证明，而必要性则由欧拉所证明。

性质

以下是目前已发现的完全数共有的性质。

偶完全数都是以6或28结尾。
在十二进制中，除了6跟28以外的偶完全数都以54结尾，甚至除了6, 28, 496以外的偶完全数都以054或854结尾。

在六进制中，除了6以外的偶完全数都以44结尾，甚至除了6, 28以外的偶完全数都以144或344结尾。

当n为2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161时, $\mathrm{2^{n}−1}$是质数။

3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727

3, 7, 27, X7, 48X7, 63X27, 2134X7, 4EE2308X7, 1057E377E1343360X7, 79524577E0E577476E7X8EX27, 82521X179793278231206852X37X27, 2X695925806818735399X37X20X31E3534X7

当n为3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177, 9011, 9551, 36913, 43063, 49681, 57917, 483611, 877843, 2215303, 2704981, 3598867, 7973131, 8530117时, $\mathrm{\frac{3^{n}−1}{2}}$是质数။

当n为3, 7, 11, 13, 47, 127, 149, 181, 619, 929, 3407, 10949, 13241, 13873, 16519, 201359, 396413, 1888279, 3300593时, $\mathrm{\frac{5^{n}−1}{4}}$是质数။

2, 3, 7, 29, 71, 127, 271, 509, 1049, 6389, 6883, 10613, 19889, 79987, 608099, 1365019, 3360347

5, 13, 131, 149, 1699, 14221, 35201, 126037, 371669, 1264699

当n为2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, 5794777, 8177207时, $\mathrm{\frac{10^{n}−1}{9}}$是质数။

17, 19, 73, 139, 907, 1907, 2029, 4801, 5153, 10867, 20161, 293831, 1868983

2, 3, 5, 19, 97, 109, 317, 353, 701, 9739, 14951, 37573, 46889, 769543