更改wordpress链接,辽宁做网站和优化,商品图片网站开发,wordpress文章序号排列完美数
完美数(perfect number#xff0c;又称完全数)指#xff0c;它所有的真因子(即除了自身以外的因子)和#xff0c;恰好等于它自身。
第一个完美数#xff1a;6#xff0c;
第二个完美数#xff1a;28#xff0c;
第三个完美数#xff1a;496#xff0c;
第四个完…完美数
完美数(perfect number又称完全数)指它所有的真因子(即除了自身以外的因子)和恰好等于它自身。
第一个完美数6
第二个完美数28
第三个完美数496
第四个完美数8128
第五个完美数33550336,
.......
2 探索
在茫茫数海中第五个完美数(33550336)要大得多居然藏在千万位数的深处它在十五世纪被人们发现计算机问世后借助这一有力工具数论爱好者们继续探索。
笛卡尔曾公开预言“能找出的完美数是不会多的好比人类一样要找一个完美人亦非易事。”
时至今日人们一直没有发现有奇完美数的存在。于是是否存在奇完美数成为数论中的一大难题。只知道即便有这个数也是非常之大并且需要满足一系列苛刻的条件。
经过不少数学家研究到2013年为止一共找到了48个完美数。
3 有趣性质
1. 目前发现的完美数都是以6或8结尾会不会有奇完全数存在如果存在它必须大于10^300至今无人能回答这些问题。
2. 所有的完美数都是三角形数。例如6123
28123...67
8128123…126127
3. 所有完美数的倒数都是调和数。例如1/11/21/31/62
1/11/21/41/71/141/282
1/11/21/41/81/161/311/621/1241/2481/4962
4. 可以表示成连续奇立方数之和。除6以外的完全数都可以表示成连续奇立方数之和并规律式增加。例如281³3^3
4961^33^35^37^3
81281^33^35^3……15^3
335503361^33^35^3……125^3127^3
4 判断
如何判断是为否完美数呢在计算机数值型可以表达的的范围内我们可以尝试找一找。
这是一道leetcode题(No.507)我前段时间写过一个解在leetcode平台上已通过class Solution:
def checkPerfectNumber(self, num: int) - bool:
sum 1
tmp num
if num 0 or num1:
return False
while num%2 0:
num / 2
sum numtmp/num
return sumtmp
已知完美数都以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:
j1
print(第%d个完美数: %d%(j,i))
i1
第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位数据估计它以四号字打出时需要一本字典大小的书。
推荐阅读
点个好看
