2次の素数生成公式について考えます。

n^2+n+41についてはn=0から39まで素数であることがわかります。

ところが、2015年に読者の方から

「n^2+n+kがn=0〜k-2のとき素数になるには、0≦n≦√(k/3)のとき素数になることが必要十分だとわかっているようです．」

という情報をいただいきました

この性質により効率的な判定が可能となります。

n^2+n+11についてはn=0,1について素数であることを確かめればn=0から9まで素数であることがわかります。

n^2+n+41についてはn=0,1,2,3について素数であることを確かめればn=0から39まで素数であることがわかります。

　これが正しいことを確認するのは簡単ですが，それ以来、時々この問題を思い出しては証明を試みては跳ね返されてきた。

この問題が数学オリンピック(1987)の問題であることを知ったのは2021年のことだった。

数学オリンピックの中でも難問に属する問題なのだそうですが、実は初等的に証明できるのだそうである。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　an=n^2+n+k

　a0,a1,a2,・・・,ak-2に一つでも素数でなければ矛盾が生ずることを示します。

最初に現れる素数でない数をasとすると、　

a0,a1,a2,・・・,as-1は素数、asは素数でない。最も小さい素因数をｐとすると

as=s^2+s+k=p・q・r・・・

as=s^2+s+k≧p^2

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

a0,a1,a2,・・・,as-1は素数であるが、このなかにｐが出てくるかどうかを分析する

as-a0,as-a1,・・・,as-as-1

as-an=s^2+s-n^2-n=(s-n)(s+n+1)より

as-a0=s(s+1)

as-a1=(s-1)(s+2)

as-a2=(s-2)(s+3)

as-as-1=1x2s

ここでp≦2sと仮定すれば因数分解のどこかに素数ｐが顔を出すことになる。

それをatとすると

0≦ｔ≦ｓ-1

as-at=(s-t)(s+t+1)

s-t=pまたはs+t+1=p

as-atはｐの倍数となり、もともとasはｐの倍数ですから、atもｐの倍数。

atは素数ですから、atはｐそのもの。

したがって、at=t^2+t+k=p

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

-1＜t^2,ｓ≦ｋ-2なので、s+t+1＜t^2+t+k=p

s-t＜s+t+1＜ｐとなって、矛盾。仮定p≦2sがまずかったことになる。

したがって、2ｓ+1≦ｐ・・・これが0≦n≦√(k/3)、n^2+n+kは素数に引っかかることになる。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

s^2+s+k≧p^2≧(2s+1)^2=4s^2+4s+1

k≧3s^2+3s+1

s=√(k/3)とおくと3s^2+3s+1＞ｋとなるから

s≦√(k/3)であるが、asは素数になってしまい、仮定に反する。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

[参]小島寛之「数学オリンピック問題にみる現代数学」講談社ブルーバックス

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝