n番目の素数を表す式 - RPGツクールと数学のブログ

過去ブログの転載です。

素数の並びは今でも謎ですけど、n番目の素数を一本の式で表すこと自体は出来ちゃうんです。

$\displaystyle {\rm P}(n)=1+\sum_{m=1}^{2^{n}}\left\lfloor\sqrt[n]{\frac{n}{\sum_{k=1}^{m}\left\lfloor\cos^{2} \frac{(k-1)!+1}{k} \pi\right\rfloor}}\right\rfloor$

${\rm P}(n)$ はn番目の素数を表します。とっても複雑なのでカッコイイ感じがしますけど、非常にアルゴリズム的な数式で、まったく実用的な式ではありません。表せるというだけです。

3番目の素数を求めてみる

試しに ${\rm P}(3)$ を計算してみましょう。３番目の素数ということなので、５になるはずです。

f:id:fermiumbay13:20190323071156p:plain
↑ $n=3$ を代入して計算します。ややこしくなるため、各々四角で囲んで①、②としておきます。

①の計算です。 $m=1$ から始めますので、 $k=1$ の代入のみとなります。［　］の上半分が切れたような記号は床関数といって、中の数が正なら小数点以下切り捨てを意味します。

コサイン二乗の中は分数式です。 $k=1$ を代入すると、 $\cos^{2}\frac{(1-1)!+1}{1} \pi = \cos^{2} 2 \pi=1$ となります。

次に②の計算をします。 $\frac{3}{1}=3$ 、3の3乗根は1.44……といった無限小数です。それの更に切り捨てなので、②の中身は1になります。

$m=1$ のとき②の中身は1でした。
$m=2$ のとき、 $m=3$ のとき、……も順々やっていきます。

$m=2$ のときは①は $1+1=2$ となり、②は $\left\lfloor \sqrt[3]{\frac{3}{2}} \right\rfloor = 1$ になります。

$m=3$ のときは①は $1+1+1=3$ となり、②は $\left\lfloor \sqrt[3]{\frac{3}{3}} \right\rfloor = 1$ になります。

$m=4$ のときは①は $1+1+1+0=3$ となり、②は $\left\lfloor \sqrt[3]{\frac{3}{3}} \right\rfloor = 1$ になります。

$m=5$ のときは①は $1+1+1+0+1=4$ となり、②は $\left\lfloor \sqrt[3]{\frac{3}{4}} \right\rfloor = 0$ になります。

$m=6$ のときは①は $1+1+1+0+1+0=4$ となり、②は $\left\lfloor \sqrt[3]{\frac{3}{4}} \right\rfloor = 0$ になります。

$m=7$ のときは①は $1+1+1+0+1+0+1=5$ となり、②は $\left\lfloor \sqrt[3]{\frac{3}{5}} \right\rfloor = 0$ になります。

$m=8$ のときは①は $1+1+1+0+1+0+1+0=5$ となり、②は $\left\lfloor \sqrt[3]{\frac{3}{5}} \right\rfloor = 0$ になります。

$m=1$ の値から $m=8$ の値まで全部足して、 $1+1+1+1+0+0+0+0=4$ になり、最後に先頭に $1$ があるので、 $1+4=5$ 、よって ${\rm P}(3)=5$ と求まりました。3番目の素数は5ということですね！あってます。

しかしこの式で例えば100番目の素数とか計算しようと思うと、100近い数の階乗が出てきたり、そもそもΣの上限が $2^{100}$ とかなってとてもじゃないけど現実的に計算できなくなります。理論上は有限時間で計算可能で、 ${\rm P}(100)=541$ と求まるはずなんですけど……

n番目の素数が得られる仕組み

何でこの式で素数が求められるのか、仕組みを説明していきます。

↑式中の①の $k$ に関するΣの中には、切り捨て記号の中にコサイン2乗の式が入っていました。この部分では、素数の判定を行っています。この部分が肝ですね。

$n$ が素数のとき $(n-1)! \equiv -1 (\mod n)$ が成り立つという定理（ウィルソンの定理）があります。つまり、 $(n-1)!+1$ が $n$ で割り切れたら素数、ということになります。割り切れる⇔整数になる、ということなので、次は $\cos$ を使って整数か非整数かを判定します。 $\cos($ 整数 $\pi)=\pm 1$ ですので、さらにこれを2乗すれば、整数なら1、非整数なら1未満、として振り分けができます。ということは、小数点以下切り捨てた結果が1なら整数（素数だった）、0なら非整数（素数じゃなかった）、と判定できることになります。

これにより、 $\displaystyle \left\lfloor\cos^{2} \frac{(n-1)!+1}{n} \pi\right\rfloor$ というのは、 $n$ が素数なら1、非整数だったら0と判定する式となります。（ $n=1$ だと1）

①の計算では $k=1$ から $m$ まで足しているので、1は素数と認めないとすると、( $m$ までの素数の個数)＋1の値が得られることになります。 $m=5$ だったら2, 3, 5が素数だから、4になりますね。

①の計算により、 $m$ までの素数の個数は取得できるようにはなりましたけど、やりたいのは $n$ 番目の素数が何かを求めることですので、欲しかった順番の素数が出てきたら計算終了としたいわけです。

例えば3番目の素数が出て来たとき、①の計算結果は4になっており、3を超えます。一方で $\frac{3}{4}$ を計算すると1未満の数になります。1未満の数の3乗根はやはり1未満ですので、これを切り捨てれば0にすることができます。

これを利用したのが②の部分の計算です。①の計算結果が4以上だと分母が大きくなるので0とし、3以下だと1以上の数になります。1以上といっても判定だけしたいので2とかになってもらっては困るから、 $n$ 乗根が間に入ってます。 $m$ の範囲を $2^{n}$ までと制限しておけば、 $n \ge 1$ のとき $1 \le \sqrt[n]{n} \lt 2$ になるので、これを切り捨てて1とすることで判定しているのです。