昨天看Knuth讲算法视频，听到"Perfect Number"

今天研究了大半天。数论啊数论~那些15、16、17、18世纪的大牛怎么都这么牛呢……
先说一下什么是完美数吧：
一个数，它的所有小于或等于它自身的因子(包括1)之和=这个数
例如：
6=1+2+3 =2^1(2^2-1)=1+...+(2^2-1)
28=1+2+4+7+14 =2^2(2^3-1)=1+...+(2^3-1)
496=1+2+4+8+16+31+62+124+248 =2^2(2^5-1)=1+...+(2^5-1)
注意到后面的指数2,3,5都是质数。
****插播八卦：Knuth只带了28个学生，他认为这样已经完美了。****

多列举一些完美数：
n p_n P_n (_n表示下标, n为index，p_n为素数，P_n为完美数)
1 2 6
2 3 28
3 5 496
4 7 8128
5 13 33550336
6 17 8589869056
7 19 137438691328
8 31 2305843008139952128

研究完美数，一半必要要研究到梅森素数
完美数和梅森素数紧密关联。Mersenne primes(梅森素数):
M_p = 2^p - 1 ,如果要使得M_p为素数，p必须为素数。必要条件，例如p=11时，M_p不是梅森数，因为2^11-1不是素数。

P = 1/2(M_p+1)M_p = q*(2^(p-1)) = (2^p-1)(2^(p-1))

28=1/2(2^0 + 2^1 + 2^2)(7^0 + 7^1)


但是P= (2^p-1)(2^(p-1))仅仅是必要条件。例如p=11时，就不成立。

那么怎么办呢.....范围仍然不够小。下面看一个重要的定理，从Knuth书上翻出来的：

一个2^p-1是否梅森素数的测试方法：
Lucas-Lehma 测试(Ref:Knuth vol2,4.5.4 (24), maybe P.391)
定理: 设q是一个奇素数，用下面的规则定义序列:
L[0]=4, L[n+1]=(L[n]^2 - 2) mod (2^p -1)
那么 2^q-1 是素数，当且仅当 L[q-2]=0.


至此，这样找完美数就比较ez了，只要程序中能表示足够大的整数，就能找出尽量多。
32位int发觉只能打出六七个数，输出到33550336这个数。只是后面的数都太大了，现在仍然只找出了有限多的完美数。第八个完美数，就是19位整数了。第27个完美数(相应于梅森质数44497)是一个13395位整数，OMG...