インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

1987:削除可能素数

1987

1987削除可能素数です:

\begin{align}&19\color{red}{8}7 \ \text{←素数!}\\
&\color{red}{1}97 \ \text{←素数!}\\
&\color{red}{9}7 \ \text{←素数!}\\
&7 \ \text{←素数!}\end{align}


というように、一桁ずつ削っていってずっと素数に出来るような素数のことを削除可能素数と言います(赤色の数字が次に削られる数)。削除可能素数は1987年にCaldwellという人が考察したものであり、この年に「1987の面白い性質が何かないかな~」と考えていて、この概念を思いついたのではないかと推察します。

ちなみに、1987年といえば次の2つの大きい出来事があった年です:

  1. 大マゼラン雲における超新星爆発SN1987A
  2. Elkiesによる\mathbb{Q}上楕円曲線の超特異素数の無限性証明

SN1987Aは近年では最も近い距離で起きた超新星爆発です。このとき放出されたニュートリノを観測したことによって小柴昌俊がノーベル賞を受賞しました。ちなみに、超新星爆発の日付である2月23日は月も日も素数で、くっつけた223も素数です。

Elkiesの業績についてはいずれ記事にすると思います。

削除可能素数の話に戻しましょう。以前記事にした切り取り可能素数は全て削除可能素数であることがわかります*1:
integers.hatenablog.com
integers.hatenablog.com
integers.hatenablog.com

削除可能素数に関しては、両側を除く桁の部分に0があっても構いません:

\begin{align}&516433\color{red}{0}99410256793 \ \text{←素数!} \\
&5\color{red}{1}643399410256793\ \text{←素数!} \\
&5\color{red}{6}43399410256793\ \text{←素数!} \\
&5433\color{red}{9}9410256793\ \text{←素数!} \\
&\color{red}{5}4339410256793\ \text{←素数!} \\
&\color{red}{4}339410256793\ \text{←素数!} \\
&33\color{red}{9}410256793\ \text{←素数!} \\
&\color{red}{3}3410256793\ \text{←素数!} \\
&\color{red}{3}410256793\ \text{←素数!} \\
&41\color{red}{0}256793\ \text{←素数!} \\
&412567\color{red}{9}3\ \text{←素数!} \\
&41\color{red}{2}5673\ \text{←素数!} \\
&4\color{red}{1}5673\ \text{←素数!} \\
&4567\color{red}{3}\ \text{←素数!} \\
&4\color{red}{5}67\ \text{←素数!} \\
&\color{red}{4}67\ \text{←素数!} \\
&\color{red}{6}7\ \text{←素数!} \\
&7\ \text{←素数!} \end{align}


また、次の素数列の例はとても有名ですが、削除可能素数であることが分かります。

\begin{align}&\color{red}{3}3333331\ \text{←素数!} \\
&\color{red}{3}333331\ \text{←素数!} \\
&\color{red}{3}33331\ \text{←素数!} \\
&\color{red}{3}3331\ \text{←素数!} \\
&\color{red}{3}331\ \text{←素数!} \\
&\color{red}{3}31\ \text{←素数!} \\
&3\color{red}{1}\ \text{←素数!} \\
&3 \ \text{←素数!} \end{align}


ちなみに、333333313も削除可能素数です(最初に右端の3を削除すればよい)。

知られているFermat素数3, 5, 17, 257, 65537では257のみが削除可能素数ではありません:

\begin{align}&6553\color{red}{7}\ \text{←素数!} \\
&65\color{red}{5}3\ \text{←素数!} \\
&\color{red}{6}53\ \text{←素数!} \\
&\color{red}{5}3\ \text{←素数!} \\
&3\ \text{←素数!} \end{align}


左切り取り可能素数は4260個(最大が24桁)しかありませんでしたが、削除可能素数は大量に見つかります。実際、

\begin{align}&2620\color{red}{6}9\ \text{←素数!} \\
&26\color{red}{2}09\ \text{←素数!} \\
&26\color{red}{0}9\ \text{←素数!} \\
&2\color{red}{6}9\ \text{←素数!} \\
&2\color{red}{9}\ \text{←素数!} \\
&2\ \text{←素数!} \end{align}


はたったの6桁ですが、1万個目の削除可能素数です*2

Caldwellは削除可能素数は無数の存在すると予想しているそうです(ただし、2進法の場合は削除可能素数は存在しないため、3進法以上で考える)。このことを、切り取り可能素数のときのようにheuristicな議論によって理解してみましょう。

Heuristicな議論

定義 b進法表記で自然数を考えているとする。このとき、n \in \mathbb{N}の左からj桁の部分のみを考えて出来る数をn_{(j)}、右からj桁の部分のみを考えて出来る数をn^{(j)}と表記する。
例) 10進法において、123456789_{(4)}=1234, 123456789^{(6)} = 456789.

定義 b2以上の整数、dを自然数とする。このとき、集合\mathrm{D}_d^{(b)}を次のように帰納的に定義する:
まず、集合\mathrm{D}_1^{(b)}\mathrm{D}_1^{(b)}:=\{p\in \mathbb{P} \mid p\leq b−1\}によって定義し、\mathrm{D}_d^{(b)}が定義されているとき、p\in \mathrm{D}_d^{(b)}に対して
\mathrm{D}_{d+1}^{(b)}(p):=\mathrm{D}_{d+1}^{(b)}(p)_0 \cup \mathrm{D}_{d+1}^{(b)}(p)_1 \cup \cdots \cup \mathrm{D}_{d+1}^{(b)}(p)_d,
\mathrm{D}_{d+1}^{(b)}(p)_0:=\{pb+k \mid 1\leq k\leq b−1, \ pb+k: \text{素数}\},
\mathrm{D}_{d+1}^{(b)}(p)_1:=\{p_{(d-1)}b^2+kb+p^{(1)} \mid 0\leq k\leq b−1, p_{(d-1)}b^2+kb+p^{(1)}: \text{素数}\},
\mathrm{D}_{d+1}^{(b)}(p)_2:=\{p_{(d-2)}b^3+kb^2+p^{(2)} \mid 0\leq k\leq b−1, p_{(d-2)}b^3+kb^2+p^{(2)}: \text{素数}\},
{\small \mathrm{D}_{d+1}^{(b)}(p)_{d-1}:=\{p_{(1)}b^{d}+kb^{d-1}+p^{(d-1)} \mid 0\leq k\leq b−1, p_{(1)}b^{d}+kb^{d-1}+p^{(d-1)}: \text{素数}\}},
\mathrm{D}_{d+1}^{(b)}(p)_d:=\{kb^d+p \mid 1\leq k\leq b−1, \ kb^d+p: \text{素数}\}
として、\displaystyle \mathrm{D}_{d+1}^{(b)}:=\bigcup_{p\in \mathrm{D}_d^{(b)}}\mathrm{D}_{d+1}^{(b)}(p)によって\mathrm{D}_{d+1}^{(b)}を定義する。
このとき、\displaystyle \mathrm{D}^{(b)}:=\bigcup_{d=1}^{\infty}\mathrm{D}_d^{(b)}の元のことを(b進法における)削除可能素数とよぶ。

まず、定義から\#\mathrm{D}_1^{(b)}=\pi (b−1)です。dを自然数としましょう。p\in \mathrm{D}_d^{(b)}に対して、右切り取り可能素数の記事と同様に

\displaystyle \mathrm{D}_{d+1}^{(b)}(p)_0 ≒ \sum_{k=1, (k, b)=1}^{b-1}\frac{b}{\varphi (b)\log (pb+k)} > \frac{b}{(d+1)\log b}

とできます。また、左切り取り可能素数の記事と同様に

\displaystyle \mathrm{D}_{d+1}^{(b)}(p)_d ≒ \sum_{k=1}^{b-1}\frac{b}{\varphi (b)\log (kb^d+p)} > \frac{b(b-1)}{(d+1)\varphi (b) \log b} \geq \frac{b}{(d+1)\log b}

です。 1 \leq j \leq d-1のときは、p_{(d-j)}b^{j+1}+kb^j+p^{(j)}はどのkについてもbと互いに素かどうかは非自明なため、条件付き確率は用いずに単に素数定理から推定される確率を採用します。すると、

\displaystyle \mathrm{D}_{d+1}^{(b)}(p)_j ≒ \sum_{k=0}^{b-1}\frac{1}{\log (p_{(d-j)}b^{j+1}+kb^j + p^{(j)})} > \frac{b}{(d+1)\log b}

が得られます。ここで、p_{(d-j)}b^{j+1}+kb^j + p^{(j)} < b^{d+1}であることに注意します。すると、≒の部分を等号とみなすことによって、

\displaystyle \#\mathrm{D}_{d+1}^{(b)}(p) > \frac{b}{\log b},

すなわち、

\displaystyle \#\mathrm{D}_{d}^{(b)} > \frac{b}{\log b}\#\mathrm{D}_{d-1}^{(b)} > \cdots > \left( \frac{b}{\log b} \right)^{d-1} \pi (b-1)

が分かります。従って、b \geq 3のとき*3

\displaystyle \#\mathrm{D}^{(b)} = \sum_{d=1}^{\infty}\#\mathrm{D}_d^{(b)} > \pi (b-1) \sum_{d=1}^{\infty} \left( \frac{b}{\log b} \right)^{d-1} = \infty

となって、削除可能素数は無数に存在すると期待されることがわかりました。

*1:削除可能素数についてはGreat Icosahedron氏にtwitter上で教えて頂きました。

*2:http://oeis.org/A080608/b080608.txt この表には20032017が載っていますが、私はこれは削除可能素数とは呼びたくありません(一番左の桁が0になることは認めたくない)。ですので、この例は実際には1万個目ではありません。ただ、削除可能素数が大量にあることはある程度伝わります。

*3:b=2ならば\pi (b-1)=0となります。