インテジャーズ

インテジャーズ

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

Ruiz-Sondowの素数公式

素数公式記事第二弾。

定理 (Ruiz-Sondow, (2002) ) p_nn番目の素数とするとき、
\displaystyle p_n=2+\sum_{k=2}^{[2n\log n+2]}\left( 1-\left[\frac{\displaystyle \sum_{j=2}^k\left( 1+\left[ \frac{2-\sum_{i=1}^j\left( \left[ \frac{j}{i} \right] - \left[ \frac{j-1}{i} \right] \right)}{j} \right] \right)}{n}\right] \right)
が成り立つ。

補題1 d_nnの正の約数の個数とする。このとき、
\displaystyle d_n = \sum_{i=1}^n \left( \left[ \frac{n}{i} \right] - \left[ \frac{n-1}{i}\right] \right)
が成り立つ。

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

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

であり、i \nmid nならば、n-1iで割った商は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)は素数判定関数です。

integers.hatenablog.com

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

定理 (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)
が成立する。

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

補題2 任意の自然数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.

補題2より

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

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

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

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