１．はじめに

その昔、数学者のオイラーは素数を表す次のような2次の多項式を見つけました。
f(x)=x^2+x+41でx=0〜40のf(x)の値が連続して全て素数になると言うことです。
電卓もコンピュータも無い時代に、手計算で見つけるなんて、信じられません。

今ではコンピュータで自由に何桁でも計算できますから、次の疑問は3次多項式で
オイラーと同じような結果が得られないだろうか？、となるでしょう。
そこで、情報を集めてみると既にある程度結果が得られている事がわかりました。

f(x)=a*x^3+b*x^2+c*x+dとして、x:0〜kの範囲の全てのxに対し素数となるf(x)を探索する。

a    b    c      d    T  N  P  D  

1 - 35  308     73   29  0 29 25 
3 -183 3318 -18757   47 32 15 43 
                   
Ｔ：f(x)が素数となる総件数
Ｎ：f(x)<0となる件数
Ｐ：f(x)>0となる件数
Ｄ：重複する素数を除いた件数
（参照：The Prime puzzles & problems connection, Puzzle 232. Primes and Cubic polynomials)
        http://www.primepuzzles.net

現在求められているのは、N=0でD>25の多項式とd>43の多項式と言う事になります。
それで、上記条件の多項式を早速探索する事にしました。



2.探索方法

最初はBasicでプログラムを作成したのですが、処理時間がかかり過ぎて駄目でした。
それで、Ｃ言語でプログラムを作成する事にしました。
多項式の係数a,b,c,dを決定するために、単純に考えると4重ループの組み合わせになります。
処理時間を短くするために次のような工夫をしました。

a.係数dに素数表を使う

　f(0)=dで、dは素数でなければならないので、予め素数表を作成しておいて
　dの値はは素数表を参照するようにした。

b.素数の判定にFermatの小定理を使う
　f(x)の値が素数かどうかは、2^(f(x)-1) ≡ 1 mod f(x)　を満たさないとき合成数とした。
　Fermatの小定理の対偶：2^(f(x)-1) ≡ 1 mod f(x)　を満たさないとき、f(x)は素数ではない。
　しかし、2^(f(x)-1) ≡ 1 mod f(x)　満たされた時は、ほとんどの場合素数なので素数候補とする。

c.2^(f(x)-1) ≡ 1 mod f(x)　のべき乗計算方法
　べき指数を2進展開して、所謂繰り返し２乗計算を行い演算回数を少なくした。





3.探索結果


プログラムを実行させたところ、次の様な結果が得られました。
N=0でd > 25については、記録を更新出来たと思います。

a    b     c      d      T   N    P   D
2  -28 -2334  46153     36   0   36  36   

2  -22 -2384  43793     35   0   35  35

2  -16 -2422  41389     34   0   34  34

2  -10 -2448  38953     33   0   33  33

2   -4 -2462  36497     32   0   32  32

2    2 -2464  34033     31   0   31  31

2    8 -2454  31573     30   0   30  30