素数の一般項を求めよ
問題
【問】素数の一般項を求めよ。無理ならば何か面白いことを書け。
アミオP/AMIO@謎解きスト @amioP
面白いことは言えないので一般項を求めます。一般項には高校までに登場する数学記号を使えるものとします。
素数生成式は存在するか
n 番目の素数を求める素数生成式は存在しないと主張されることがあるが、これは誤りである。
素数 - Wikipedia
計算可能な整数の集合はその要素を整数解とするディオファントス方程式が存在することが証明されているなど、
実は一般項を求める問題は計算可能性と深く結びついています。
詳しくは
を参照
素数を列挙するアルゴリズムを書くことはできるので、それを数式に変換することができれば、一般項が求まりそうです。
アルゴリズムを考える
いきなり$ n番目の素数を求める公式を作るのは難しいので、
命題を以下のように変換します。
$ mが$ n番目の素数 ⇔ $ mが素数 かつ$ m以下の素数が$ n個である
そして、
素数かどうか判定する式 （素数判定式）
n以下の素数の個数を出力する式 （素数の個数を求める式）
を考えることにします。
つまり、アルゴリズムとしては、
$ n番目の素数 $ {a_n} を求めるアルゴリズム
$ 1〜f(n)までの自然数$ mについて( $ f(n)は十分大きい数)
$ mが素数 かつ$ m以下の素数が$ n個であるならば$ m 、そうでなければ $ 0
の総和
となります。
素数判定式と素数の個数の式
まずは
$ IsPrime(p): pが素数ならば1, そうでなければ0
を考えます。
実は、色々な方法があります。
シンプルなのはウィルソンの定理
ウィルソンの定理
ウィルソン(Wilson)の定理：
2 以上の整数 p について，
$ p が素数 ⟺(p−1)!≡−1 \mod{p}
とガウス記号$ (\lfloor x \rfloorはxを下回らない最小の整数)を使って
$ IsPrime(p): \lfloor cos^2(\frac{(n-1)!+1}{n}\pi)\rfloor
と表すことができます。
また、$ nまでの素数の個数 $ π(n)は
$ π(n) = \sum_{k=1}^{n}IsPrime(n) = \sum_{k=1}^{n}\lfloor cos^2(\frac{(n-1)!+1}{n}\pi)\rfloor]
で求められます。
素数の一般項
$ n番目の素数 $ {a_n} を求めるアルゴリズム
$ 1〜f(n)までの自然数$ mについて( $ f(n)は十分大きい数)
$ mが素数 かつ$ m以下の素数が$ n個であるならば$ m 、そうでなければ $ 0
の総和
このアルゴリズムを数式にします。文章をそのまま数式にするだけ！
$ \sum_{m=1}^{f(n)} m * IsPrime(m)* δ_{π(m),n}
すなわち
$ \delta_{ij} = \begin{cases} 1 & (i=j)\\ 0 & (i \ne j)\end{cases}
となる関数です。
この関数は高校範囲ではないので、別の表現を考える必要があります。
これも色々ありますが、
$ i,jが自然数であれば、シンプルに
$ \lfloor \cos^2{(i-j)} \rfloor
で良さそうです。
n番目の素数の見積もり
あとは$ f(n) >= a_nとなる整数関数$ f(n)を求めるだけです。
ベルトランの仮説（チェビシェフの定理）
「任意の自然数 n に対して、n < p ≤ 2n を満たす素数 p が存在する」
より、2^nはn番目の素数よりも常に大きい数になります。
$ f(n) = \lfloor 2nlog(n)\rfloor + 2 > a_n などと表すこともできます。
というわけで、できました。
$ \sum_{m=1}^{\lfloor 2nlog(n) \rfloor + 2} m \lfloor cos^2(\frac{(m-1)!+1}{m}\pi)\rfloor\lfloor \cos^2{(\sum_{k=1}^{m}\lfloor cos^2(\frac{(k-1)!+1}{k}\pi)\rfloor- n)} \rfloor
参考
おまけ
こんな感じの数式いじりが好きな人におすすめの謎