INTEGERS

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

Regimbalの素数公式

素数公式

$p_n$ で $n$ 番目の素数を表します。素数の分布に真に迫るのは大変に難しいことですが、「素数を式で表す」だけなら簡単です*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$
が成り立つ。

補題１ $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)=1$ 、 $n$ が合成数なら $g(n) > 1$ が成り立つ。

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

$\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.

命題１ 素数判定関数 $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]$

が成り立つ。

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

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

命題２ $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.

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

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

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

$\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)$

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

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

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