ｎ番目の素数

 $n$番目の素数，$p(n)$を与える式があることを初めて知った。Mathematicaでは，Prime[] という関数があり，10^12番目までを15秒で計算してくれる。

In[1]:= Table[Timing[Prime[10^k]], {k, 1, 12}]

Out[1]= {{0.000014, 29}, {5.*10^-6, 541}, {4.*10^-6, 7919}, {0.000238, 104729}, {6.*10^-6, 1299709}, {3.*10^-6, 15485863}, {3.*10^-6, 179424673}, {3.*10^-6, 2038074743}, {4.*10^-6,22801763489}, {3.*10^-6, 252097800623}, {2.41945,2760727302517}, {15.5547, 29996224275833}}

 その$p(n)$の公式は，1964年にWillansが与えたものである。まず準備として，1から$n$までの自然数の集合に含まれる素数の個数を与える関数を $\Phi(n)$として以下で定義する。ただし，$\lfloor x \rfloor$ はfloor関数（ガウス関数）であり，xを越えない最大の整数を与えるものである。

$\displaystyle \Phi(n) = \sum_{k=1}^m \lfloor \cos^2{\dfrac{(k-1)!+1}{k}\pi} \rfloor -1$

例えば，$\Phi(1)=0, \Phi(2)=1, \Phi(3)=2, \Phi(4)=2, \Phi(5)=3, \Phi(6)=3, \Phi(7)=4$である。この式が成り立つのはウィルソンの定理を用いているからだ。$k$ が素数ならば $(k − 1)! +1 ≡ 0 \ (\rm{mod}\ k)$ が成り立つというものであり，素数に対しては$\lfloor \cos^2 \rfloor$の項が1，それ以外では0となるため，これを加え合わせたものが素数の数に対応する（1は素数でないために取り除いている）。

次に，これを用いて，$n$番目の素数$p(n)$を与える式が次のようになる。

$\displaystyle p(n) = 1 + \sum_{m=1}^{2^n} \lfloor \Bigl( \dfrac{n}{1+\Phi(m)}\Bigr)^{\frac{1}{n}}\rfloor$

ここで，floor関数の値は，$m$までの素数の数 $< n$ならば1， $m$までの素数の数 $\ge n$ならば0である。つまりこれは1から$m$までの自然数の集合における素数カウンターの働きをすることから，与式により$p(n)$が得られることになる。

なお，$m$を1から$2^n$までとしているのは，ベルトランの仮説（任意の自然数 $n$ に対して，$n < m \le 2n$ を満たす素数 $m$ が存在する）より，$n$個の素数を含む十分大きな範囲としているためである。この仮説は高校生時代のエルデシュによって初等的な証明がされたといういわくつきのものだ。$2^n$は$n=10^4$程度の範囲なら$10n$で置き換えられる。

コンパクトな式ではあるが，実際にMathematicaに落とし込んで数値計算してみると，$2^n$が効くので，p(11)で23秒，p(12)で195秒という悲惨な結果となるのであった。$\Phi(n)$をあらかじめ配列にいれて，$10n$を用いれば，$p(1000)$が15秒で実行できる。