5

我一直在慢慢地解决 Project Euler 问题的列表，我已经找到了一个我知道如何解决的问题，但似乎我做不到（考虑到我的解决方案的编写方式）。

我正在使用 Common Lisp 来执行此操作，并且我的脚本已经运行了超过 24 小时（远超过他们的一分钟目标）。

为了简洁起见，这是我的解决方案（这是一个剧透，但前提是你有一个非常快的处理器）：

(defun square? (num)
  (if (integerp (sqrt num)) T))

(defun factors (num)
  (let ((l '()))
    (do ((current 1 (1+ current)))
        ((> current (/ num current)))
      (if (= 0 (mod num current))
          (if (= current (/ num current))
              (setf l (append l (list current)))
              (setf l (append l (list current (/ num current)))))))
    (sort l #'< )))

(defun o_2 (n)
  (reduce #'+ (mapcar (lambda (x) (* x x)) (factors n))))

(defun sum-divisor-squares (limit)
  (loop for i from 1 to limit when (square? (o_2 i)) summing i))

(defun euler-211 ()
 (sum-divisor-squares 64000000))

使用更小、更友好的测试参数解决问题所需的时间似乎比指数级增长……这是一个真正的问题。

花了：

  • 0.007 秒解决 100
  • 0.107 秒求解 1000
  • 2.020 秒解决 10000
  • 56.61 秒解决 100000
  • 1835.385 秒求解 1000000
  • 24+小时解决64000000

我真的想弄清楚脚本的哪些部分导致它需要这么长时间。我已经考虑过记忆因子函数，但我不知道如何实际实现它。

对于那些想看看问题本身的人，在这里。

任何关于如何使这件事变得更快的想法将不胜感激。

**对不起，如果这对任何人来说是一个剧透，它并不意味着......但如果你有计算能力在相当长的时间内运行它，那么你就有更多的能力。

4

7 回答 7

14

这是一个解决方案，牢记 [Project] Euler 的精神。[警告：剧透。我试图让提示保持缓慢，以便您只能阅读部分答案并根据需要自行思考。:)]

当您遇到与数字有关的问题时，一个好的策略（正如您可能已经从解决 210 个 Project Euler 问题中知道的那样）是查看小示例，找到一个模式并证明它。[根据您对数学的态度，最后一部分可能是可选的；-)]

但是，在这个问题中，看一些小例子——对于 n=1,2,3,4,... 可能不会给你任何提示。但是在处理数论问题时还有另一种意义上的“小例子”，你现在可能也知道——素数是自然数的组成部分，所以从素数开始。

对于素数 p，它的唯一除数是 1 和 p，所以它的除数的平方和是 1+p 2。
对于素数 p k，它的唯一除数是 1, p, p 2 , ... p k，所以其除数的平方和是 1+p+p 2 +...+p k =(p k+1 - 1)/(p-1)。
那是最简单的情况：你已经解决了所有数字的问题，只有一个素数。

到目前为止没有什么特别的。现在假设你有一个数 n，它有两个质因数，比如 n=pq。那么它的因数是1、p、q和pq，所以它的除数的平方和是1+p 2 +q 2 +p 2 q 2 =(1+p 2 )(1+q 2 )。
那么 n=p a q b呢？其因子的平方和是多少？

[.......................在此行下方阅读有危险...... ....]

∑ 0≤c≤a, 0≤d≤b (p c q d ) 2 = ((p a+1 -1)/(p-1))((q b+1 -1)/(q -1））。

这应该给你提示，答案是什么以及如何证明它：n 的除数之和只是其因式分解中每个素数幂的（答案）的乘积，所以你只需要要做的是分解 64000000 （即使在一个人的头脑中也很容易做到:-)）并乘以每个（=两者，因为唯一的素数是 2 和 5）的素数幂的答案。

这解决了 Project Euler 问题；现在从道德上拿走它。

这里更普遍的事实是关于乘法函数——自然数上的函数使得当 gcd(m,n)=1 时 f(mn) = f(m)f(n)，即 m 和 n 在常见的。如果你有这样一个函数，那么函数在特定数字上的值完全由它在素数上的值决定（你能证明这一点吗？）

稍微难一点的事实，你可以尝试证明[它并不难]，是这样的：如果你有一个乘法函数 f [这里，f(n)=n 2 ] 并且你将函数 F 定义为 F(n) = ∑ d 除以 n f(d)，（就像问题在这里所做的那样）然后 F(n) 也是一个乘法函数。

[事实上，非常美丽的东西是真实的，但现在不要看它，你可能永远不需要它。:-)]

于 2008-12-03T02:53:46.567 回答
3

我认为你的算法不是最有效的。提示：你可能从错误的角度开始。

编辑：我想补充一点，选择 64000000 作为上限可能是问题发布者告诉你想出更好的东西的方式。

编辑：一些效率提示：

  • 代替
(setf l (append l (...)))

您可以使用

（推（...）升）

它会破坏性地修改您的列表，方法是使用一个新单元格，您的值为 car，前者l为 cdr，然后指向l该单元格。这比每次都必须遍历列表一次的追加要快得多。如果您需要其他顺序的列表，您可以在完成后将其反转（但此处不需要）。

  • 你为什么排序l？

  • 您可以(> current (/ num current))通过与 num 的平方根进行比较来提高效率（每个 num 只需计算一次）。

  • 是否有可能更有效地找到数字的因数？

还有一个样式提示：您可以将范围l放入 do 声明中：

(做 ((l ()))
     (电流 1 (+电流 1)))
    ((> 当前 (/当前数))
     l)
  ...)
于 2008-12-03T01:43:48.500 回答
2

我会通过对数字进行素数分解来解决这个问题（例如：300 = 2^2 * 3^1 * 5^2），这相对较快，特别是如果你通过筛子生成它。由此，通过迭代 i=0..2 来生成因子是相对简单的；j=0..1；k=0..2，做 2^i * 3^j * 5^k。

5 3 2
-----
0 0 0 = 1
0 0 1 = 2
0 0 2 = 4
0 1 0 = 3
0 1 1 = 6
0 1 2 = 12
1 0 0 = 5
1 0 1 = 10
1 0 2 = 20
1 1 0 = 15
1 1 1 = 30
1 1 2 = 60
2 0 0 = 25
2 0 1 = 50
2 0 2 = 100
2 1 0 = 75
2 1 1 = 150
2 1 2 = 300

这可能不够快

于 2008-12-03T02:52:59.843 回答
2

您缺少的巧妙技巧是您根本不需要考虑数字 1..N 中有多少数字是 1 的倍数？N 1..N 中有多少个数是 2 的倍数？N/2

诀窍是将列表中的每个数字的因子相加。对于 1，将 1^2 添加到列表中的每个数字。对于 2，每隔一个数字加上 2^2。对于 3，每第三个数字加 3^2。

根本不检查可分性。最后，您必须检查总和是否是完美平方，仅此而已。在 C++ 中，这对我来说只需要 58 秒。

于 2009-03-11T01:48:32.697 回答
1

抱歉，我不太了解 LISP，无法阅读您的答案。但我的第一印象是暴力破解的时间成本应该是：

开括号

sqrt(k) 找到 k 的除数（通过试除法），将每个除数平方（每个因子的恒定时间），并将它们相加（每个因子的恒定时间）。这是 σ 2 (k)，我称之为 x。

加

不确定一个好的整数平方根算法的复杂性是多少，但肯定不比 sqrt(x) （哑试乘法）差。x 可能比 k 大-O，所以我在这里保留判断，但是 x 显然在 k^3 之上，因为 k 最多有 k 个除数，每个除数本身不大于 k，因此它的平方不大于 k ^2。自从我获得数学学位以来已经很长时间了，我不知道 Newton-Raphson 收敛的速度有多快，但我怀疑它比 sqrt(x) 更快，如果所有其他方法都失败了，那么二进制斩波就是 log(x)。

右括号

乘以 n（因为 k 的范围为 1 .. n）。

因此，如果您的算法比 O(n * sqrt(n^3)) = O(n ^ (5/2)) 差，在哑平方的情况下，或者 O(n * (sqrt(n) + log( n^3)) = O(n ^ 3/2) 在 smart-sqrt 的情况下，我认为在算法中应该可以识别出问题。此时我被卡住了，因为我无法调试你的 LISP .

哦，我假设算术对于正在使用的数字是恒定时间的。它应该适用于小到 6400 万的数字，并且它的立方几乎适合 64 位无符号整数。但是，即使您的 LISP 实现使算术比 O(1) 差，它也不应该比 O(log n) 差，因此它不会对复杂性产生太大影响。当然不会使它成为超多项式。

这是有人过来告诉我我错了。

哎呀，我只是看了你的实际时间数字。它们并不比指数差。忽略第一个和最后一个值（因为小时间不能准确测量并且您还没有分别完成），将 n 乘以 10 将时间乘以不超过 30-ish。30 大约是 10^1.5，这对于如上所述的蛮力来说是正确的。

于 2008-12-03T01:16:34.127 回答
0

我认为你可以用像初筛这样的东西来解决这个问题。不过这只是我的第一印象。

于 2008-12-03T01:35:22.777 回答
0

我用这里的评论中的一些注释重新设计了程序。'factors' 函数现在效率稍微高了一点，我还必须修改 σ_(2)(n) 函数以接受新的输出。

“因素”的输出如下：

$ (factors 10) => (1 2 5 10)

有一个喜欢

$ (factors 10) => ((2 5) (1 10))

修改后的函数如下所示：

(defun o_2 (n)
"sum of squares of divisors"
  (reduce #'+ (mapcar (lambda (x) (* x x)) (reduce #'append (factors n)))))

在我进行了适度的重写之后，我在计算 100,000 时只节省了大约 7 秒。

看起来我将不得不离开我的屁股并写一个更直接的方法。

于 2008-12-03T05:50:57.567 回答