Haskell Wiki中Project Euler第27题解法的原理解析

问题背景 #

• 近期通过练习Project Euler题目提升Haskell编程能力，每完成一题通常会查阅Haskell Wiki上的对应题解。
• 完成第27题时，最初采用常规方案实现：组合isPrime函数与map遍历求解，之后在Wiki上看到一份完全无法理解的极简题解，仅能找到一篇已关闭的相关讨论帖，没有获得清晰解释。

题解代码如下：

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，对应题目中系数绝对值不超过1000的约束
2. 从自然数序列中找到第一个满足x² - x + 41 > n的数，记为m
3. 计算a = m - 1
4. 最终输出的-(2a-1) * (a² - a + 41)即为题目要求的两个系数的乘积

该算法不需要遍历校验素数就能直接输出正确结果，核心逻辑依托已被证明的数论结论。

核心数学推导 #

这个解法的核心是欧拉发现的经典素数生成多项式性质：

多项式 f(k) = k² - k + 41 对k取0到40的所有整数时，输出结果全为素数，是目前已知连续素数生成长度最长的二次多项式之一。

题目要求找整数a、b满足|a|<1000、|b|≤1000，使得从n=0开始n² + a n + b能生成最多的连续素数。我们可以对欧拉的素数多项式做平移变形，匹配题目要求的二次式结构：
令k = n + t（t为整数），代入原多项式展开：

f(n+t) = (n+t)² - (n+t) + 41
       = n² + (2t - 1)n + (t² - t + 41)

展开后的式子刚好匹配题目要求的n² + a n + b结构，对应关系为：

• a = 2t - 1
• b = t² - t + 41

要让这个变形后的多项式生成最长的连续素数，就要让b尽可能大但不超过题目约束的1000，同时保证从n=0开始的取值尽可能落在原多项式的素数区间内：

1. 先找最小的整数m使得m² - m + 41 > 1000，解二次不等式可得m=32（代入验证：31²-31+41=971≤1000，32²-32+41=1033>1000）
2. 取t = m-1 =31，对应b=971，满足|b|≤1000的约束
3. 要让连续素数序列最长，需要取a为负系数，即a = -(2t -1) = -61，此时多项式为n² -61n +971，从n=0开始可以连续生成71个素数，是约束范围内的最优解
4. 题目最终要求输出a和b的乘积，即-61 * 971 = -59231，和代码计算结果完全一致。

数论上已经证明，在|a|、|b|≤1000的约束范围内，不存在任何二次多项式生成的连续素数长度超过上述变形得到的多项式，因此不需要做任何素数遍历校验，直接通过数学推导就能得到结果。

内容的提问来源于stack exchange，提问作者Naitik Mundra