オイラーの素数生成式(Lucky numbers of Euler)

オイラーの素数生成式に関する雑談記事です。


f(n)=n2n+41という式は 1n40 の範囲で異なる40個の素数の値を与えることが知られています。これは「オイラーの素数生成(多項)式」と呼ばれる有名な二次式です。

この多項式によって得られる最初の40個の素数を列挙してみます。

n f(n)
1 41
2 43
3 47
4 53
5 61
6 71
7 83
8 97
9 113
10 131
11 151
12 173
13 197
14 223
15 251
16 281
17 313
18 347
19 383
20 421
21 461
22 503
23 547
24 593
25 641
26 691
27 743
28 797
29 853
30 911
31 971
32 1033
33 1097
34 1163
35 1231
36 1301
37 1373
38 1447
39 1523
40 1601

このようにオイラーの素数生成式は連続して40個もの素数を与えます。n=41 のときは f(41)=412 となって初めて素数でなくなります。

なお、この二次式はゼロ以下の場合でも素数値を与えますが f(n)=f(n+1) なのでnが正のときを考えれば十分です(n2+n+41 を考えることに相当するので重複しています)。


f(n)1n100 の範囲ではその半数以上の86個のnについて素数を与えます。範囲を広げて調べてみると以下の結果を得ます。

範囲 素数を与えるnの個数
1n102 86
1n103 581
1n104 4149
1n105 31985
1n106 261081
1n107 2208197
1n108 19132652

この結果から、1n10k の範囲で素数を与えるnの個数をN(k)と置くと、N(k)e2.0918k100.9084kという関係式が得られます。これは下図に示したklog10N(k)の間に成り立つ直線関係から求めたものです(青色折れ線はlog10N(k)のプロット、橙色破線は原点を通る近似直線)。

図.klog10N(k)の直線関係

ここまで多くの素数値を与えるのは定数項が41の場合に特有の性質と言えます。例えば n2n+15 の場合、1n103 の範囲で素数を与える整数nは68個しかありません。

fq(n)=n2n+q と置くとき、f15(n)が素数になるnの個数を調べると以下のようになり、f41(n)に比べて明らかに少ない結果を得ます。

範囲 f15(n)が素数になるnの個数
1n102 11
1n103 68
1n104 470
1n105 3634
1n106 29525
1n107 249551
1n108 2162730

qを素数としてf13(n)を調べても、q=41 の場合ほどは多くありません。

範囲 f13(n)が素数になるnの個数
1n102 19
1n103 126
1n104 885
1n105 6850
1n106 55791
1n107 472233
1n108 4092968

試しに多項式 fq(n)=n2n+q について q の値を11000までで色々変え、1n105 の範囲で素数を与えるnの個数を調べてみると、上位10位は下の表のようになります。

q 素数を与えるnの個数
41 31985
941 25445
671 25290
107 25162
227 24658
101 24549
221 24305
881 24270
857 23911
587 23786

q=41 のときに飛び抜けて多いという結果になりました。

多項式fq(n)について、q235111741のとき、1nq1 の自然数を代入すると素数になることが知られており、これらの素数をまとめて “Lucky numbers of Euler”「オイラーの幸運数」と呼びます。しかし、q=41 の場合について、より大きなnについてもf(n)が多数の素数値を与えることはあまり知られていないように思います。

きいねく氏によれば、ウラムの螺旋に類するfq(n)のプロットを描くと以下のようになるそうです。q=41 の場合は特に黒く塗り潰されており、より広範囲のnについても素数になっていることが視覚的に理解できます。これはなかなか興味深い性質です。

定数項qが特定の数の場合に多項式fq(n)が多数の素数を与える現象は「ヘーグナー(Heegner)数」との関係が深いことが背景にありますが、難解なのでここでは詳しく立ち入りません。興味のある方はtsujimotter氏の「オイラーの素数生成多項式の秘密」のページを参考にして下さい。2次体、類数、ラビノヴィッチの定理などについても併せて調べてみると良いでしょう。


2020年の奈良教育大学の入試に次のような問題が出題されています。

 

以下の問に答えよ。

(1)nを自然数とするとき、n3+2n3の倍数であることを証明せよ。

(2)次の命題が真または偽であることを示せ。

nを自然数とするとき、n2n+41は素数である。」

2020年奈良教育大学 前期(数学教育専修) 第1問

 
(2)の式はまさにオイラーの素数生成式そのもので、n=41 を代入すれば命題が偽であることが示されます。

昔、慶応大学の数学に多項式f(n)がすべての整数nについて素数ならf(n)は定数関数であることを証明させる問題が出題されていたと記憶しています。この事実を何となく知っているだけでも二次式が常に素数になることは無さそうだと判断できます。一方でnを自然数としてn2n+41という形で表せる素数(オイラー素数)が無数に存在するかどうかは知られていない(恐らく無数に存在するでしょうが証明されていない)ように思います。


また、過去には国際数学オリンピック(IMO)にもオイラーの素数生成式が登場したことがあります。

 

Let n2 be an integer. Prove that if k2+k+n is prime for all integers k such that 0kn3, then k2+k+n is prime for all integers k such that 0kn2.

IMO 1987, Day 2, Problem 6(キューバ大会)

 
本問は「nを自然数として f(k)=k2+k+n と置くとき、f(0),f(1),,f([n3])がすべて素数であれば、f(0),f(1),f(n2)はすべて素数であることを示せ。」と読み替えられます。

k2+k+n が合成数になるような[n3]以上 n2 以下の整数kが存在するとして、f(k)を割り切るような最小の素数pを仮定して矛盾を導く、という方法で証明されます。

これを定理として使えば、例えば k2+k+11 について、f(0)f(1)f(2)f(3)が素数になるので残りのf(4)f(9)も素数になることが従います。また、k2+k+13 の場合は f(1)=15 となり素数でないので素数生成式に該当しないことが直ちに分かります。


ところで、41241+41=412 45245+41=2021=43×47 50250+41=2491=47×53となりますが、これらの素因数はいずれもf41(n)の素数値として得られるものであり、ここから何らかの規則性が見出せそうにも思われます。

しかし、f41(82)=6683=41×163となりf41(n)の値として登場しない素因数163が現れるので、これは単なる思い違いのようです。

そもそもf41(n)=n2n+41から得られる整数を素因数分解したときに41未満の素因数が現れることはないので、小さめのnに対してf41(n)が与える素数値とf41(n)の素因数分解に現れる素数が少し似ているように見える、というだけのことです。

なお、下線部の事実は各素数を法とする剰余類を調べることで示されます。素数pについてf(n+p)f(n)(modp)となるので 1np の範囲で調べれば十分です。いま、1n40 の範囲のすべての整数nに対してf41(n)41以上の素数となるので、f41(n)40以下の素数pで割り切れることはありません。したがって、任意の整数nに対してf41(n)41未満の素因数を含むことはありません。当然ですが、素数だけでなく240までの整数についても同様にf41(n)を割り切らないことが言えます。


(参考:素数一覧表

“オイラーの素数生成式(Lucky numbers of Euler)” への2件の返信

  1. 「f[41](n)=n^2-n+41の値に41未満の素因数が現れることはない」
    ことを示すには,
    「各素数を法とする剰余類を調べる」わけですが,
    その手続きは,(個別に1つずつ行うとすればかなり大変ですが,そうでなければ)
    さほど煩雑な計算はしないで完結しますし,
    明記しておく方がよさそうな気がします.

    言わずもがなですが,以下のようになりますね.

    [1]
    f[41](n) (n=0,1,2,…,40)はすべて素数であり,41未満のものはないので,
    どれも,41未満の素数pで割った余りは0ではない.

    [2]
    f[41](n+p)とf[41](n)は,pで割った余りは等しい.
    よって,nをpで割った余りが定まれば,f[41](n)をpで割った余りは定まる.

    [3]
    p<41だから,任意の自然数は,
    0,1,2,…,40の少なくとも1つとpで割った余りが等しい.

    以上[1],[2],[3]より,f[41](n)は,41未満の素数pで割り切れることはない.

  2. たけちゃん さん

    コメントありがとうございます。

    仰る通り、各素数について個別に論じる必要はありませんね。
    簡単にですが加筆しました。ご指摘ありがとうございます。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です