【Project Euler】Problem 27: 二次式の素数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 27：二次式の素数

原文 Problem 27: Quadratic primes

問題の要約：$|a|,|b|<1000$のとき$n^2+an+b$が$n=0,1,2,3,\dots $のとき連続して素数となる最長の時の$a,b$の積を求めよ

まずは全探索で答えを探してみます。すべての$|a|,|b|<1000$で連続する素数の数を求めて最長のものの[連続素数の数、a, b, a*b]を出力します。結果は連続素数が71となりました。

import itertools
from sympy import isprime

N = 1000
maxConsPrimes = [0,0,0,0]
AB = range(-N, N)
for a, b in itertools.product(AB,repeat=2):
  consPrimes = 0
  for n in range(0,81):
    qf = n**2 + a*n + b
    if not isprime(qf): break
    else:
      consPrimes += 1
  if consPrimes > maxConsPrimes[0]:
    #print(f"a = {a}, b = {b}, {consPrimes}")
    maxConsPrimes = [consPrimes, a, b, a*b]
print(maxConsPrimes)

オイラーの素数生成式のトリック

ここで疑問に思えるのが元のオイラーの素数生成式$n^2\pm n+41$は39個($-$の時は40個)で最長だと思われているのに、簡単に80個や71個の式が見つかるのはへんだと思いませんか？

これにはトリックがあります。$x^2+x+41$は2次関数なのでグラフに描くと$x=-1/2$を軸に左右対象の放物線です。したがって$x=0,1,2,3,\dots $で$y$の値が素数になるということは$x=-1,-2,-3,-4\dots $で同じ値の素数になるということになります。

したがってこのグラフを右方向にスライドさせると左半分の部分が$x>0$の領域に入ってくるので見かけ上、連続素数が増えるということです。

グラフを右に$m$だけスライドさせた式$S(m)$は。

\begin{align}
&S(m)=(x-m)^2+(x-m)+41 \\
&=x^2-(2m-1)x+m^2-m+41\\ \\

&この時の連続素数の数P(m)は \\
&P(0)=39なので \\
&P(m)=m+39 (m\leq 40) \\
&となりそうです。\\　\\

&最大のP(40)=79となるのは　\\　

&S(40)=x^2-(2\times40-1)x+40^2-40+41 \\
&= x^2-79x+1601 \\
&となり例題の式と一致します
\end{align}

ここで問題に戻ると$|b|<1000$から

\begin{align}
&m^2-m+41<1000 \\
&となる最大のmは31になるので \\
&a = -(2 \times 31 - 1) = -61 \\
&b = 31^2-31+41 = 971 \\
&となり解答が筆算で得られました。
\end{align}

（開発環境：Google Colabと筆算）