数学研发论坛

 找回密码
 欢迎注册
查看: 16235|回复: 63

[讨论] K-Smith numbers

[复制链接]
发表于 2008-11-21 12:45:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
Smith number 是自身数字和等于其所有素因子(包含重复)的数字和的合数。
比如:666=2*3*3*37
666的数字和为:6+6+6=18;而666的所有素因子(包含重复)的数字和为:2+3+3+3+7=18,于是,666是一个Smith number。

更奇特的,三个相邻合数73615 ,73616,73617都是Smith number(73615=5*14723 ,73616=(2^4)*43*107,73617=3*53*463)。我们把K个相邻合数都是Smith number的数称为K-Smith numbers ,为了方便,就以第1个合数来表示这K个数。比如,73615 ,73616,73617,表示为3-Smith numbers : 73615。

问题:
1):请求出10^12内的所有3-Smith numbers。
2):对1<=i<=10中的每个i,请求出i-Smith numbers各一个

[ 本帖最后由 medie2005 于 2008-11-21 16:30 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 13:28:51 | 显示全部楼层
Smith number,这个我到是见过,我是在一个业余数学天地的网站上看到的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 13:45:09 | 显示全部楼层
medie找到什么好的想法了吗?
通常同进制相关的东西很难有特别有效的方法,感觉$10^19$的范围也太大了一些
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-11-21 14:06:04 | 显示全部楼层
是,大了很多,Smith number太多了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 15:00:01 | 显示全部楼层
我的想法是穷举,但没想出什么好的剪枝算法。
算法思路:
   1. 采用筛法,批量分解质因数。应该比逐个分解质因数快不少。需要用到链表(可用内存池优化性能),也需要不少的内存。
   2. .对于每个合数,计算其各位数字之和,和各个素因数各个数字之和。
   
  复杂是O(n)的算法,不知大家有没有想到更好的算法。

  对了,当n<10^19,谁能给出  每个数的素因素的个数的平均值
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 15:55:54 | 显示全部楼层
$logn$吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 16:17:40 | 显示全部楼层
平均值应该不是这么简单吧。不过每个数的素因子个数的上限是  $log_2{n}$, 因为因子越小,因子个数越多,对于形如2^k的数,如1048576,他的每个因子都达到最小值,因此因子个数达到最大值  $log_2{n}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 16:36:34 | 显示全部楼层
我有个想法,也许可以将总搜索过程降低将近一个数量级。
对于每个整数a,记N(a)为a的所有数字之和,P(a)为a的所有素因子的数字之和。那么我们就是要找N(a)-P(a)=0的所有的数。
我们知道如果N(ab)=P(ab)=P(a)+P(b),两边同时对9取余数,我们得到$N(a)xxN(b)-=P(a)+P(b)(mod 9)$
如果我们对一个比较小的范围内所有的都事先计算好N(a),P(a),然后将它们的值模9分类,共可以分成81类。然后它们之间两两组合平均应该只有1/9满足上面同余式,这样我们应该可以消去一些工作量
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 17:15:38 | 显示全部楼层
不是$log_2 n$是$ln n$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 18:17:30 | 显示全部楼层

回复 9# 无心人 的帖子

这两个数只差了一个很小的因子。
另外,我估计平均因子个数应该小于$log(n)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-1-17 20:44 , Processed in 0.066994 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表