インテジャーズ

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

インテジャーズ

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

357686312646216567629137:左切り取り可能素数

357686312646216567629137は最大の左切り取り可能素数です:

\begin{align}&357686312646216567629137 \ \text{素数!} \\
&57686312646216567629137 \ \text{素数!} \\
&7686312646216567629137 \ \text{素数!} \\
&686312646216567629137 \ \text{素数!} \\
&86312646216567629137 \ \text{素数!} \\
&6312646216567629137 \ \text{素数!} \\
&312646216567629137 \ \text{素数!} \\
&12646216567629137 \ \text{素数!} \\
&2646216567629137 \ \text{素数!} \\
&646216567629137 \ \text{素数!} \\
&46216567629137 \ \text{素数!} \\
&6216567629137 \ \text{素数!} \\
&216567629137 \ \text{素数!} \\
&16567629137 \ \text{素数!} \\
&6567629137 \ \text{素数!} \\
&567629137 \ \text{素数!} \\
&67629137 \ \text{素数!} \\
&7629137 \ \text{素数!} \\
&629137 \ \text{素数!} \\
&29137 \ \text{素数!} \\
&9137 \ \text{素数!} \\
&137 \ \text{素数!} \\
&37 \ \text{素数!} \\
&7 \ \text{素数!} \end{align}

たった一つの素数を知っているだけで24個もの素数を知っていることになる優れもの!!

左切り取り可能素数の定義は伝わったことと思いますが、後に行うheuristicな議論のために数式を用いて定義してみましょう:

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

\mathbb{P}は素数全体のなす集合です。\mathrm{LT}はLubin-Tateの略ではなく、"left truncatable prime"からつけた名称です。この定義から、左切り取り可能素数を組織的に見つけるプログラムを書くことは(素数判定を既知とすれば)容易にできます。その結果、タイトルにあげた24桁の素数が10進法における最大の左切り取り可能素数ということです。\mathrm{LT}^{(2)}=\emptysetですが、b\geq 3に対してL_b := \max_{p \in \mathrm{LT}^{(b)}}pとするとき、実は1977年の時点で3\leq b \leq 11に対するL_bが決定されています:*1

\begin{align} L_3&=23 \\
L_4&=4091\\
L_5&=7817 \\
L_6&=4836525320399\\
L_7&=817337\\
L_8&=14005650767869\\
L_9&=1676456897\\
L_{10}&=357686312646216567629137\\
L_{11}&=2276005673\end{align}

ところで、一般のbに対してL_bが存在することは(一応)、定義からは自明ではありません。とは言っても、直観から言って流石に存在するはずです。すなわち、次が予想されます:

予想 任意のb\geq 2に対して\mathrm{LT}^{(b)}は有限集合である。

この予想の反例がもしあれば、なかなか強烈な個性をもったb-adic numberが存在することになりますが、それはないことだと思われます。予想のもう少しまともな根拠として、次のようなheuristicな議論が可能です。まず、3つほど復習をしましょう。

復習1

与えられた自然数nが素数である確率を1/\log nであるとみなしてheuristicな議論を行うことがよくあることは素数定理に関する記事で述べました:
integers.hatenablog.com

復習3

 \displaystyle e^x= 1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\cdots

e^xのマクローリン展開,三角関数との関係 | 高校数学の美しい物語
余談ですが、ネイピア数の「ネイピア」とティッシュペーパーの「ネピア」が実は無関係でないことを大栗博司先生の『数学の言葉で世界を見たら』を読んで知りました。ちなみにこの本は超おすすめです。

確率論的考察

まず、定義から\# \mathrm{LT}_1^{(b)} = \pi (b-1)です*2dを自然数としましょう。p \in \mathrm{LT}_{d}^{(b)}に対して\mathrm{LT}_{d+1}^{(b)}(p)の元の候補はb^d+pから(b-1)b^d+pb-1通りあります。これらの中にいくつ素数があるかをカウントすればよいわけですが、復習1の内容からkb^d+pが素数である確率を1/ \log (kb^d+p)とみなすことができます。しかしながら、今kb^d+pbと互いに素であることが分かっているので*3、条件付き確率で考えると確率

\displaystyle \frac{1}{\log (kb^d+p)}\prod_{q \mid b}\left( 1-\frac{1}{q} \right)^{-1} = \frac{b}{\varphi (b)\log (kb^d+p)}

で素数であると考えることができます。ここで、与えられた自然数が素数qで割り切れる確率を1/qとみなしており(従って、与えられた数がbと互いに素である確率は\displaystyle \prod_{q\mid b}\left( 1-\frac{1}{q} \right))、\varphi (b)はEulerのトーシェント関数です:
integers.hatenablog.com


従って、\displaystyle \# \mathrm{LT}_{d+1}^{(b)}(p) ≒ \sum_{k=1}^{b-1}\frac{b}{\varphi (b) \log (kb^d+p)} \leq \frac{b(b-1)}{d\varphi (b)\log b}

と評価できます。よって、ニアリ―イコールが等号であると仮定すれば、

\begin{equation}\begin{split} \#\mathrm{LT}_d^{(b)} &\leq \frac{b(b-1)}{(d-1)\varphi (b)\log b} \#\mathrm{LT}_{d-1}^{(b)} \\ &\leq \cdots \leq \left( \frac{b(b-1)}{\varphi (b)\log b}\right)^{d-1}\times \frac{1}{(d-1)!}\#\mathrm{LT_1^{(b)}} \\ &=\left( \frac{b(b-1)}{\varphi (b)\log b}\right)^{d-1}\times \frac{\pi (b-1)}{(d-1)!} \end{split}\end{equation}

と評価できます。実際にはp \in \mathrm{LT}_1^{(b)}であっても、pbを割りきれば\mathrm{LT}_2^{(b)}(p) = \emptysetとなってしまうので、d\geq 2に対しては

\displaystyle \#\mathrm{LT}_d^{(b)} \leq \left( \frac{b(b-1)}{\varphi (b)\log b}\right)^{d-1}\times \frac{\pi (b-1)-\omega (b)}{(d-1)!}

としてよいです(\omega (b)bの素因数の個数)。 従って、

\begin{equation}\begin{split} \# \mathrm{LT}^{(b)} = \sum_{d=1}^{\infty}\# \mathrm{LT}_{d}^{(b)} &\leq \pi (b-1)+ \sum_{d=2}^{\infty}\left( \frac{b(b-1)}{\varphi (b)\log b-1}\right)^{d-1}\cdot \frac{\pi (b-1)-\omega (b)}{(d-1)!} \\ &= \omega (b) + (\pi (b-1)-\omega (b))e^{\frac{b(b-1)}{\varphi (b)\log b}}\end{split}\end{equation}

が得られます。こうして、確率論的な考察からは\mathrm{LT}^{(b)}は有限集合であることが示唆されました。しかしながら、実際の素数の分布は全く一様ではありません。与えられた数が素数であるかについて、「その数が素数である確率」と「実際に素数であるか」の間には天と地の差があります。これは左切り取り素数を実際にサーチすれことによってかなりの偏りがあることを実感できると思います。

上の議論から\#\mathrm{LT}^{(10)} < 35061が期待されますが、\#\mathrm{LT}^{(10)}=4260です。また、L_{10}が25桁以下であることも期待されますが、実際に24桁です。

次回予告

明日の記事は右切り取り可能素数についてです。

*1:I. O. Angeli, H. J. Godwin, On truncatable primes, Math. of Comp. vol. 31, No. 137(1977), 265-267. 実は左切り取り可能素数や以下で考察するheuristicな議論は昨年の9月頃から遊んだり考察したりしていたものなのですが、だいぶ昔から知られていたことを知りました。命名権が得られなくてちょっぴり残念です。とは言っても"左切り取り素数"という日本語訳は勝手につけたものです(笑)。

*2:\pi \times (b-1)ではなく、b-1以下の素数の個数であることに注意。

*3:すぐ見るようにd=1のときだけ例外ケースあり。