第1種カニンガム鎖について調べてみた。どのくらい長くなるの？

経緯など
第1種カニンガム鎖の長さは有限
第1種カニンガム鎖を具体的に求めてみよう。
$p < 10^{3}$
$p < 10^{4}$
$p < 10^{5}$
$p < 10^{6}$
$p < 10^{7}$
$p < 10^{8}$
見つけられた長さ9のもの
発見されている長いもの（2021年現在）
カニンガム鎖に関連した未解決問題
仮想通貨に使われているらしい
感想
参考文献

大学数学基礎解説

文献あり

第1種カニンガム鎖について調べてみた。どのくらい長くなるの？

初等整数論,素数,カニンガム鎖

1122

経緯など

最近、こんな疑問が浮かびました。

$p$ が素数、 $2 p + 1$ も素数、 $2 (2 p + 1) + 1$ も素数、 $2 (2 (2 p + 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} = 2 p_{n} + 1 (n = 1, 2, 3, 4, \dots)$ で定められた数列 ${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} = 2 p_{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 \dots (1)$
が成り立つ。
ここで、 $2$ と $p_{1}$ は互いに素なので、フェルマーの小定理より
$2^{p_{1} - 1} \equiv 1 (\mod p_{1})$
である。よって
$2^{p_{1} - 1} - 1 \equiv 0 (\mod p_{1}) \dots (2)$
が成り立つ。
(1)(2)より、 $n = p_{1}$ のとき、 $p_{p_{1}} \equiv 0 (\mod p_{1})$ であることがわかる。
$p_{p_{1}} \neq 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."

とのことです。仮想通貨の仕組みを学んでみたくなりました！

感想

「長いもの、全然見つからない！」というのが率直な感想でした。工夫してプログラミングすると家庭用パソコンでも、もっと色々できるんですかね？

また、計算したり調べたりしているうちに「素朴なテーマがゆえの沼」を感じました。

参考文献

[1]

Cunningham Chain records, 閲覧日 2021年3月1日, http://primerecords.dk/Cunningham_Chain_records.htm

投稿日：2021年3月1日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

みぽ

163

32744