Haskell Wiki 中的 Project Euler Problem 27 的解决方案是如何工作的？

Question

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

对于问题27，我用常规方式解决了它，即使用

isPrime

和

map

的组合。但后来，我在维基上看到了这个解决方案。我不知道这个解决方案是如何工作的。我发现的唯一提到它的是来自数学堆栈交换上的this封闭线程。

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)：（我认为这意味着两者都是系数。）

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

Answer 1

请注意

(n-x)^2 + a(n-x) + b = n^2 + (a-2x)n + x^2 - ax + b

这意味着变量的变化可以将任何（整数系数）二次方程转变为 n^2+d 或 n^2+n+d 形式之一，并明智地选择 x。现在第一种形式不好：所有其他项都是偶数，所以我们不能有很长的素数。对于第二种形式的二次方程，拉宾诺维茨证明了产生最大素数序列的二次方程必须有 4d-1 个 Heegner 数，其中只有 6 个。从那里可以很快检查 n^2+n+ 41 是这 6 个中最好的，次佳 n^2+n+17 产生的连续素数总数（即正输入和负输入）比 n^2+n+41 从 0 开始产生的连续素数更少。

现在，(-1-n)^2+(-1-n)+41 = n^2+n+41，所以如果 n 产生素数，那么 -1-n 也会产生素数。这意味着该二次方程产生的连续素数大约有一半是由负输入产生的，因此我们可以在不超出系数预算的情况下将其移入范围内的素数越多越好；而且，更重要的是，我们不能比尝试移动更多值更好，因为移动任何其他多项式得到的连续素数比我们移动这个多项式之前要少。

我们的预算是多少？好吧，回顾我们的第一个方程，现在 a=1 和 b=41，我们必须有：

|1-2x| < 1000
|x^2-x+41| < 1000

因为这是最后的两个系数。第二个将是我们的限制器，因为 x^2 通常比 2x 增长得快得多，所以我们只是寻找验证该方程的最大 x。这就是

m = head $ filter (\x -> x ^ 2 - x + 41 > n) [1 ..]
a = m-1

片段确实如此。一旦我们有了这个，1-2x 和 x^2-x+41 就是我们的两个系数，我们想要计算它们的乘积，这就是

-(2 * a - 1) * (a ^ 2 - a + 41)

片段确实如此。