K-Smith numbers

medie2005

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 编辑 ]

liangbch

Smith number，这个我到是见过，我是在一个业余数学天地的网站上看到的。

mathe

medie找到什么好的想法了吗？ 通常同进制相关的东西很难有特别有效的方法，感觉$10^19$的范围也太大了一些

medie2005

是，大了很多，Smith number太多了。

liangbch

我的想法是穷举，但没想出什么好的剪枝算法。 算法思路： 1. 采用筛法，批量分解质因数。应该比逐个分解质因数快不少。需要用到链表（可用内存池优化性能），也需要不少的内存。 2. .对于每个合数，计算其各位数字之和，和各个素因数各个数字之和。 复杂是O(n)的算法，不知大家有没有想到更好的算法。 对了，当n<10^19,谁能给出 每个数的素因素的个数的平均值

无心人

$logn$吧

liangbch

平均值应该不是这么简单吧。不过每个数的素因子个数的上限是 $log_2{n}$, 因为因子越小，因子个数越多，对于形如2^k的数，如1048576，他的每个因子都达到最小值，因此因子个数达到最大值 $log_2{n}$

mathe

我有个想法，也许可以将总搜索过程降低将近一个数量级。 对于每个整数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满足上面同余式，这样我们应该可以消去一些工作量

无心人

不是$log_2 n$是$ln n$

liangbch

这两个数只差了一个很小的因子。 另外，我估计平均因子个数应该小于$log(n)$