n番目の素数の式
なんか凄そうな式に見えて実際はめっちゃナイーブな実装の式
$ P(n)=1+\sum_{k=1}^{2^n}\left\lfloor\sqrt[^n]\frac{n}{\sum_{j=1}^k\left\lfloor\cos^2\left(\frac{(j-1)!+1}{j}\pi\right)\right\rfloor}\right\rfloor
プログラムで書くなら
$ P(n)=1+\sum_{k=1}^{2^n}{\rm ge}(n,{\rm countP}(k))
どっちみち計算量が$ \Omicron(2^n)であることに注意
素数判定
$ {\rm isP}(j)=\left\lfloor\cos^2\left(\frac{(j-1)!+1}{j}\pi\right)\right\rfloor
ウィルソンの定理より$ pが 1 か素数の時$ (j-1)!\overset{j}{\equiv}-1 すると、$ \frac{(j-1)!+1}{j}は整数になる
なので、$ \cos^2\left(\frac{(j-1)!+1}{j}\pi\right)=1
$ jが "1 または素数" でない時は
$ -1<\cos\left(\frac{(j-1)!+1}{j}\pi\right)<1
なので
$ \left\lfloor\cos^2\left(\frac{(j-1)!+1}{j}\pi\right)\right\rfloor=\begin{cases}0&jが\ 1または素数\ ではない\\1&jが\ 1または素数\ である\end{cases}
素数カウント
$ {\rm countP}(k)=\sum_{j=1}^k{\rm isP}(j)=\sum_{j=1}^k\left\lfloor\cos^2\left(\frac{(j-1)!+1}{j}\pi\right)\right\rfloor
$ kまでの素数$ +1を返す
$ 1がカウントされているため、$ +1される
大小比較
$ {\rm ge}(n,m)=\left\lfloor\sqrt[n]\frac{n}{m}\right\rfloor=\begin{cases}0&n<m\\1&n\ge m\end{cases}
$ 0<\sqrt[n]\frac{n}{m}<\sqrt[n]n<\sqrt[e]e<2 なので
$ {\rm ge}(n,{\rm countP}(k))=\left\lfloor\sqrt[^n]\frac{n}{\sum_{j=1}^k\left\lfloor\cos^2\left(\frac{(j-1)!+1}{j}\pi\right)\right\rfloor}\right\rfloor
$ kまでの素数の数が$ n未満のとき$ 1、以上のとき$ 0となる
$ P(n)=1+\sum_{k=1}^{2^n}{\rm ge}(n,{\rm countP}(k))
$ =1+\sum_{k=1}^{2^n}\left\lfloor\sqrt[^n]\frac{n}{\sum_{j=1}^k\left\lfloor\cos^2\left(\frac{(j-1)!+1}{j}\pi\right)\right\rfloor}\right\rfloor
$ {\rm ge}(n,{\rm countP}(k)) は$ kまでの素数の数が$ n未満のとき$ 1、以上のとき$ 0となる関数なので、
$ 1から$ n番目の素数$ -1までの間、ずっと$ 1が出る
このため、合計を取ると$ n番目の素数$ -1になる