10
大学数学基礎解説
文献あり

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

981
0
$$$$

経緯など

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

$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."

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

感想

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

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

関連記事:

参考文献

投稿日:202131

この記事を高評価した人

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

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

バッジはありません。

投稿者

みぽ
みぽ
144
21904
今日もねこがかわいい。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中