シェルピンスキー数

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz です。

はじめに

『名前のついた素数コレクション 〜Haskellを添えて〜』のエントリでは、名前のついた素数を取り上げました。その記事を記すために調べていた際に、名前のついた合成数も幾つか見かけましたので、その中から『シェルピンスキー数』『リーゼル数』『ブリエ数』を本稿では紹介しようと思います。これらはどれも、WikiPediaのシェルピンスキー数の項に説明があります。
本稿は、このWikiPediaと「巨大数研究 Wiki¹」にある解説を参考にします。

シェルピンスキー数

シェルピンスキー数には次の２種類があります。

• 第一種シェルピンスキー数：自然数$n$に対して$n^{n}+1$の形式の数
• 第二種シェルピンスキー数：全ての自然数$n$に対して$ k \times 2^{n} + 1 $が合成数となるような正の奇数 $k$

そして、単に『シェルピンスキー数』と呼ぶときには、第二種シェルピンスキー数をいうそうです。このシェルピンスキー数は、 が尊敬している @tsujimotter さんのYouTube動画「現時点で最小のシェルピンスキー数「78557」 - 明日話したくなる「数」のお話 #31」にも取り上げられております。十数分の動画ですのでお時間がある方は是非チェックしてみてください。

改めて単なる『シェルピンスキー数』の定義を再掲します。

シェルピンスキー数の定義

$ \forall n \in \mathbb{N} $ に対して、$ k \times 2^{n} + 1 $ が合成数となる正の奇数 $k$

現在知られている最小のシェルピンスキー数 $78557$ に対しては、1962年にセルフリッジが次の場合分けで証明しています。

【 $s_{n} = 78557 \times 2^{n} + 1 $ が $ \forall n \in \mathbb{N} $ について合成数である場合分け】

$ n = 2k\quad(k \in \mathbb{N}) $ のとき、$s_{n} \equiv 0 \pmod{3}$
$ n = 4k+1\quad(k \in \mathbb{N}) $ のとき、$s_{n} \equiv 0 \pmod{5}$
$ n = 12k+7\quad(k \in \mathbb{N}) $ のとき、$s_{n} \equiv 0 \pmod{7}$
$ n = 12k+11\quad(k \in \mathbb{N}) $ のとき、$s_{n} \equiv 0 \pmod{13}$
$ n = 36k+3\quad(k \in \mathbb{N}) $ のとき、$s_{n} \equiv 0 \pmod{73}$
$ n = 36k+15\quad(k \in \mathbb{N}) $ のとき、$s_{n} \equiv 0 \pmod{19}$
$ n = 36k+27\quad(k \in \mathbb{N}) $ のとき、$s_{n} \equiv 0 \pmod{37}$

シェルピンスキーの問題

$78557$ より小さい数で、シェルピンスキー数となる数があるかは確認されておらず、『$78557$ が最小のシェルピンスキー数である』かどうかは未解決問題です。すべての自然数に対して合成数となる証明を与えるか、１つでも例外である素数を見つけることが、この未解決問題に対して有効な手段です。そこで、2002年から "Seventeen or Bust" プロジェクトとして、それまでに素数が見つかっていないシェルピンスキー数の候補である17個の数に対して、素数である数の探索が行われております。そして次々と素数が見つかり、素数となる数が見つかっていない $k$ が、$ 21181, 22699, 24737, 55459, 67607 $ の5個まで絞れたところまで来ています。そして、その5個の数は今後も探索対象とされています。

コルベール数

この探索で、メルセンヌ素数ではない素数で巨大な素数が発見されております。$k \lt 78557$ の反例として示された素数のうち、十進数展開が100万桁を越える素数（『メガ素数』と呼ばれる素数）を『コルベール数』と呼びます。

プロス素数

$k\cdot2^{n}+1$（$n$：正の整数、$k$：$2^{n}>k$を満たす正の奇数）で表される数を『プロス数』といい、さらに素数であるプロス数を『プロス素数』と呼びます。（の過去エントリを参照²）つまり、この探索の判例として発見される素数は、プロス素数になりえます。そして、現時点で知られている全てのコルベール数はプロス素数でもあるそうです。

プロス数が素数であるか否かの判定を行うことができる「プロスの定理」という素数判定方法があり、この判定方法がシェルピンスキー数の判例の探索にも役立っています。

リーゼル数

リーゼル数はシェルピンスキー数と似た（$+1$を$-1$に置き換えた）次のように定義された数です。

リーゼル数の定義

$ \forall n \in \mathbb{N} $ に対して、$ k \times 2^{n} - 1 $ が合成数となる正の奇数 $k$

既知のリーゼル数は、$ 509203, 762701, 777149, 790841, 992077, \dots$ （オンライン整数列大辞典 A101036より）です。シェルピンスキー数と同様に、最小のリーゼル数が $509203$ かどうかは確認されておらず、2020年12月の時点では、探索対象の数が48個あるそうです。

ブリエ数

ブリエ数とは、シェルピンスキー数でもあり、リーゼル数でもある数です。既知のブリエ数は、$ 3316923598096294713661, 10439679896374780276373, 11615103277955704975673, \dots $（オンライン整数列大辞典 A076335より）です。

おわりに

シェルピンスキーは彼の名前を冠した３つのフラクタル図形『シェルピンスキーの三角形（ガスケット）』『シェルピンスキーのカーペット』『シェルピンスキー曲線』も有名です。
本稿では、第二種シェルピンスキー数について主に記述しましたので、最後に第一種シェルピンスキー数についても簡単に取り上げておきましょう。

第一種シェルピンスキー数

シェルピンスキーは、第一種シェルピンスキー数 $S_{n} := n^{n} + 1 (n \ge 2)$ が素数であるには、$n = 2 ^{2^{k}}$ の形に限られることを証明しました。素数である第一種シェルピンスキー数は、$ m = k + 2^{k} $ とおくと、フェルマー数 $F_{m} = 2^{2^{m}}+1$ となり、フェルマー素数であることがわかります。現時点で素数である第1種シェルピンスキー数は、$2, 5, 257$ しか知られていません。（オンライン整数列大辞典 A121270 参照）

いかがでしたでしょうか。シェルピンスキー数に関しての情報はそこまで多くなかったため、本稿では、参考プログラムは無しに解説記事を主にさせていただきました。ご一読いただきまして有り難うございます。それでは。

（●）（●） Happy Hacking!
/""　＿＿""＼

1. 巨大数研究 Wiki『シェルピンスキー数』 ↩

2. の記事『プロス素数とピアポイント素数』 ↩