Ruiz-Sondowの素数公式

素数公式記事第二弾。

定理 (Ruiz-Sondow, (2002) ) $p_n$ を $n$ 番目の素数とするとき、

$\displaystyle p_n=2+\sum_{k=2}^{[2n\log n+2]}\left( 1-\left[\frac{\displaystyle \sum_{j=2}^k\Biggl( 1+\Biggl[ \frac{2-\sum_{i=1}^j\left( \left[ \frac{j}{i} \right] - \left[ \frac{j-1}{i} \right] \right)}{j} \Biggr] \Biggr)}{n}\right] \right)$

が成り立つ。

補題１ $d_n$ を $n$ の正の約数の個数とする。このとき、

$\displaystyle d_n = \sum_{i=1}^n \left( \left[ \frac{n}{i} \right] - \left[ \frac{n-1}{i}\right] \right)$

が成り立つ。

証明. $n$ を $i$ で割った商を $q$ 、余りを $r$ としよう。このとき、 $[n/i]=q$ が成り立つ。 $i\mid n$ ならば、 $n-1$ を $i$ で割った商は $q-1$ 、余りは $r-1$ であるから、

$\displaystyle \left[ \frac{n}{i}\right] - \left[ \frac{n-1}{i}\right] = q-(q-1)=1$

であり、 $i \nmid n$ ならば、 $n-1$ を $i$ で割った商は $q$ 、余りは $i-1$ であるから、

$\displaystyle \left[ \frac{n}{i}\right] - \left[ \frac{n-1}{i}\right] = q-q=0$

となる。よって、 $d_n$ の公式が得られる。 Q.E.D.

$\begin{align} d_n=1 &\Longleftrightarrow n=1, \\ d_n=2 &\Longleftrightarrow n\text{が素数}, \\ d_n > 2 &\Longleftrightarrow n\text{が合成数},\end{align}$

であるから、 $n\geq 2$ のとき

$\displaystyle P(n) = 1 + \left[ \frac{2-d_n}{n}\right]$ −①

が成り立ちます( $d_n \leq n$ に注意)。ここで、 $P(n)$ は素数判定関数です*1。

次の定理は深い結果なので、この記事では証明抜きで用いることに足ます。

定理 (Rosser-Schoenfeld) 任意の自然数 $n$ に対して

$p_n > n\log n$

が成立し、 $n > 20$ なる $n$ に対して

$\displaystyle p_n < n\log n+n\left( \log \log n-\frac{1}{2} \right)$

が成立する。

これを使う形に書き換えます：

補題２ 任意の自然数 $n$ に対して、

$\pi (2n\log n+2) < 2n$

および

$p_n \leq 2n\log n+2$

が成り立つ。

証明. Rosser-Schoenfeldの定理より、一つ目はただちに従う。二つ目の式は $20$ 以下の $n$ については直接確認し、 $n > 20$ ならばRosser-Schoenfeldより

$\displaystyle p_n < n\log n+n\left( \log \log n-\frac{1}{2} \right) < n\log n+n\log \log n < 2n\log n$

を得る。 Q.E.D.

補題２より

$\displaystyle \left[ \frac{\pi(x)}{n} \right] = \begin{cases} 0 & (1 \leq x < p_n) \\ 1 & (p_n \leq x < 2n\log n+2)\end{cases}$

が分かります。よって、

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

が成立し、補題１、①、および

$\displaystyle \pi (x) = \sum_{j=2}^{[x]}P(j)$

よりRuiz-Sondowの公式が証明されました。

*1:cf.integers.hatenablog.com

INTEGERS

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

Ruiz-Sondowの素数公式