完美數
完美數(perfect number，又稱完全數)指，它所有的真因子(即除了自身以外的因子)和，恰好等于它自身。
第一個完美數：6，
第二個完美數：28，
第三個完美數：496，
第四個完美數：8128，
第五個完美數：33550336,
.......
2 探索
在茫茫數海中，第五個完美數(33550336)要大得多，居然藏在千萬位數的深處！它在十五世紀被人們發現，計算機問世后，借助這一有力工具，數論愛好者們繼續探索。
笛卡爾曾公開預言：“能找出的完美數是不會多的，好比人類一樣，要找一個完美人亦非易事。”
時至今日，人們一直沒有發現有奇完美數的存在。于是是否存在奇完美數成為數論中的一大難題。只知道即便有，這個數也是非常之大，并且需要滿足一系列苛刻的條件。
經過不少數學家研究，到2013年為止，一共找到了48個完美數。
3 有趣性質
1. 目前發現的完美數都是以6或8結尾，會不會有奇完全數存在？如果存在，它必須大于10^300，至今無人能回答這些問題。
2. 所有的完美數都是三角形數。例如：6=1+2+3
28=1+2+3+...+6+7
8128=1+2+3…+126+127
3. 所有完美數的倒數都是調和數。例如：1/1+1/2+1/3+1/6=2
1/1+1/2+1/4+1/7+1/14+1/28=2
1/1+1/2+1/4+1/8+1/16+1/31+1/62+1/124+1/248+1/496=2
4. 可以表示成連續奇立方數之和。除6以外的完全數，都可以表示成連續奇立方數之和，并規律式增加。例如：28=13+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 判斷
如何判斷是為否完美數呢？在計算機數值型可以表達的的范圍內，我們可以嘗試找一找。
這是一道leetcode題(No.507)，我前段時間寫過一個解，在leetcode平臺上已通過：class Solution:
def checkPerfectNumber(self, num: int) -> bool:
sum = 1
tmp = num
if num == 0 or num==1:
return False
while num%2 == 0:
num /= 2
sum += num+tmp/num
return sum==tmp
已知完美數都以6或8結尾，所以才有了上面的方法，注意這不是尋找一個數所有因子的方法。使用6或8結尾這個小trick，實現更高效（ > 95.26%），但不嚴謹。
很遺憾，今天我發現這是一個錯誤的解法，雖然在Leetcode上已經通過。原因如下，我們試圖打印盡可能多的完美數：import sys
if __name__ == "__main__":
s = Solution()
i,j = 0,0
while(i
isPerfect = s.checkPerfectNumber(i)
if isPerfect is True:
j+=1
print("第%d個完美數: %d"%(j,i))
i+=1
第1個完美數: 6
第2個完美數: 28
第3個完美數: 120
第4個完美數: 496
第5個完美數: 2016
第6個完美數: 8128
第7個完美數: 32640
第8個完美數: 130816
第9個完美數: 523776
第10個完美數: 2096128
很明顯，120不是一個完美數，因此，可以確定Leetcode平臺遺漏了這些cases，已經將此問題提交到Leetocode，如下所示：
5 正解
如果遍歷所有的小于num的數，check是否為其因子，時間復雜度為o(n),在平臺上提交會超時。
一種更好的解法，時間復雜度為O(sqrt(n)), 因為num的兩個因子：num_i和num_j，假設num_i < num_j ，則 num_i 的最大值為 sqrt(num), 所以我們只需要遍歷到sqrt(num)即可。
代碼如下：class Solution:
def checkPerfectNumber(self, num: int) -> bool:
if num <= 0:
return False
i, sum = 1, 0
while i*i <= num:
if num % i == 0:
sum += i
if i*i != num:
sum += num / i
i += 1
return sum - num == num
6 更多完美數
6. 8,589,869,056
7. 137,438,691,328
8. 2,305,843,008,139,952,128
9. 2,658,455,991,569,831,744,654,692,615,953,842,176
10. 191,561,942,608,236,107,294,793,378,084,303,638,130,997,321,548,169,216
11. 13,164,036,458,569,648,337,239,753,460,458,722,910,223,472,318,386,943,117,783,728,128
12. 14,474,011,154,664,524,427,946,373,126,085,988,481,573,677,491,474,835,889,066,354,349,131,199,152,128
……
……
47 ……2^42643800 X (2^42643801-1)
48 ……2^57885160 X (2^57885161-1)
由于后面數字位數較多，例子只列到12個，第13個有314位。
到第39個完全數有25674127位數，據估計它以四號字打出時需要一本字典大小的書。
推薦閱讀：
點個好看
)
