完全数

[定义]

完全数（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等等。
例如：
6＝1+2+3
28＝1+2+4+7+14
496＝1+2+4+8+16+31+62+124+248
8128＝1+2+4+8+16+32+64+127+254+508+1016+2032+4064

对于“4”这个数，它的真因子有1、2，其和是3。由于4本身比其真因子之和要大，这样的数叫做亏数。对于“12”这个数，它的真因子有1、2、3、4、6，其和是16。由于12本身比其真因子之和要小，这样的数就叫做盈数。那么有没有既不盈余，又不亏欠的数呢？即等于它自己的所有真因子之和的数，这样的数就叫做完全数。

 

[性质]

完全数有许多有趣的性质：

1、它们都能写成连续自然数之和。例如：
6＝1+2+3
28＝1+2+3+4+5+6+7
496＝1+2+3+……+30+31

2、它们的全部因数的倒数之和都是2，因此每个完全数都是调和数。例如：
1/1+1/2+1/3+1/6＝2
1/1+1/2+1/4+1/7+1/14+1/28＝2

3、除6以外的完全数，还可以表示成连续奇立方数之和。例如：
28＝1^3+3^3
496＝1^3+3^3+5^3+7^3
8128＝1^3+3^3+5^3+……+15^3
33550336＝1^3+3^3+5^3+……+125^3+127^3

4、完全数都可以表达为2的一些连续正整数次幂之和。例如：
6＝2^1+2^2
28＝2^2+2^3+2^4
8128＝2^6+2^7+2^8+2^9+2^10+2^11+2^12
33550336＝2^12+2^13+……+2^24

5、完全数都是以6或8结尾。如果以8结尾，那么就肯定是以28结尾。

6、除6以外的完全数，把它的各位数字相加，直到变成个位数，那么这个个位数一定是1。（亦即：除6以外的完全数，被9除都余1）
28：2+8＝10，1+0＝1
496：4+9+6＝19，1+9＝10，1+0＝1

7、完全数公式：(2^n-1)*2^(n-1)n=质数2.3.5.7.13.17.19.31……

[历史]

公元前6世纪的毕达哥拉斯是最早研究完全数的人，他已经知道6和28是完全数。毕达哥拉斯曾说：“6象征着完满的婚姻以及健康和美丽，因为它的部分是完整的，并且其和等于自身。”不过，或许印度人和希伯来人早就知道它们的存在了。有些《圣经》注释家认为6和28是上帝创造世界时所用的基本数字，他们指出，创造世界花了六天，二十八天则是月亮绕地球一周的日数。圣·奥古斯丁说：6这个数本身就是完全的，并不因为上帝造物用了六天；事实恰恰相反，因为这个数是一个完全数，所以上帝在六天之内把一切事物都造好了。

完全数诞生后，吸引着众多数学家与业余爱好者像淘金一样去寻找。它很久以来就一直对数学家和业余爱好者有着一种特别的吸引力，他们没完没了地找寻这一类数字。接下去的两个完数看来是公元1世纪，毕达哥拉斯学派成员尼克马修斯发现的，他在其《数论》一书中有一段话如下：也许是这样，正如美的、卓绝的东西是罕有的，是容易计数的，而丑的、坏的东西却滋蔓不已；是以盈数和亏数非常之多，杂乱无章，它们的发现也毫无系统。但是完全数则易于计数，而且又顺理成章：因为在个位数里只有一个6；十位数里也只有一个28；第三个在百位数的深处，是496；第四个却在千位数的尾巴上，接近一万，是8128。它们具有一致的特性：尾数都是6或8，而且永远是偶数。第五个完全数要大得多，是33550336，它的寻求之路也艰难得多，直到十五世纪才由一位无名氏给出。这一寻找完全数的努力从来没有停止。电子计算机问世后，人们借助这一有力的工具继续探索。笛卡尔曾公开预言：“能找出完全数是不会多的，好比人类一样，要找一个完美人亦非易事。”时至今日，人们一直没有发现有奇完全数的存在。于是是否存在奇完全数成为数论中的一大难题。目前，只知道即便有，这个数也是非常之大，并且需要满足一系列苛刻的条件。

[疑难问题]

1、到底有多少完全数？
寻找完全数并不是容易的事。经过不少数学家研究，到目前为止，一共找到了47个完全数。

2、有没有奇完全数？
奇怪的是，已发现的47个完全数都是偶数，会不会有奇完全数存在呢？如果存在，它必须大于10^300。
至今无人能回答这些问题。
尽管没有发现奇完全数，但是当代数学家奥斯丁·欧尔证明，若有奇完全数，则其形式必然是12^p+1或36^p+9的形式，其中p是素数。在10^300以下的自然数中奇完全数是不存在的。

 

[完全数公式]

大数学家欧几里德曾推算出完全数的获得公式：如果2^p-1质数，那么（2^p-1）X2^（p-1）便是一个完全数。
例如p＝2，2^p-1＝3是质数，（2^p-1）X2^（p-1）＝3X2＝6，是完全数。
例如p＝3，2^p-1＝7是质数，（2^p-1）X2^（p-1）＝7X4＝28，是完全数。
但是2^p-1什么条件下才是质数呢?
事实上，当2^p-1是质数的时候，称其为梅森素数。至今，人类只发现了47个梅森素数，也就是只发现了47个完全数。

 

[实例代码]

 

#include <iostream>
using namespace std;

bool isPerfectNumber(long);
void printOut(long);

int main()
{
    for(long i=2; i<100000; i++)
    {
       if(isPerfectNumber(i))
       {
          cout<<i<<" = ";
          printOut(i);                      
       }        
    }
    
}

//计算整数n所有约数(除了自身)的和
long sum(long n)
{
   long s = 1;
   long i = 2;
   while(i < n/i)    //类似二分查找
   {
      if(n % i == 0)  //整除,说明i是n的约数
      {
         s += (i + n/i);     //此处,i*(n/i) = n,即i和n/i都是n的约数
      }
      i++;        
   } 
   return s;
}

//打印整数n的约数之和
void printOut(long n)
{
     cout<<1;
     long i=2;
     while(i < n/i)
     {
        if(n % i == 0)
        {
           cout<<" + "<<i<<" + "<<n/i;     
        }
        i++;        
     }     
     cout<<endl;
}

//判断整数n是否是完全数
bool isPerfectNumber(long n)
{
     if(n == sum(n))  //如果整数n除了自身外所有约数之和等于n,则n是完全数
     {
        return true;     
     }
     return false;
}

 控制台打印输出为

6 = 1 + 2 + 3
28 = 1 + 2 + 14 + 4 + 7
496 = 1 + 2 + 248 + 4 + 124 + 8 + 62 + 16 + 31
8128 = 1 + 2 + 4064 + 4 + 2032 + 8 + 1016 + 16 + 508 + 32 + 254 + 64 + 127
请按任意键继续. . .

  

 

附：前12个完全数
1……6
2……28
3……496
4……8128
5……33550336
6……8589869056
7……137438691328
8……2305843008139952128
9……2658455991569831744654692615953842176
10……191561942608236107294793378084303638130997321548169216
11……13164036458569648337239753460458722910223472318386943117783728128
12……14474011154664524427946373126085988481573677491474835889066354349131199152128