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

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

1077
0

経緯など

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

pが素数、2p+1も素数、2(2p+1)+1も素数、2(2(2p+1)+1)+1も素数…といった具合で、2を掛けて1を足して素数を生成していく列は、どのくらい続くものなのか?

  • 例1
    2は素数
    5(=22+1)は素数
    11(=25+1)は素数
    23(=211+1)は素数
    47(=223+1)は素数
    95(=247+1)は合成数
    となるので、2からスタートすると、2,5,11,23,47で素数の列が止まります(長さ5)。

  • 例2
    3は素数
    7(=23+1)は素数
    15(=27+1)は合成数
    となるので、3からスタートすると、3,7で素数の列が止まります(長さ2)。

少し調べてみたところ、このような列は第1種カニンガム鎖と言うそうです。知らなかった!

参考: Cunningham Chain

今回は、この第1種カニンガム鎖について、プログラミングしながら、色々と調べてみました。

※第2種カニンガム鎖も存在しており、こちらは「2を掛けて1を引く」のだそうです。今回の記事では、第1種カニンガム鎖のみをテーマに調べていきます。

第1種カニンガム鎖の長さは有限

「第1種カニンガム鎖、どのくらい続くものなのかな~」という当初の疑問についてですが、「無限には続かない」ということは既に知られています。

初項p1、漸化式pn+1=2pn+1(n=1,2,3,4,)で定められた数列{pn}について、以下が成り立つ。

  • p1=2であるとき、p6は合成数
  • p1が奇素数であるとき、pp1は合成数

[1]p1=2のとき
p2=5, p3=11, p4=23, p5=47, p6=95
となるため、p6は合成数である。

[2]p1が奇素数であるとき
pn+1=2pn+1
より
pn+1+1=2(pn+1)
となる。
数列{pn+1}は初項p1+1、公比2の等比数列なので
pn+1=2n1(p1+1)
である。よって、1以上の全ての整数nについて
pn=2n1p1+2n11 (1)
が成り立つ。
ここで、2p1は互いに素なので、フェルマーの小定理より
2p111(modp1)
である。よって
2p1110(modp1) (2)
が成り立つ。
(1)(2)より、n=p1のとき、pp10(modp1)であることがわかる。
pp1p1なので、pp1は合成数である。

第1種カニンガム鎖を具体的に求めてみよう。

目標:

  • (家庭用のパソコンだけど)できるだけ長いものを見つけたい
  • 長さの傾向を知りたい

使用した言語: Julia

使用したパッケージ: Primes.jl

以下、開始する素数(初項)をpとします。

p<103

p<103で長さ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<103で、各長さの第1種カニンガム鎖の個数は以下です。

  • 長さ1:131
  • 長さ2:28
  • 長さ3:3
  • 長さ4:3
  • 長さ5:2
  • 長さ6:1

p<103では、[89, 179, 359, 719, 1439, 2879]が最長で長さ6でした。

p<104

p<104で、各長さの第1種カニンガム鎖の個数は以下です。

  • 長さ1:1039
  • 長さ2:149
  • 長さ3:30
  • 長さ4:8
  • 長さ5:2
  • 長さ6:1

p<104でも、[89, 179, 359, 719, 1439, 2879]が最長で長さ6でした。

p<105

p<105で、各長さの第1種カニンガム鎖の個数は以下です。

  • 長さ1:8421
  • 長さ2:966
  • 長さ3:168
  • 長さ4:29
  • 長さ5:6
  • 長さ6:2

p<105では、
[89, 179, 359, 719, 1439, 2879]
[63419, 126839, 253679, 507359, 1014719, 2029439]
が最長で長さ6でした。

p<106

p<106で、各長さの第1種カニンガム鎖の個数は以下です。

  • 長さ1:70752
  • 長さ2:6559
  • 長さ3:1028
  • 長さ4:126
  • 長さ5:28
  • 長さ6:5

p<106では、
[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<107

p<107で、各長さの第1種カニンガム鎖の個数は以下です。

  • 長さ1:608547
  • 長さ2:48556
  • 長さ3:6584
  • 長さ4:702
  • 長さ5:145
  • 長さ6:42
  • 長さ7:3

p<107では、
[1122659, 2245319, 4490639, 8981279, 17962559, 35925119, 71850239]
[2164229, 4328459, 8656919, 17313839, 34627679, 69255359, 138510719]
[2329469, 4658939, 9317879, 18635759, 37271519, 74543039, 149086079]
が最長で長さ7でした。

p<108

p<108で、各長さの第1種カニンガム鎖の個数は以下です。

  • 長さ1:5338315
  • 長さ2:373702
  • 長さ3:44427
  • 長さ4:4068
  • 長さ5:771
  • 長さ6:149
  • 長さ7:20
  • 長さ8:2
  • 長さ9:1

p<108では、
[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
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。
バッチを贈って投稿者を応援しよう

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

投稿者

みぽ
みぽ
161
31726
今日もねこがかわいい。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 経緯など
  2. 第1種カニンガム鎖の長さは有限
  3. 第1種カニンガム鎖を具体的に求めてみよう。
  4. p<103
  5. p<104
  6. p<105
  7. p<106
  8. p<107
  9. p<108
  10. 見つけられた長さ9のもの
  11. 発見されている長いもの(2021年現在)
  12. カニンガム鎖に関連した未解決問題
  13. 仮想通貨に使われているらしい
  14. 感想
  15. 参考文献