posts - 225, comments - 62, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

完全数与梅森素数

Posted on 2008-08-03 21:35 魔のkyo 阅读(668) 评论(0)  编辑 收藏 引用 所属分类: Number Theory

定义：若n的真因子的和等于n，则称n为完全数。

例：6有真因子1,2,3，1+2+3=6，所以6是完全数。

定理：若p=2^n-1为素数，则p*(p+1)/2是偶完全数，且无其它偶完全数存在。（这意味着下文讲提到的"梅森素数"和"偶完全数"有一一对应关系）

奇完全数尚未被发现，是否有奇完全数存在是至今尚未解决的数论难题。

事实上，可以证明2^n-1为素数时，n也必是素数，不妨将n记为p0，形如p=2^p0-1的素数又称为梅森素数。

梅森数，即形如2^n－1的数,常记做Mn。如果梅森数为素数，则称之为“梅森素数”（即2^P－1型素数）,常记做Mp.

1930年，美国数学家雷默改进了鲁卡斯的工作，给出了一个针对Mp的新的素性测试方法，即鲁卡斯-雷默方法：Mp＞3是素数的充分必要条件是

L(p-2)=0 ModMp，其中L(0)=4，L(n+1)=(L(n)*L(n)－2)ModMp。

这一方法直到今天的“计算机时代”仍发挥重要作用。
(p=2,M2=2^2-1=3是素数，但L(2-2)=4 ModM2=1，是特例)

//输出所有[2,MAXN]内的完全数。
#include <iostream>
using namespace std;

#define MAXN 1000

//返回第n个梅森数Mn是否是素数 
bool isMersennePrime(int Mn,int n)
{
    if(n==2)return 1;
    static int L[32];
    L[0]=4;
    for(int i=1;i<=n-2;i++){
        L[i]=(L[i-1]*L[i-1]-2)%Mn;
    }
    return L[n-2]==0;
}    

int main()
{
    for(int i=2,k=4;(k-1)<=2*MAXN/k ; k<<=1,i++){
        int Mi=k-1;
        if(isMersennePrime(Mi,i)){
            printf("%d\n",Mi*(Mi+1)/2);
        }
    }
}


从下表中可以看出梅森素数是相当少的，在int范围内完全可以手动打表

有意思的是int范围内最大的数2^31-1恰好是一个梅森素数

序号 梅森素数 位数 发现时间
1 M2 1 公元前300
2 M3 1 公元前300
3 M5 2 公元前100
4 M7 3 公元前100
5 M13 4 15世纪中叶
6 M17 6 1603
7 M19 6 1603
8 M31 10 1772
9 M61 19 1883
10 M89 27 1911
11 M107 33 1914
12 M127 39 1876
13 M521 157 1952
14 M607 183 1952
15 M1279 386 1952
16 M2203 664 1952
17 M2281 687 1952
18 M3217 969 1957
19 M4253 1281 1961
20 M4423　 1332 1961
21 M9689 2917 1963
22 M9941 2993 1963
23 M11213 3376 1963
24 M19937 6002 1971
25 M21701 6533 1978
26 M23209 6987 1979
27 M44497 13395 1979
28 M86293 25962 1983
29 M110503 33265 1988
30 M132049 39751 1983
31 M216091 65050 1985
32 M756839 227832 1992
33 M859433 258716 1995
34 M1257787 378632 1996
35 M1398269 420921 1996
36 M2976221 895933 1997
37 M3021377 909526 1998
38 M6972593 2098960 1999
？ M13466917 4053946 2001
？ M20996011 6320430 2003
？ M24036583 7235733 2004

只有注册用户登录后才能发表评论。