tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

日曜数学アドベントカレンダー初日:2341 はスーパープライム

この記事は 日曜数学 Advent Calendar 2017 の 1 日目の記事です。

アドベントカレンダーの季節が始まりましたね!

2017年も「日曜数学アドベントカレンダー」は健在です!
adventar.org

嬉しいことに,既に投稿予定が全日埋まっております!これは嬉しいですね!みなさんの記事が投稿されるのを楽しみにしております!

2341 争奪戦?

ところでみなさん。アドベントカレンダーを登録している Adventar というサイトですが,各カレンダーに ID がついているのをご存知でしょうか。

URLの

https://adventar.org/calendars/XXXX

の XXXX の部分が ID です。日曜数学アドベントカレンダーは,ID が 2343 となっています。

この ID はカレンダーが作成された順に連番で振られています。

実は,日曜数学アドベントカレンダーでは,毎年密かにこの ID で「面白い数」を狙っていました。たとえば昨年の ID は 1777 で,これが非正則素数と呼ばれる重要な素数なのでした。

そんなわけで今年もよい ID が取れるといいなと思い,周辺の数を Wikipediaの記事「2000」 で探していたのでした。

f:id:tsujimotter:20171201102316p:plain:w360

この辺は割と素数砂漠で,面白い数もそんなにないなぁと思っていたら,しばらく先に 2341 という素数を見つけました。

やったー!しかも,よく見ると「スーパー素数(スーパープライム)」とあります。スーパープライムといえば,素数の中の素数です。これは素晴らしい。とるしかない。


そう思って,この ID が取得できるタイミングを虎視眈々と待っておりました。なかなか新しいカレンダーができなかったので,普段の就寝時間になっても寝ることができず,ID が来るまで寝ずに待っていたのです(たしか2時くらいだったような)。

ID 2340 のカレンダーができ「よし作るぞ!!」と気合を入れたその矢先,なんと「数学カフェさん」に先を越されてしまいました・・・。まさか身内で奪い合うとは。笑

正直なところ,結構悔しかった。。。笑


でもね,ちょっと考えを改めることにしたのです。だって

アドベントカレンダーのIDで,素数を奪い合うなんてすごくないですか?

それもそのはず。今年は「数学系のアドベントカレンダー」がとても多いのです。私のしっている範囲で列挙してみましょう:

2017年の数学系アドベントカレンダー:
数学カフェ Advent Calendar 2017 - Adventar
インテジャーズ Advent Calendar 2017 - Adventar
日曜数学 Advent Calendar 2017 - Adventar
素数大富豪 Advent Calendar 2017 - Adventar
Math Advent Calendar 2017 - Adventar
Category Theory Advent Calendar 2017 - Adventar
数学とコンピュータ Advent Calendar 2017 - Qiita
数学とコンピュータⅡ Advent Calendar 2017 - Qiita
※ほかにもあればぜひ教えてください。

ほかにも私が知らないだけでもっとあるかもしれません。アドベントカレンダーで数学が盛り上がっている,と思わせてくれるような盛況ぶりです。

IDの争奪戦が発生したのも,趣味で数学をする人たちのコミュニティが活発になってきたことの表れなのかな,と思ってちょっぴり嬉しい気持ちになりました。
(数学カフェさん,ネタにしてごめんなさい笑)

2341 は スーパープライム

さて,ここからが本題です。笑

tsujimotter が狙っていた 2341 という素数は,単なる素数ではありません。スーパープライム と呼ばれる素数なのです。

スーパープライムについて調べてみると,INTEGERSという素晴らしいブログを発見しましたので,こちらをご覧ください:
integers.hatenablog.com

簡単に言うと,スーパープライムとは「素数番目の素数」ということになります。2341 は 347 番目の素数で,347 も素数なのでスーパープライムということになります。

素敵な素数ですね!

スーパープライムについての自由研究

ここで自然に気になってくる(かどうかはわかりませんが)のが,「素数番目のスーパープライム」です。これをスーパープライムのスーパープライムということで,

スーパー2プライム

と呼ぶことにしましょう。読み方は「スーパースーパープライム」です。

2341 は 69 番目のスーパープライムなので,残念ながらスーパースーパープライムではありません。

さらに言えば,スーパーnプライム というものも考えたくなるでしょう。

定義:スーパーnプライム
 n を非負整数とし,素数全体の集合を  PRIME としたとき,その部分集合  SP(n) \subset PRIME を次のように再帰的に定義する.

  •  SP(0) = PRIME とする.
  •  SP(n) の元を昇順に並べて  p_1, p_2, p_3, \cdots, p_i, \cdots とする. i が素数であるとき  p_i \in SP(n+1) として, SP(n+1) を得る.

また, n次数と呼ぶ.

定義から容易にわかることですが(というtsujimotterはしばらく気づかなかった), SP({n+1}) SP({n}) の真部分集合になります。

定理
 n を非負整数とすると,
 SP(n+1) \subsetneq SP(n)

が成り立つ.


実際にプログラムを使ってスーパーnプライムを計算してみました。各次数のスーパーnプライムを表にまとめます。

計算の都合上,3,000,000以下の素数に限定して列挙しています。また,紙面の都合もあって各次数で挙げている素数は100件までとしています。

次数  n スーパーnプライム(各次数で最大100件)
02, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547
13, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, 179, 191, 211, 241, 277, 283, 331, 353, 367, 401, 431, 461, 509, 547, 563, 587, 599, 617, 709, 739, 773, 797, 859, 877, 919, 967, 991, 1031, 1063, 1087, 1153, 1171, 1201, 1217, 1297, 1409, 1433, 1447, 1471, 1499, 1523, 1597, 1621, 1669, 1723, 1741, 1787, 1823, 1847, 1913, 2027, 2063, 2081, 2099, 2221, 2269, 2341, 2351, 2381, 2417, 2477, 2549, 2609, 2647, 2683, 2719, 2749, 2803, 2897, 2909, 3001, 3019, 3067, 3109, 3169, 3229, 3259, 3299, 3319, 3407, 3469, 3517, 3559, 3593, 3637, 3733, 3761, 3911, 3943
25, 11, 31, 59, 127, 179, 277, 331, 431, 599, 709, 919, 1063, 1153, 1297, 1523, 1787, 1847, 2221, 2381, 2477, 2749, 3001, 3259, 3637, 3943, 4091, 4273, 4397, 4549, 5381, 5623, 5869, 6113, 6661, 6823, 7193, 7607, 7841, 8221, 8527, 8719, 9319, 9461, 9739, 9859, 10631, 11743, 11953, 12097, 12301, 12547, 12763, 13469, 13709, 14177, 14723, 14867, 15299, 15641, 15823, 16519, 17627, 17987, 18149, 18311, 19577, 20063, 20773, 20899, 21179, 21529, 22093, 22811, 23431, 23801, 24107, 24509, 24859, 25423, 26371, 26489, 27457, 27689, 28109, 28573, 29153, 29803, 30133, 30557, 30781, 31667, 32341, 32797, 33203, 33569, 33967, 35023, 35311, 36887, 37217
311, 31, 127, 277, 709, 1063, 1787, 2221, 3001, 4397, 5381, 7193, 8527, 9319, 10631, 12763, 15299, 15823, 19577, 21179, 22093, 24859, 27457, 30133, 33967, 37217, 38833, 40819, 42043, 43651, 52711, 55351, 57943, 60647, 66851, 68639, 72727, 77431, 80071, 84347, 87803, 90023, 96797, 98519, 101701, 103069, 112129, 125113, 127643, 129229, 131707, 134597, 137077, 145547, 148439, 153877, 160483, 162257, 167449, 171697, 173867, 182261, 195677, 200017, 202001, 204067, 219613, 225503, 234293, 235891, 239489, 243781, 250751, 259657, 267439, 271939, 275837, 280913, 285191, 292489, 304553, 305999, 318211, 321017, 326203, 332099, 339601, 347849, 352007, 357473, 360293, 371981, 380557, 386401, 391711, 396269, 401519, 415253, 418961, 439357, 443419
431, 127, 709, 1787, 5381, 8527, 15299, 19577, 27457, 42043, 52711, 72727, 87803, 96797, 112129, 137077, 167449, 173867, 219613, 239489, 250751, 285191, 318211, 352007, 401519, 443419, 464939, 490643, 506683, 527623, 648391, 683873, 718807, 755387, 839483, 864013, 919913, 985151, 1021271, 1080923, 1128889, 1159901, 1254739, 1278779, 1323503, 1342907, 1471343, 1656649, 1693031, 1715761, 1751411, 1793237, 1828669, 1950629, 1993039, 2071583, 2167937, 2193689, 2269733, 2332537, 2364361, 2487943, 2685911, 2750357, 2779781, 2810191
5127, 709, 5381, 15299, 52711, 87803, 167449, 219613, 318211, 506683, 648391, 919913, 1128889, 1254739, 1471343, 1828669, 2269733, 2364361
6709, 5381, 52711, 167449, 648391, 1128889, 2269733
75381, 52711, 648391, 2269733
852711, 648391
9648391
10(3,000,000以下には存在しない)

10次のスーパープライムは,3,000,000 以下には存在しないのですね。648391 といった数はなかなかスーパーなプライムということですね。覚えたくなってきました。

最初,この表を眺めていたとき,最小値に  2, 3, 5, \cdots と出てきているので「あーなるほど。最小のスーパーnプライムは,素数が順番に出てくるんだな」と思いました。ところが,それは嘘だったことに気づきました。

たしかに, SP(n+1) の最小値は「 SP(n) の2番目に小さい素数」になるので(最小の素数が  2 より)順番に出てくるように思ってしまいますが,それ以降については(当然ですが)順番どおりに出てくるわけではありませんね。

そこで,各  n に対して  SP(n) の最小値が気になりましたので,まとめてみました。

次数最小値
02
13
25
311
431
5127
6709
75381
852711
9648391
10(3,000,000以下には存在しない)

なかなか急激に増加しているのが見てとれるかと思います。実際どのような増加傾向をしているのか気になったので,グラフに書いてみることにしました。

f:id:tsujimotter:20171201110700p:plain:w360

横軸が  n で,縦軸が  SP(n) の最小値です。

もしかしたら指数的に増加しているのかもしれないと思って,縦軸を対数軸にしたのが以下のグラフです。

f:id:tsujimotter:20171201110742p:plain:w360


グラフを見る限りだと,単純な指数関数よりもやや速い速度で増加しているようです。いったいどんな関数で抑えられるのでしょう。

というわけで,こんな問題が気になってきます。

問題:スーパーnプライムの漸近挙動
スーパー ^nプライムの集合を  SP(n) としたとき, \min SP(n) n に対するオーダー  \mathcal{O}(\min SP(n) ) はどのような関数となるか?

もしかしたら,素数定理を使ったヒューリスティックな評価をすれば解決するのかもしれませんが,そこまで考える余裕がなかったのでオープンプロブレムとして残しておきます。よかったらみなさんも考えてみてください。

なかなか楽しい自由研究でした。

最後に,今回使った Ruby のコードを置いておきます。

# coding: utf-8

require 'prime'
# x 以下のスーパー^nプライムを計算します

x = 3000000


sp = []


# 0 次のスーパープライム
sp << []
Prime.each(x) do |p|
	sp[0] << p
end


# n+1 次のスーパープライムを n 次から構成する(10次まで)
10.times do |n|
	sp << []
	sp[n].each_with_index do |p, index|
		if Prime.prime?(index+1)
			sp[n+1] << p
		end
	end
end

# 10 次のスーパープライムまでを表示
puts "\# x = #{x} 以下を探索し,"
puts "10 次のスーパープライムまでを表示(各次数で最大100件)"
sp.each_with_index do |array, n|
	print "\##{n}: "
	puts array[0..100].join(", ")
end

次回予告

mathcafe_japan さんの記事です。私と素数争奪戦をした因縁の相手(笑)ですが,なんと私が取得した「2343 の魅力」を語ってくださるそうなのです。これは楽しみですね!

それでは今日はこの辺で!

追記

intergers_blog さんから以下のページを教えていただきました!まだちゃんと読めていませんがドンピシャでこの記事に関係する話のようです!

Fernandez's Order of Primeness