1千万以内因数数目最多的是哪个？

gxqcn

这是昨晚，上小学五年级的儿子问我的，
我没能答上来，他也没答案，因为题目是他自创的。

282842712474

第一想法是：$2*3*5*7*11*13*17*19=9699690$，共256个因子。

但是想想，如果牺牲一个$19$，可以换来$2^4$，此时$2^5*3*5*7*11*13*17=8168160$，共384个因子。

再牺牲一个17？可以考虑，但是不能将$17$换成$2^4$了， 这样反而得不偿失，更优的办法是$2^4*3^4*5*7*11*13=6486480$，有400个因子。

不知道还有没有更优。

282842712474

更正一下，最多因子的是8648640，有448个因子，它等于$2^6*3^3*5*7*11*13$，它在$2^4*3^4*5*7*11*13=6486480$的基础上，牺牲了一个3，换来了两个2。

其次是9424800, 7207200，因子均为432个

已经用mathematica验证过（算法效率可能不高）：

1. f[q_] := Length[Divisors[q]];
   
2. b = Map[f, Range[10^7]];
   
3. Ordering[b, 1, Greater]

复制代码

gxqcn

谢谢啊！

如果是人工搜索，是不是主要靠局部调整实现？

他按了会计算器，也得到 \(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19=9699690\)（可能这也正是他把范围限定在“1千万以内”的原因吧），
但我反驳了他，\(2^4\cdot3\cdot5\cdot7 \lt 2\cdot3\cdot5\cdot7\cdot11\)，但显然前者的因子个数更多！

KeyTo9_Fans

这里列出了因子数目最多的数：
http://oeis.org/A002182/b002182.txt

我们可以看到，$1$千万以内的最后一项是第$47$项：$8648640$，

与你们手工搜寻的结果吻合。

gxqcn

牛！下班后就跟儿子说去：“你的问题已有高人解决了”！

我想知道的是，可有快速的算法？是指那种非常非常快的那种！

KeyTo9_Fans

这是$0$-$1$背包问题的一个特例。

而一般的$0$-$1$背包问题是没有理论时间复杂度为【关于物品数量的多项式】的算法。

但是，我们可以根据这个特例的特点，设计出针对于这个特例的高效算法。

以$10000000$为例，它的对数$\log 10000000=7$就是背包的容量。

我们有以下物品：

物品　　体积　价值
第$1$个$2$　$\log 2$　$\log 2$
第$2$个$2$　$\log 2$　$\log(3/2)$
第$3$个$2$　$\log 2$　$\log(4/3)$
第$4$个$2$　$\log 2$　$\log(5/4)$
……
第$1$个$3$　$\log 3$　$\log 2$
第$2$个$3$　$\log 3$　$\log(3/2)$
第$3$个$3$　$\log 3$　$\log(4/3)$
第$4$个$3$　$\log 3$　$\log(5/4)$
……
第$1$个$5$　$\log 5$　$\log 2$
第$2$个$5$　$\log 5$　$\log(3/2)$
第$3$个$5$　$\log 5$　$\log(4/3)$
第$4$个$5$　$\log 5$　$\log(5/4)$
……
第$1$个$7$　$\log 7$　$\log 2$
第$2$个$7$　$\log 7$　$\log(3/2)$
第$3$个$7$　$\log 7$　$\log(4/3)$
第$4$个$7$　$\log 7$　$\log(5/4)$
……

这个特例的最优解是选择以下物品：

物品　　体积　价值
第$1$个$2$　$\log 2$　$\log 2$
第$2$个$2$　$\log 2$　$\log(3/2)$
第$3$个$2$　$\log 2$　$\log(4/3)$
第$4$个$2$　$\log 2$　$\log(5/4)$
第$5$个$2$　$\log 2$　$\log(6/5)$
第$6$个$2$　$\log 2$　$\log(7/6)$
第$1$个$3$　$\log 3$　$\log 2$
第$2$个$3$　$\log 3$　$\log(3/2)$
第$3$个$3$　$\log 3$　$\log(4/3)$
第$1$个$5$　$\log 5$　$\log 2$
第$1$个$7$　$\log 7$　$\log 2$
第$1$个$11$　$\log 11$　$\log 2$
第$1$个$13$　$\log 13$　$\log 2$
————————————————————
总计　$\log 8648640$　$\log 448$

算法如下：
$1$、把物品按照【价值体积比】从大到小排序；
$2$、把序列里的物品依次放入背包，如果某个物品放不下，则跳过，直到所有物品都放不下为止，得到一个可行解；
$3$、把可行解看作一个$01$字符串：选了第$i$个物品，字符串的第$i$位就是$1$，否则就是$0$；
$4$、找字符串字典序里的下一个可行解。
重复$4$。

该算法实际上是递归的算法，第$i$层递归会将字符串里的第$i$位从$1$循环到$0$，终止条件如下：

假设当前处理到第$i$个物品，那么当前的理论最优解就是把这一物品无限复制、切割，塞满背包。如果这一理论最优解不比当前最好的可行解好，就可以结束这一层递归。

由于这个特例性质良好，这一算法足以对付容量为$1000$以内的背包，即$10^1000$以内的最大因子数问题。

mathematica

1. Clear["Global`*"];(*Clear all variables*)
   
2. f={#,Length@Divisors@#}&/@Range[10^7];
   
3. fmax=Max[f[[All,2]]];(*找出因子个数最多的是多少个*)
   
4. Select[f,#[[2]]==fmax&](*选出因子最多的数*)
   

复制代码

{{8648640, 448}}
穷举法完美得到结果

zeroieme

http://wwwhomes.uni-bielefeld.de/achim/highly.html

zeroieme

mathematica 发表于 2017-5-24 14:52
{{8648640, 448}}
穷举法完美得到结果

读完大学依然是小学生的思维，不是愚蠢是什么。