optimization - 如何更快地解决 Euler Project Problem 303？

Question

problem是:

For a positive integer n, define f(n) as the least positive multiple of n that, written in base 10, uses only digits ≤ 2.

Thus f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222.

---

为了在 Mathematica 中解决它，我编写了一个函数 f 来计算 f(n)/n :

f[n_] := Module[{i}, i = 1; 
While[Mod[FromDigits[IntegerDigits[i, 3]], n] != 0, i = i + 1]; 
Return[FromDigits[IntegerDigits[i, 3]]/n]]

原理很简单:用三元数制枚举所有0, 1, 2的数，直到其中一个数除以n。

它正确地给出了 1~100 的 11363107，我测试了 1~1000(计算大约花了一分钟，并给出了 111427232491)，所以我开始计算问题的答案。

但是，这个方法太慢了。计算机已经计算了两个小时的答案，还没有计算完。

如何改进我的代码以加快计算速度？

Answer 1

hammar 的评论清楚地表明，计算时间不成比例地花费在 n 的值上，它们是 99 的倍数。我建议找到一种针对这些情况的算法(我将其保留为读者练习)并使用 Mathematica 的模式匹配将计算定向到适当的计算。

f[n_Integer?Positive]/; Mod[n,99]==0  :=  (*  magic here *)
f[n_] := (* case for all other numbers *) Module[{i}, i = 1;
 While[Mod[FromDigits[IntegerDigits[i, 3]], n] != 0, i = i + 1];
 Return[FromDigits[IntegerDigits[i, 3]]/n]]

顺便说一句，您可以通过稍微不同的方式来加快快速简单的速度，但这当然是二阶改进。您或许可以将代码设置为最初使用 ff，如果 i 达到某个点，则中断 While 循环，然后切换到 f 您已经提供的功能。 (注意我在这里返回 n i 而不是 i - 这只是为了说明目的。)

ff[n_] := 
 Module[{i}, i = 1; While[Max[IntegerDigits[n i]] > 2, i++]; 
  Return[n i]]

Table[Timing[ff[n]], {n, 80, 90}]

{{0.000125, 1120}, {0.001151, 21222}, {0.001172, 22222}, {0.00059, 
  11122}, {0.000124, 2100}, {0.00007, 1020}, {0.000655, 
  12212}, {0.000125, 2001}, {0.000119, 2112}, {0.04202, 
  1121222}, {0.004291, 122220}}

对于短案例，这至少比您的版本(转载如下)快一点，但对于长案例，它要慢得多。

Table[Timing[f[n]], {n, 80, 90}]

{{0.000318, 14}, {0.001225, 262}, {0.001363, 271}, {0.000706, 
 134}, {0.000358, 25}, {0.000185, 12}, {0.000934, 142}, {0.000316, 
 23}, {0.000447, 24}, {0.006628, 12598}, {0.002633, 1358}}