奇素数の抜け穴
奇素数Pがそれより小さい素数pと自然数kを用いて
P=p+k*(k+1)/2
の形式で表せるものを探すと
3=2+1*2/2
5=2+2*3/2
････
13=3+4*5/2
(7+3*4/2も可能)
････
31=3+7*8/2
････
97=19+12*13/2
(31+11*12/2,61+8*9/2も可能)
････
の様にP,pの間でk*(k+1)/2の繋がりが構成されてくる。
ところで、いくら頑張ってもその構成が見つからない奇素数Pが存在していますが
それは何でしょうか？
7と61かな？
(追記)
プログラムを作って調べたら、211も該当していました。
GAI様、らすかる様、こんにちは。
＞P=p+k*(k+1)/2
というと
P=p+(1+2+3+・・・+k)
ということですか？
この3個以外に見当たらないのが面白かったです。
Pが大きくなっていくと、構成できる場合の可能性が圧倒的に増大していくのでこれ以上は見つからないのでしょうね。
ミラー・ラビン法のStorong pseudoprimeの発見において
底を2,3,6の３つで調査すれば1～10^8までには
次の21個が発見でき
1373653;[829, 1; 1657, 1]
1530787;[619, 1; 2473, 1]
1987021;[997, 1; 1993, 1]
2284453;[1069, 1; 2137, 1]
3116107;[883, 1; 3529, 1]
5173601;[929, 1; 5569, 1]
6787327;[1303, 1; 5209, 1]
11541307;[1699, 1; 6793, 1]
13694761;[2617, 1; 5233, 1]
15978007;[1999, 1; 7993, 1]
16070429;[1637, 1; 9817, 1]
16879501;[1453, 1; 11617, 1]
25326001;[2251, 1; 11251, 1]
27509653;[3709, 1; 7417, 1]
27664033;[3037, 1; 9109, 1]
28527049;[2389, 1; 11941, 1]
54029741;[1733, 1; 31177, 1]
61832377;[3517, 1; 17581, 1]
66096253;[5749, 1; 11497, 1]
74927161;[6121, 1; 12241, 1]
80375707;[4483, 1; 17929, 1]
同じく底を2,3,7で調査すると次の1個が
2284453;[1069, 1; 2137, 1]
また底を2,3,11でも
2284453 が発見される。
底を2,3,13なら
6787327;[1301,1;5209,1]が出現
ところでP=p+k*(k+1)/2
と構成できなかったタイプ(2を含めて),2,7,61を底にして調査すれば、
一つも擬素数は存在しないことが判明する。
ウィキペディアのミラー-ラビン素数判定法の記事によれば
もし
n<4759123141なら、底を2,7,61について調べればよい。
とある。
n=10^8～10^10では
4759123141;[48781, 1; 97561, 1] が出現してしまう。
これと何かしら関係しているかもと思われました。
