続・素数生成式
以前にここに書いた素数生成式を大幅に簡略化できましたーって話。
素数生成式というのは、自然数(ここでは 1 以上の整数の意) n を代入すると n 番目の素数になるような式のことです。
ネットで調べてみると、そんな式は存在しない!という発言が多々見受けられますが、それは大いなる間違いです。
素数生成式はいくらでも発見されていますし、素数全てとまではいかないまでも値が必ず素数になるものや、特定の条件を満たす値が全て素数であるようなものも含めると、とてもとてもたくさんあります。
おそらく、こうした誤解は、「自然数 n を代入した結果の値が全て素数となるような整数係数の多項式が存在しない」という事実からきた誤解なのではないかと。
[ 参考 ] Wikipedia:Formula for primes
さてさて。
ここから、具体的に素数生成式を作っていきます。
以下では、変数は全て整数を表すものとします。
まず、x と y が等しいなら 1、異なるなら 0 を返す関数(クロネッカーのデルタ)を次のように定義しちゃいます。
i = 1 のときに i-1 = 0 なので、x と y が異なるなら、|x-y| > 0 より、各 (i-1) の積は 0 になります。
x = y のときは、積をとれないので、このときは便宜的に 1 になります。 はそのように定義されています。
次に、x が y で割り切れるなら 1、割り切れないなら 0 を返す関数。
x を y で割った商は一つに定まるので、この値が必ず 1 か 0 になることが分かります。
そして、x が素数なら 1、合成数なら 0 を返す関数。
1 と自分自身以外では割り切れない、ということですね。
これで、準備完了です。
素数生成式は、次のようになります。
n 番目の素数は 以下、という定理があるので、2 から までの数を考えて、その中で、素数であって、それより小さい素数の個数が n-1 個であるもの、という意味です。
具体的に書き下すと
となります。
実用性は、全くありません。