で
番目の素数を表します。素数の分布に真に迫るのは大変に難しいことですが、「素数を式で表す」だけなら簡単です*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](http://chart.apis.google.com/chart?cht=tx&chl=%5Cdisplaystyle%20%5C%C2%A0%5C%20%5C%20p_n%3D%5Csum_%7Bk%3D2%7D%5E%7B2%5En%7D%5Cleft%5B%20%5Cfrac%7B1%7D%7B%5Cdisplaystyle%201%2B%5Cleft%7C%20n-%5Cleft%5B%20%5Cfrac%7B1%7D%7B%5Csum_%7Bi%3D1%7D%5E%7Bk-1%7D%5Cleft%5B%20%5Cleft.%20%5Cleft%5B%20%5Cfrac%7Bk%7D%7Bi%7D%20%5Cright%5D%20%5Cright%2F%20%5Cfrac%7Bk%7D%7Bi%7D%5Cright%5D%7D%C2%A0%5Cright%5D%20%5Csum_%7Bj%3D2%7D%5Ek%5Cleft%5B%20%5Cfrac%7B1%7D%7B%5Csum_%7Bi%3D1%7D%5E%7Bj-1%7D%5Cleft%5B%20%5Cleft.%20%5Cleft%5B%20%5Cfrac%7Bj%7D%7Bi%7D%20%5Cright%5D%20%5Cright%2F%20%5Cfrac%7Bj%7D%7Bi%7D%5Cright%5D%7D%20%5Cright%5D%20%5Cright%7C%7D%5Cright%5D%20k)
が成り立つ。
が成り立つ。
補題1
に対して関数
を
と定める。このとき、
が素数ならば
、
が合成数なら
が成り立つ。
証明. より、
の値は
か
であることに注意する。
であるから、となるための必要十分条件は
なる
が一つだけであることがわかる。この条件はすなわち
が素数であることに他ならない。 Q.E.D.
命題1 素数判定関数
を
と定める。このとき、
ならば
が成り立つ。
証明. 補題1より刹那に従う。 Q.E.D.
次に番目の素数が出現した際に、その値を返す機械を作製しましょう:
命題2
を固定し、
とする。このとき、
が成り立つ。
は
以下の素数の個数を表す。
証明. まず、
が成り立つことに注意する。よって、が成り立つための必要十分条件は
である。そうして、
が得られるので、両辺をばいすればよい。 Q.E.D.
補題2
.
証明.Bertrandの仮説からわかる。 Q.E.D.
定理の証明. 命題2及び補題2より、
がわかる。あとは
であることに注意すれば、補題1及び命題1より定理が得られる(のときは直接確認できる)。 Q.E.D.
「番目の素数を表す公式は存在しない」と主張する人と対面したときのみ役立つ定理です。
*1:番目の素数を上から押さえるところだけ非自明な結果を使います。ただ、深い結果を使えば使うほど無駄がなくなるだけであって
integers.hatenablog.com
で紹介した
でも良いです。