インテジャーズ

INTEGERS

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

Regimbalの素数公式

p_nn番目の素数を表します。素数の分布に真に迫るのは大変に難しいことですが、「素数を式で表す」だけなら簡単です*1。この記事はそんな公式達を紹介する第一弾です。

定理 (Regimbal, 1975) \displaystyle \ \ \ p_n=\sum_{k=2}^{2^n}\left[ \frac{1}{\displaystyle 1+\left| n-\left[ \frac{1}{\sum_{i=1}^{k-1}\left[ \left. \left[ \frac{k}{i} \right] \right/ \frac{k}{i}\right]} \right] \sum_{j=2}^k\left[ \frac{1}{\sum_{i=1}^{j-1}\left[ \left. \left[ \frac{j}{i} \right] \right/ \frac{j}{i}\right]} \right] \right|}\right] k
が成り立つ。

補題1 n \geq 2に対して関数g(n)
\displaystyle g(n) = \sum_{i=1}^{n-1}\left[ \left. \left[ \frac{n}{i}\right] \right/ \frac{n}{i} \right]
と定める。このとき、nが素数ならばg(n)=1nが合成数ならg(n) > 1が成り立つ。

証明. 0 < \frac{[x]}{x} \leq 1より、\left[ [x] / x \right]の値は01であることに注意する。

\displaystyle \left[ \left. \left[ \frac{n}{i}\right] \right/ \frac{n}{i} \right] = 1 \Longleftrightarrow \left[ \frac{n}{i}\right] = \frac{n}{i} \Longleftrightarrow i \mid n

であるから、g(n)=1となるための必要十分条件はi \mid nなるi \in \{1, \dots, n-1 \}が一つだけであることがわかる。この条件はすなわちnが素数であることに他ならない。 Q.E.D.

命題1 素数判定関数P(n)
\displaystyle P(n) := \begin{cases}1 & (n\text{が素数であるとき}) \\ 0 & (\text{そうでないとき})\end{cases}
と定める。このとき、n \geq 2ならば
\displaystyle P(n) = \left[ \frac{1}{g(n)}\right]
が成り立つ。

証明. 補題1より刹那に従う。 Q.E.D.

次にn番目の素数が出現した際に、その値を返す機械を作製しましょう:

命題2 nを固定し、m \geq 2とする。このとき、
\displaystyle \left[ \frac{1}{1+|n-P(m)\pi (m)|}\right]m=\begin{cases}m & (m=p_n) \\ 0 & (\text{そうでないとき})\end{cases}
が成り立つ。\pi (m)m以下の素数の個数を表す。

証明. まず、

\displaystyle P(m)\pi (m) = \begin{cases}\pi (m) & (m\text{:素数}) \\ 0 & (m\text{:合成数})\end{cases}

が成り立つことに注意する。よって、n=P(m)\pi (m)が成り立つための必要十分条件はm=p_nである。そうして、

\displaystyle  \left[ \frac{1}{1+|n-P(m)\pi (m)|}\right] = \begin{cases}1 & (m=p_n) \\ 0 & (\text{そうでないとき})\end{cases}

が得られるので、両辺をmばいすればよい。 Q.E.D.

補題2 \ \ \ p_n \leq 2^n.

証明.Bertrandの仮説からわかる。 Q.E.D.

定理の証明. 命題2及び補題2より、

\displaystyle p_n = \sum_{k=2}^{2^n}\left[ \frac{1}{1+\left|n-P(k)\pi (k)\right|}\right] k

がわかる。あとは

\displaystyle \pi (k) = \sum_{j=2}^kP(j)

であることに注意すれば、補題1及び命題1より定理が得られる(n=1のときは直接確認できる)。 Q.E.D.



n番目の素数を表す公式は存在しない」と主張する人と対面したときのみ役立つ定理です。

*1:n番目の素数を上から押さえるところだけ非自明な結果を使います。ただ、深い結果を使えば使うほど無駄がなくなるだけであって integers.hatenablog.com で紹介したp_n < 2^{2^n}でも良いです。