Haskell Wiki 中 Project Euler 问题 27 的这个解决方案是如何工作的？

How does this solution of Project Euler Problem 27 in the Haskell Wiki work?

提问人：Naitik Mundra 提问时间：7/15/2022 最后编辑：Naitik Mundra 更新时间：7/15/2022 访问量：474

问：

我一直在解决一些随机的欧拉计划问题来练习我的 haskell。解决问题后，我通常会在 haskell wiki 上查找解决方案。

对于问题 27，我以常规方式解决它，即使用 和 s 的组合。但后来，我在 wiki 上看到了这个解决方案。我不知道这个解决方案是如何工作的。我发现的唯一其他提及来自math stackexchange上的这个封闭线程。isPrimemap

problem_27 :: Integer
problem_27 = -(2 * a - 1) * (a ^ 2 - a + 41)
  where
    n = 1000
    m = head $ filter (\x -> x ^ 2 - x + 41 > n) [1 ..]
    a = m - 1

我试图理解这段代码

据我了解，此代码执行以下操作

  1. 设 n=1000
  2. 设 m 为第一个自然数 x，使得 x^2 - x + 41 大于 n（这里是 1000）
  3. 则 a = m - 1
  4. 问题的答案是 -（2a-1） * （a^2-a+41）：（我认为这意味着两者是系数。

但我不明白为什么这个程序给出了正确的答案。或者换句话说，这个算法背后的原因是什么？

算法 Haskell Math 函数式编程

评论

2赞 amalloy 7/15/2022
它实际上产生了正确的答案吗？这个问题似乎要求两个数字，而这个表达式当然只产生一个。
2赞 Naitik Mundra 7/15/2022
@amalloy 是的，这是正确答案。请注意，要求是两个系数的乘积，这将产生一个数字。我也在互联网上的其他解决方案中证实了这一点。
1赞 leftaroundabout 7/15/2022
我认为这更像是 maths.se 的问题，而不是 StackOverflow 的问题。
0赞 chi 7/15/2022
确实是一个神秘的解决方案。也许其他语言也使用了相同的算法，也许有人在用这些其他语言编写解决方案时写下了为什么这实际上有效。（胡思乱想，但是......也许您可以尝试搜索其他语言的解决方案？
2赞 Mark Dickinson 7/15/2022
请注意，它给出了介于 和 （包括）之间的所有质值。这意味着对于任何整数，都会给出 和 之间的所有质值。因此，例如，通过获得 的素数输出，因此如果我们从 开始，我们会得到 45 个素数输出。代码只是查找不会溢出 和 上所需边界的最大值。这是推理的简单部分。困难的部分是推理没有其他多项式会做得更好;这就是数论的用武之地。n^2 + n + 41n-4039x(n - x)^2 + (n - x) + 41nx - 40x + 39x = 5-35440xab

答： 暂无答案

上一个：计算两个向量之间顺时针角度的直接方法

下一个：提高超越方程求解的精度