インテジャーズ

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

インテジャーズ

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

73939133:右切り取り可能素数

73939133 素数大富豪

73939133は最大の右切り取り可能素数です:

\begin{align}&73939133 \ \text{素数!}\\
&7393913 \ \text{素数!}\\
&739391 \ \text{素数!}\\
&73939 \ \text{素数!}\\
&7393 \ \text{素数!}\\
&739 \ \text{素数!}\\
&73 \ \text{素数!}\\
&7 \ \text{素数!}\end{align}

左切り取り可能素数
integers.hatenablog.com

のときと同じように数式で定義しましょう:

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

最大の左切り取り可能素数357686312646216567629137に比べて、最大の右切り取り可能素数73939133は小さいことが特徴的です。全体の数も少なく、\#\mathrm{LT}^{(10)}=4260に対し、\#\mathrm{RT}^{(10)}=83です。

83個しかないということなので全てリストアップしてもよいですが、実はその全部を紹介する必要はありません。というのも、例えば73838133は右切り取り可能素数ですが、実際に切り取った7383813, 738381, 73838, 7383, 738, 73, 7も全て右切り取り可能素数です。つまり、73838133だけを覚えておけば他の7つはわざわざ覚える必要がありません。というわけで次の概念を導入します。

定義 右切り取り可能素数p \in \mathrm{RT}_d^{(b)}\mathrm{RT}_{d+1}^{(b)}(p) = \emptysetを満たすとき、pのことを極大右切り取り可能素数といい、b進法における極大右切り取り可能素数全体
のなす集合を\mathrm{RT}_{\text{res}}^{(b)}と記す。

極大左切り取り可能素数\mathrm{LT}_{\text{res}}^{(b)}も同様に定義できます。このとき、\#\mathrm{RT}_{\text{res}}^{(10)}=27であり、その全ての元をリストアップすると以下のようになります:

53, 317, 599, 797, 2393, 3793, 3797, 7331, 23333, 23339, 31193, 31379, 37397,
73331, 373393, 593993, 719333, 739397, 739399, 2399333, 7393931, 7393933,
23399339, 29399999, 37337999, 59393339, 73939133

左切り取り可能素数と同じく、次の予想ができます:

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

最後にheuristicな議論によって、左切り取り可能素数より右切り取り可能素数の方が少ない理由を見て終わりましょう:

p \in \mathrm{RT}_d^{(b)}に対して、bp+1からbp+p-1の中にどれだけ素数があるかをカウントします。これらのうち、bと共通因数をもつようなものは素数になりえないので排除します。すると、考慮すべき数は\varphi (b)個であることがわかります*1bと互いに素な数bp+kが素数となる条件付き確率は、左切り取り可能素数のときと同様に考えることにより、b/\varphi(b)\log(bp+k)とみなすことにします。すると、b^{d-1} < p < b^dであることから、

\displaystyle \#\mathrm{RT}_{d+1}^{(b)}(p) ≒ \sum_{k=1, (k, b)=1}^{b-1}\frac{b}{\varphi (b)\log (bd+k)} < \frac{b}{d\log b}

と評価できます。よって、ニアリーイコールを等号とみなすことによって、

\displaystyle \#\mathrm{RT}_d^{(b)} < \frac{b}{(d-1)\log b}\#\mathrm{RT}_{d-1}^{(b)} < \cdots < \left( \frac{b}{\log b} \right)^{d-1}\cdot \frac{\pi (b-1)}{(d-1)!}

が得られます。従って、

\displaystyle \#\mathrm{RT}^{(b)} = \sum_{d=1}^{\infty}\#\mathrm{RT}_d^{(b)} < \pi (b-1)\sum_{d=1}^{\infty}\left( \frac{b}{\log b} \right)^{d-1}\cdot \frac{1}{(d-1)!} = \pi (b-1)e^{\frac{b}{\log b}}

と結論づけられました。この評価から\#\mathrm{RT}^{(10)} \leq 307であり、最大右切り取り可能素数は12桁以下であることが予測されます。ちなみに、左切り取り可能素数のときは

\#\mathrm{LT}^{(b)} \leq \omega (b) + (\pi (b-1)-\omega (b))e^{\frac{b(b-1)}{\varphi (b)\log b}}

であったため、\varphi(b) \leq b-1において\varphi(b)が小さければ小さいほど、b進法における左切り取り可能素数より右切り取り可能素数の方が少ないことが予測されます。\varphi (10) =4 < 9であることから、右切り取り可能素数が圧倒的に少なかったことが理解できるわけです(eの肩における差を考えるので、大きな差が生じる)。一方、素数進法の場合は\varphi (b)=b-1なので、右切り取り可能素数の方がむしろ多い可能性があります。実際に、11進法における最大右切り取り可能素数6774006887は最大左切り取り素数2276005673より大きいことが観察されます。このように整数の性質の違いが結果に反映されているのはとても面白いです。

ちなみに、右切り取り可能素数は全て素数大富豪素数です(29399999を出すにはジョーカー2枚必要!)
integers.hatenablog.com

*1:この部分が左切り取り可能素数とは違うことがわかります。