1

我正在使用 Mathematica解决Project Euler 的问题 23 ：

找出所有不能写成两个丰富数之和的正整数之和。

回想一下，丰富的数字#是这样的Total[Divisors[#]] - # > #。这是我的代码：

list1 = Table[i, {i, 1, 28123}];
list2 = Select[list1, Total[Divisors[#]] - # > # && 2 * # < 28123 &];
list3 = {};
l = Length[list2];
For[i = 1, i <= l, i++, 
 For[j = i, j <= l, j++, 
  list3 = Append[list3, list2[[i]] + list2[[j]]]]];
Total[Complement[list1, list3]]

它非常慢；嵌套For循环需要花费大量时间来评估。

我是否正确地解决了这个问题？有没有办法让它更快？

编辑：背后的原因28123是任何大于它的数字都可以写成两个丰富数字的总和。

4

2 回答 2

4

用这个替换你制作 list3 的循环。

list3 = (list2[[#]] + list2[[# ;; -1]]) & /@ Range[Length[list2]] // Flatten;

在我的旧电脑上计时为 0.49 秒

更新

回答我的答案中构造的 list3 给出错误解决方案的抱怨。

出色地。它提供与使用原始代码构建的 list3 相同的内容。这种方法只是更快。如果原始方法中的构造是错误的，那么我真的无能为力，因为问题是关于如何使它更快，而不是纠正算法本身的任何错误，我不熟悉。假设发布的算法是正确的，但速度很慢。

(*28123  replaced with smaller value to check, else will take forevever*)
(*for original algorithm to finish *)

n = 200;
list1 = Table[i, {i, 1, n}];
list2 = Select[list1, Total[Divisors[#]] - # > # && 2*# < n &];
list3 = {};
l = Length[list2];
For[i = 1, i <= l, i++, 
  For[j = i, j <= l, j++, 
   list3 = Append[list3, list2[[i]] + list2[[j]]]]];


mylist3 = (list2[[#]] + list2[[# ;; -1]]) & /@ Range[Length[list2]] //Flatten;

相比

list3 - mylist3

数学图形

于 2012-12-18T05:04:44.990 回答
2

（28123 替换为较小的值来检查，否则将永远花费）

除非您别无选择，否则我会避免在 Mathematica 中使用 for 循环。我用上述解决方案杀死了内核，因为它似乎需要很长时间才能完成。

下面的解决方案在我的 Macbook 上大约需要 6 秒。正如其他人在欧拉论坛中指出的那样，您可以将上限设置为 20161。

Total[Complement[Range[20161], 
      Plus @@ # & /@ 
         Tuples[Select[Range[20161], ((DivisorSigma[1, #] - #) > #) &], 2]]]

更新：

阅读其他一些关于优化的线程，我发现替换

Plus @@ # &Total[#]&再刮一秒。

此版本耗时 4.9 秒

Total[Complement[Range[20161], 
      Total[#] & /@ 
         Tuples[Select[Range[20161], ((DivisorSigma[1, #] - #) > #) &], 2]]]
于 2015-12-22T17:53:16.133 回答