整数N的所有素因子（包含N本身）的和如果是N的倍数则称为多重完全数
普通的完全数是2重的
存在10重的完全数
最小的是6 1+2+3+6=12 12/6=2 2重
120 1+2+3+4+5+6+8+10+12+15+20+24+30+40+60+120=360 360/120=3 3重
以 σ(N)表示N的所有因子和
则如果σ(N)/N=k 称N为k重完全数
设N = Π p(i)^r(i) i=1..n p(i)为素数, r(i)为指数
则σ(N) = Π (p(i)^(r(i) + 1) - 1) / (p(i) - 1)
现在的问题是如何发现这类数字
大家有什么好算法
贡献出来大家讨论
17 个解决方案
#1
我有一个模糊的想法
曾经利用手算
找到好多
但这个想法现在不好实现计算机自动化
想听听大家如何解决
曾经利用手算
找到好多
但这个想法现在不好实现计算机自动化
想听听大家如何解决
#2
“整数N的所有素因子”？应该是所有因子吧。
我的理解：判断多重完全数是建立在对整数进行分解的基础上，而对大整数的分解本身就是一个难题（RSA加密得以生存的基础），恐怕很难找到满意的算法吧。
我的理解：判断多重完全数是建立在对整数进行分解的基础上，而对大整数的分解本身就是一个难题（RSA加密得以生存的基础），恐怕很难找到满意的算法吧。
#4
好好学习一下。
以前见过这个问题的讨论帖子，一见题目是E文的掉头就跑了，呵呵。
以前见过这个问题的讨论帖子，一见题目是E文的掉头就跑了，呵呵。
#5
这个题目同那个superabundant问题的确联系非常紧密，不过要求有点不同。
题目中显然是N的所有因子而不是素因子，这个应该是笔误。
superabudant问题里面没有要求σ(N)/N是整数。
这个题目更加像是一个指派问题。
不过这里看你要处理多大的N,还有要求如何（是穷举某个范围内的数还是随便找一些解，越大越好；是找到结果越大越好还是K越大越好等等）
题目中显然是N的所有因子而不是素因子，这个应该是笔误。
superabudant问题里面没有要求σ(N)/N是整数。
这个题目更加像是一个指派问题。
不过这里看你要处理多大的N,还有要求如何（是穷举某个范围内的数还是随便找一些解，越大越好；是找到结果越大越好还是K越大越好等等）
#6
谢谢指出错误
另外N的大小是受算法收敛控制的
且其中的素因子也是无法控制大小的
如果算法收敛快，则N小
否则上几百位数字也是很容易的
但已无法手算了
另外，收敛到第几重也无法预料
我手工最多算出来过6重
另外N的大小是受算法收敛控制的
且其中的素因子也是无法控制大小的
如果算法收敛快，则N小
否则上几百位数字也是很容易的
但已无法手算了
另外，收敛到第几重也无法预料
我手工最多算出来过6重
#7
我想得到个能可行的程序
最低要求
最低要求
#8
gxqcn， 你们讨论的和我的要求差的太多了啊
我手算的东西不知道被我夹到那本书里了
呵呵
大学算出来过好多结果
全乱丢了
记得还曾经算出来过好多某种规则的圈
记得最小的4重的在几万左右是5位数字
5重的可能在8位左右
我手算的东西不知道被我夹到那本书里了
呵呵
大学算出来过好多结果
全乱丢了
记得还曾经算出来过好多某种规则的圈
记得最小的4重的在几万左右是5位数字
5重的可能在8位左右
#9
另外
你们对k的大值的估计很乐观
超出我的预期
估计在k=10时，将很困难的找到结果
讨论K>20是没有意义的事情
除非能快速分解因子和判定素性！！！！
你们对k的大值的估计很乐观
超出我的预期
估计在k=10时，将很困难的找到结果
讨论K>20是没有意义的事情
除非能快速分解因子和判定素性！！！！
#10
好吧
我说说我的思路
（因为很难写公式，一半赖这个论坛，一半是自己表达能力弱）
首先对一些固定数字分析
如N=2^a*3^b*5^c*7^d类似的
则k' = σ(N)/N能迅速计算
此时，k'通常为一个分数，简化这个分数假设为p/q
此时继续增加N的素因子x^y，但保证和N的其他素因子互素，且x^y | p
得到p' / q' = p * σ(x^y) / (q * x^y)
则一般p' / q'的分子分母大小将减少
继续增加，直到q = 1则得到结果
如果在若干步骤后，无法得到结果
则需要抛弃若干步回溯到可能产生结果的位置，继续迭代
一个坏结果产生的现象是
N p / q中 P包含的小素因子太多，且和N的若干小素因子相同，一般这会产生大的k值，但超过预期的k是很难迭代到q = 1的
我说说我的思路
（因为很难写公式，一半赖这个论坛，一半是自己表达能力弱）
首先对一些固定数字分析
如N=2^a*3^b*5^c*7^d类似的
则k' = σ(N)/N能迅速计算
此时，k'通常为一个分数，简化这个分数假设为p/q
此时继续增加N的素因子x^y，但保证和N的其他素因子互素，且x^y | p
得到p' / q' = p * σ(x^y) / (q * x^y)
则一般p' / q'的分子分母大小将减少
继续增加，直到q = 1则得到结果
如果在若干步骤后，无法得到结果
则需要抛弃若干步回溯到可能产生结果的位置，继续迭代
一个坏结果产生的现象是
N p / q中 P包含的小素因子太多，且和N的若干小素因子相同，一般这会产生大的k值，但超过预期的k是很难迭代到q = 1的
#11
本来就不是讨论同一个问题，何来得差太远，应该说这个题目比那个题目要简单一些，加了整数的约束，而且对于每个K,好像找到几个数你就满意了。
至于到K=10,是有点难度，简单估计一下，就知道需要计算到比较大的整数，手工自然很难找出来
至于到K=10,是有点难度，简单估计一下，就知道需要计算到比较大的整数，手工自然很难找出来
#12
那你给我找个k=7的
我看看你们方法的效果
2^9*3*11*31 是3的
2^8*3*7*47*73是4的
今天重新算的
我看看你们方法的效果
2^9*3*11*31 是3的
2^8*3*7*47*73是4的
今天重新算的
#13
没傻意思，有必要化时间做这些没有意义的事情嘛:)
#14
晕
你们热心的计算根号2和阶乘和斐波那契数列 是有巨大意义的事情？
有意义的有呢
来一道， 可不许不会
你们热心的计算根号2和阶乘和斐波那契数列 是有巨大意义的事情？
有意义的有呢
来一道， 可不许不会
#15
使用C/C++写一个程序实现数域筛算法分解一个64位的整数
期限2年
你来？
哈哈
不用C/C++
用Python, SML/nj, Haskell, Clean等支持高精度整数的也可以
期限半年
期限2年
你来？
哈哈
不用C/C++
用Python, SML/nj, Haskell, Clean等支持高精度整数的也可以
期限半年
#16
首先更正，我没有什么热心去计算2的根号。
此外，这些事情当然都没什么意义，只是觉得有点意思而已。
这于这里，很抱歉我很难产生兴趣。有时候仅仅很多简单的因素就可以让人失去兴趣。
至于说用C/C++写程序分解大整数，可以找现成的代码（这种情况我们根本不需要理解算法的意义，这个我更加不感兴趣），也可以找一些有关资料看一下再依葫芦画瓢，这个也没有什么意义。
最后奉劝一句，不尊重别人很难获得别人的尊重。
此外，这些事情当然都没什么意义，只是觉得有点意思而已。
这于这里，很抱歉我很难产生兴趣。有时候仅仅很多简单的因素就可以让人失去兴趣。
至于说用C/C++写程序分解大整数，可以找现成的代码（这种情况我们根本不需要理解算法的意义，这个我更加不感兴趣），也可以找一些有关资料看一下再依葫芦画瓢，这个也没有什么意义。
最后奉劝一句，不尊重别人很难获得别人的尊重。
#17
情绪化了
打住
算我胡说
对引起你反感的语言我在此道歉
就是想能引起某一人或者几个人的注意
引不起大家的兴趣
只好沉没了
我只是想得到结果而已
也是为了兴趣
打住
算我胡说
对引起你反感的语言我在此道歉
就是想能引起某一人或者几个人的注意
引不起大家的兴趣
只好沉没了
我只是想得到结果而已
也是为了兴趣
#1
我有一个模糊的想法
曾经利用手算
找到好多
但这个想法现在不好实现计算机自动化
想听听大家如何解决
曾经利用手算
找到好多
但这个想法现在不好实现计算机自动化
想听听大家如何解决
#2
“整数N的所有素因子”？应该是所有因子吧。
我的理解：判断多重完全数是建立在对整数进行分解的基础上，而对大整数的分解本身就是一个难题（RSA加密得以生存的基础），恐怕很难找到满意的算法吧。
我的理解：判断多重完全数是建立在对整数进行分解的基础上，而对大整数的分解本身就是一个难题（RSA加密得以生存的基础），恐怕很难找到满意的算法吧。
#3
早已有讨论：
superabundant问题的数学及算法描述
#4
好好学习一下。
以前见过这个问题的讨论帖子，一见题目是E文的掉头就跑了，呵呵。
以前见过这个问题的讨论帖子，一见题目是E文的掉头就跑了，呵呵。
#5
这个题目同那个superabundant问题的确联系非常紧密，不过要求有点不同。
题目中显然是N的所有因子而不是素因子，这个应该是笔误。
superabudant问题里面没有要求σ(N)/N是整数。
这个题目更加像是一个指派问题。
不过这里看你要处理多大的N,还有要求如何（是穷举某个范围内的数还是随便找一些解，越大越好；是找到结果越大越好还是K越大越好等等）
题目中显然是N的所有因子而不是素因子，这个应该是笔误。
superabudant问题里面没有要求σ(N)/N是整数。
这个题目更加像是一个指派问题。
不过这里看你要处理多大的N,还有要求如何（是穷举某个范围内的数还是随便找一些解，越大越好；是找到结果越大越好还是K越大越好等等）
#6
谢谢指出错误
另外N的大小是受算法收敛控制的
且其中的素因子也是无法控制大小的
如果算法收敛快，则N小
否则上几百位数字也是很容易的
但已无法手算了
另外，收敛到第几重也无法预料
我手工最多算出来过6重
另外N的大小是受算法收敛控制的
且其中的素因子也是无法控制大小的
如果算法收敛快，则N小
否则上几百位数字也是很容易的
但已无法手算了
另外，收敛到第几重也无法预料
我手工最多算出来过6重
#7
我想得到个能可行的程序
最低要求
最低要求
#8
gxqcn， 你们讨论的和我的要求差的太多了啊
我手算的东西不知道被我夹到那本书里了
呵呵
大学算出来过好多结果
全乱丢了
记得还曾经算出来过好多某种规则的圈
记得最小的4重的在几万左右是5位数字
5重的可能在8位左右
我手算的东西不知道被我夹到那本书里了
呵呵
大学算出来过好多结果
全乱丢了
记得还曾经算出来过好多某种规则的圈
记得最小的4重的在几万左右是5位数字
5重的可能在8位左右
#9
另外
你们对k的大值的估计很乐观
超出我的预期
估计在k=10时，将很困难的找到结果
讨论K>20是没有意义的事情
除非能快速分解因子和判定素性！！！！
你们对k的大值的估计很乐观
超出我的预期
估计在k=10时，将很困难的找到结果
讨论K>20是没有意义的事情
除非能快速分解因子和判定素性！！！！
#10
好吧
我说说我的思路
（因为很难写公式，一半赖这个论坛，一半是自己表达能力弱）
首先对一些固定数字分析
如N=2^a*3^b*5^c*7^d类似的
则k' = σ(N)/N能迅速计算
此时，k'通常为一个分数，简化这个分数假设为p/q
此时继续增加N的素因子x^y，但保证和N的其他素因子互素，且x^y | p
得到p' / q' = p * σ(x^y) / (q * x^y)
则一般p' / q'的分子分母大小将减少
继续增加，直到q = 1则得到结果
如果在若干步骤后，无法得到结果
则需要抛弃若干步回溯到可能产生结果的位置，继续迭代
一个坏结果产生的现象是
N p / q中 P包含的小素因子太多，且和N的若干小素因子相同，一般这会产生大的k值，但超过预期的k是很难迭代到q = 1的
我说说我的思路
（因为很难写公式，一半赖这个论坛，一半是自己表达能力弱）
首先对一些固定数字分析
如N=2^a*3^b*5^c*7^d类似的
则k' = σ(N)/N能迅速计算
此时，k'通常为一个分数，简化这个分数假设为p/q
此时继续增加N的素因子x^y，但保证和N的其他素因子互素，且x^y | p
得到p' / q' = p * σ(x^y) / (q * x^y)
则一般p' / q'的分子分母大小将减少
继续增加，直到q = 1则得到结果
如果在若干步骤后，无法得到结果
则需要抛弃若干步回溯到可能产生结果的位置，继续迭代
一个坏结果产生的现象是
N p / q中 P包含的小素因子太多，且和N的若干小素因子相同，一般这会产生大的k值，但超过预期的k是很难迭代到q = 1的
#11
本来就不是讨论同一个问题，何来得差太远，应该说这个题目比那个题目要简单一些，加了整数的约束，而且对于每个K,好像找到几个数你就满意了。
至于到K=10,是有点难度，简单估计一下，就知道需要计算到比较大的整数，手工自然很难找出来
至于到K=10,是有点难度，简单估计一下，就知道需要计算到比较大的整数，手工自然很难找出来
#12
那你给我找个k=7的
我看看你们方法的效果
2^9*3*11*31 是3的
2^8*3*7*47*73是4的
今天重新算的
我看看你们方法的效果
2^9*3*11*31 是3的
2^8*3*7*47*73是4的
今天重新算的
#13
没傻意思，有必要化时间做这些没有意义的事情嘛:)
#14
晕
你们热心的计算根号2和阶乘和斐波那契数列 是有巨大意义的事情？
有意义的有呢
来一道， 可不许不会
你们热心的计算根号2和阶乘和斐波那契数列 是有巨大意义的事情？
有意义的有呢
来一道， 可不许不会
#15
使用C/C++写一个程序实现数域筛算法分解一个64位的整数
期限2年
你来？
哈哈
不用C/C++
用Python, SML/nj, Haskell, Clean等支持高精度整数的也可以
期限半年
期限2年
你来？
哈哈
不用C/C++
用Python, SML/nj, Haskell, Clean等支持高精度整数的也可以
期限半年
#16
首先更正，我没有什么热心去计算2的根号。
此外，这些事情当然都没什么意义，只是觉得有点意思而已。
这于这里，很抱歉我很难产生兴趣。有时候仅仅很多简单的因素就可以让人失去兴趣。
至于说用C/C++写程序分解大整数，可以找现成的代码（这种情况我们根本不需要理解算法的意义，这个我更加不感兴趣），也可以找一些有关资料看一下再依葫芦画瓢，这个也没有什么意义。
最后奉劝一句，不尊重别人很难获得别人的尊重。
此外，这些事情当然都没什么意义，只是觉得有点意思而已。
这于这里，很抱歉我很难产生兴趣。有时候仅仅很多简单的因素就可以让人失去兴趣。
至于说用C/C++写程序分解大整数，可以找现成的代码（这种情况我们根本不需要理解算法的意义，这个我更加不感兴趣），也可以找一些有关资料看一下再依葫芦画瓢，这个也没有什么意义。
最后奉劝一句，不尊重别人很难获得别人的尊重。
#17
情绪化了
打住
算我胡说
对引起你反感的语言我在此道歉
就是想能引起某一人或者几个人的注意
引不起大家的兴趣
只好沉没了
我只是想得到结果而已
也是为了兴趣
打住
算我胡说
对引起你反感的语言我在此道歉
就是想能引起某一人或者几个人的注意
引不起大家的兴趣
只好沉没了
我只是想得到结果而已
也是为了兴趣