第1種カニンガム鎖について調べてみた。どのくらい長くなるの？
経緯など
最近、こんな疑問が浮かびました。
$p$が素数、$2p+1$も素数、$2(2p+1)+1$も素数、$2(2(2p+1)+1)+1$も素数…といった具合で、2を掛けて1を足して素数を生成していく列は、どのくらい続くものなのか？
例1
$2$は素数
$5(=2\cdot 2+1)$は素数
$11(=2\cdot 5+1)$は素数
$23(=2\cdot 11+1)$は素数
$47(=2\cdot 23+1)$は素数
$95(=2\cdot 47+1)$は合成数
となるので、$2$からスタートすると、$2,5,11,23,47$で素数の列が止まります（長さ$5$）。例2
$3$は素数
$7(=2\cdot 3+1)$は素数
$15(=2\cdot 7+1)$は合成数
となるので、$3$からスタートすると、$3,7$で素数の列が止まります（長さ$2$）。
少し調べてみたところ、このような列は第1種カニンガム鎖と言うそうです。知らなかった！
参考： Cunningham Chain
今回は、この第1種カニンガム鎖について、プログラミングしながら、色々と調べてみました。
※第2種カニンガム鎖も存在しており、こちらは「2を掛けて1を引く」のだそうです。今回の記事では、第1種カニンガム鎖のみをテーマに調べていきます。
第1種カニンガム鎖の長さは有限
「第1種カニンガム鎖、どのくらい続くものなのかな～」という当初の疑問についてですが、「無限には続かない」ということは既に知られています。
初項$p_1$、漸化式$p_{n+1}=2p_n+1 \quad (n=1,2,3,4,\cdots)$で定められた数列$\{p_n\}$について、以下が成り立つ。
- $p_1=2$であるとき、$p_6$は合成数
- $p_1$が奇素数であるとき、$p_{p_1}$は合成数
[1]$p_1=2$のとき
$$
p_2=5,\ p_3=11,\ p_4=23,\ p_5=47,\ p_6=95
$$
となるため、$p_6$は合成数である。
[2]$p_1$が奇素数であるとき
$$
p_{n+1}=2p_n+1
$$
より
$$
p_{n+1}+1=2(p_n+1)
$$
となる。
数列$\{p_n +1\}$は初項$p_1+1$、公比$2$の等比数列なので
$$
p_n + 1=2^{n-1}(p_1+1)
$$
である。よって、$1$以上の全ての整数$n$について
$$
p_n = 2^{n-1}p_1+2^{n-1}-1\ \cdots (1)
$$
が成り立つ。
ここで、$2$と$p_1$は互いに素なので、フェルマーの小定理より
$$
2^{p_1-1} \equiv 1 \pmod{p_1}
$$
である。よって
$$
2^{p_1-1}-1 \equiv 0 \pmod{p_1}\ \cdots (2)
$$
が成り立つ。
(1)(2)より、$n=p_1$のとき、$p_{p_1} \equiv 0 \pmod{p_1}$であることがわかる。
$p_{p_1} \not = p_1$なので、$p_{p_1}$は合成数である。
第1種カニンガム鎖を具体的に求めてみよう。
目標：
- （家庭用のパソコンだけど）できるだけ長いものを見つけたい
- 長さの傾向を知りたい
使用した言語： Julia
使用したパッケージ： Primes.jl
以下、開始する素数（初項）を$p$とします。
$p < 10^3$
$p < 10^3$で長さ2以上の第1種カニンガム鎖を具体的に見てみることにします。
[2, 5, 11, 23, 47]
[3, 7]
[5, 11, 23, 47]
[11, 23, 47]
[23, 47]
[29, 59]
[41, 83, 167]
[53, 107]
[83, 167]
[89, 179, 359, 719, 1439, 2879]
[113, 227]
[131, 263]
[173, 347]
[179, 359, 719, 1439, 2879]
[191, 383]
[233, 467]
[239, 479]
[251, 503]
[281, 563]
[293, 587]
[359, 719, 1439, 2879]
[419, 839]
[431, 863]
[443, 887]
[491, 983]
[509, 1019, 2039, 4079]
[593, 1187]
[641, 1283]
[653, 1307]
[659, 1319]
[683, 1367]
[719, 1439, 2879]
[743, 1487]
[761, 1523]
[809, 1619]
[911, 1823]
[953, 1907]
$p < 10^3$で、各長さの第1種カニンガム鎖の個数は以下です。
- 長さ1：131
- 長さ2：28
- 長さ3：3
- 長さ4：3
- 長さ5：2
- 長さ6：1
$p < 10^3$では、[89, 179, 359, 719, 1439, 2879]が最長で長さ6でした。
$p < 10^4$
$p < 10^4$で、各長さの第1種カニンガム鎖の個数は以下です。
- 長さ1：1039
- 長さ2：149
- 長さ3：30
- 長さ4：8
- 長さ5：2
- 長さ6：1
$p < 10^4$でも、[89, 179, 359, 719, 1439, 2879]が最長で長さ6でした。
$p < 10^5$
$p < 10^5$で、各長さの第1種カニンガム鎖の個数は以下です。
- 長さ1：8421
- 長さ2：966
- 長さ3：168
- 長さ4：29
- 長さ5：6
- 長さ6：2
$p < 10^5$では、
[89, 179, 359, 719, 1439, 2879]
[63419, 126839, 253679, 507359, 1014719, 2029439]
が最長で長さ6でした。
$p < 10^6$
$p < 10^6$で、各長さの第1種カニンガム鎖の個数は以下です。
- 長さ1：70752
- 長さ2：6559
- 長さ3：1028
- 長さ4：126
- 長さ5：28
- 長さ6：5
$p < 10^6$では、
[89, 179, 359, 719, 1439, 2879]
[63419, 126839, 253679, 507359, 1014719, 2029439]
[127139, 254279, 508559, 1017119, 2034239, 4068479]
[405269, 810539, 1621079, 3242159, 6484319, 12968639]
[810809, 1621619, 3243239, 6486479, 12972959, 25945919]
が最長で長さ6でした。
$p < 10^7$
$p < 10^7$で、各長さの第1種カニンガム鎖の個数は以下です。
- 長さ1：608547
- 長さ2：48556
- 長さ3：6584
- 長さ4：702
- 長さ5：145
- 長さ6：42
- 長さ7：3
$p < 10^7$では、
[1122659, 2245319, 4490639, 8981279, 17962559, 35925119, 71850239]
[2164229, 4328459, 8656919, 17313839, 34627679, 69255359, 138510719]
[2329469, 4658939, 9317879, 18635759, 37271519, 74543039, 149086079]
が最長で長さ7でした。
$p < 10^8$
$p < 10^8$で、各長さの第1種カニンガム鎖の個数は以下です。
- 長さ1：5338315
- 長さ2：373702
- 長さ3：44427
- 長さ4：4068
- 長さ5：771
- 長さ6：149
- 長さ7：20
- 長さ8：2
- 長さ9：1
$p < 10^8$では、
[85864769, 171729539, 343459079, 686918159, 1373836319, 2747672639, 5495345279, 10990690559, 21981381119]
が最長で長さ9でした。
見つけられた長さ9のもの
[85864769, 171729539, 343459079, 686918159, 1373836319, 2747672639, 5495345279, 10990690559, 21981381119]
[198479579, 396959159, 793918319, 1587836639, 3175673279, 6351346559, 12702693119, 25405386239, 50810772479]
[305192579, 610385159, 1220770319, 2441540639, 4883081279, 9766162559, 19532325119, 39064650239, 78129300479]
[2400025739, 4800051479, 9600102959, 19200205919, 38400411839, 76800823679, 153601647359, 307203294719, 614406589439]
[7606886429, 15213772859, 30427545719, 60855091439, 121710182879, 243420365759, 486840731519, 973681463039, 1947362926079]
[7755909149, 15511818299, 31023636599, 62047273199, 124094546399, 248189092799, 496378185599, 992756371199, 1985512742399]
この辺りまで計算して「長いものを見つけるのは、かなり大変そうだ…」と思いました。桁が増えると、1日～2日計算させても、我が家のパソコンでは計算が終わってませんでした…。素数判定って、大変なんですね。
発見されている長いもの（2021年現在）
以下のページに記録が掲載されています。
Cunningham Chain records (2021/2/25参照)
上記ページによると、2008年にJaroslaw Wroblewskiが2759832934171386593519 (22桁)から開始する第1種カニンガム鎖(長さ17)を発見しているようです。
今回、私が家のパソコンで計算できた「長さ9の第1種カニンガム鎖の最小の初項は85864769」は、上記ページによると、1989年に計算されていたようです。30年前～！
カニンガム鎖に関連した未解決問題
以下は未解決のようです。
任意の正の整数$k$に対し、長さ$k$のカニンガム鎖は無限に存在する。
例えば「長さ2の第1種カニンガム鎖が無限に存在する」ことだけでも証明できれば、ソフィー・ジェルマン素数と安全素数が無限に存在することが言えますね…。
仮想通貨に使われているらしい
カニンガム鎖は仮想通貨に使われているらしいです。
About Primecoin (2021/2/25参照)
上記Primecoinのページによると
"Primecoin network searches for special prime number chains known as Cunningham chains and bi-twin chains."
とのことです。仮想通貨の仕組みを学んでみたくなりました！
感想
「長いもの、全然見つからない！」というのが率直な感想でした。工夫してプログラミングすると家庭用パソコンでも、もっと色々できるんですかね？
また、計算したり調べたりしているうちに「素朴なテーマがゆえの沼」を感じました。
関連記事：