求完美数

redraiment, 2008-07-10

　　一个数如果恰好等于它的因子之和，这个数就称为“完美数”或“完数”，例如 6=1+2+3（6的因子是1,2,3）。完美数的一些性质：

1. 欧几里德证明了：一个偶数是完数，当且仅当它具有如下形式：2^(p-1)×(2^p-1) 其中 p 和 2p-1 是素数。尽管没有发现奇完数，但是当代数学家奥斯丁·欧尔（Oystein Ore）证明，若有奇完全数，则其形状必然是 12p+1 或 36p+9 的形式，其中 p 是素数。在 1018 以下的自然数中奇完数是不存在的。
2. 除 6 以外的偶完数，把它的各位数字相加，直到变成一位数，那么这个一位数一定是 1（亦即：除6以外的完数，被9除都余1） 28：2+8=10，1+0=1 496：4+9+6=19，1+9=10，1+0=1
3. 因为 2^p 是 2 的幂，用C语言也就是 1 << p，那么 2^p-1 的二进制也就是 p 个 1 组成了，而 2^(p-1) 是 2的幂，这两个数相乘，也就相当于把 2^p-1 向左移 p-1 位，即 (2p-1) << (p-1)，那所有完美数的二进制就是前面 p 个 1，后面跟着 p-1 个 0。 所以偶完数都可以表达为 2 的一些连续正整数次幂之和，如：
   6 = 2¹ + 2²; 28 = 2² + 2³ + 2⁴; 8128 = 2⁶ + 2⁷ + ... + 2¹²; 33550336 = 2¹² + 2¹³ + ... + 2²⁴
   

   j = ((1 + (i ^ (i-1) )) >> 1) + i - 1;
   (j & (j + 1)) || (i & 1)

4. 上面的代码可以判断整数 i 是否是前面 1 后面 0 的形式。
5. 每一个偶完数都可以写成连续自然数之和： 6=1+2+3; 28=1+2+3+4+5+6+7; 496=1+2+3+…+30+31
6. 除6以外的偶完数，还可以表示成连续奇数的立方和（被加的项共有)： 28 = 1³ + 3³; 496 = 1³ + 3³ + 5³ + 7³; 8128 = 1³ + 3³ + 5³ + ... + 15³; 33550336 = 1³ + 3³ + 5³ + ... + 125³ + 127³
7. 每一个完数的所有约数(包括本身)的倒数之和，都等于2： 1/1 + 1/2 + 1/3 + 1/6 = 2; 1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 2

　　了解了上面一些性质后，就可以简单的来写一个求完美数的程序了。

#include <stdio.h>

#ifndef WIN32

typedef long long ll;

#else

typedef __int64 ll;

#endif

int main(void)

{

    ll i, j, n, x;

    for (n = 2; n <= 31; n++)

    {

        x = (1 << n) - 1;

        for(i = 3; i*i <= x; i += 2)

            if(x % i == 0)

                break;

        if(i*i <= x) continue;

        printf("%lld\n", (1 << (n - 1)) * x);

    }

    return 0;

}

　　运行结果：

6

28

496

8128

33550336

8589869056

137438691328

2305843008139952128

　　到目前为止，已经求出的2^p-1是素数的有25个：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。 据说最后一个即2²¹⁷⁰¹－1是1978年两名美国大学生新发现的截止目前为止最大的一个素数，所以我们可以利用这个结果来求已知的完美数：

import java.math.BigInteger;

public class Main

{

    public static void main(String[] argv)

    {

        int [] prime = {

            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

        };

        BigInteger x = BigInteger.ONE;

        for (int i = 0; i < prime.length; i++)

            System.out.println ( x.shiftLeft(prime[i]-1)

                .multiply(x.shiftLeft(prime[i])

                .subtract(x)));

    }

}

　　最后一个完美数的长度是13066！堪称是BinIntegest了

---