ここから本文です

この知恵ノートを「知恵コレクション」に追加しました。

追加した知恵ノートはMy知恵袋の「知恵コレクション」ページで確認できます。

知恵コレクション」に登録済みです。

再登録しました。

追加に失敗しました。

ノートに戻り、もう一度やり直してください。

すでに1,000件のノートが登録されています。

新しく追加したい場合は、My知恵袋の「知恵コレクション」ページで登録されているノートを削除してください。

追加できませんでした。

ノートは削除されました。

素数生成式

ライターさん(最終更新日時:2014/5/11)投稿日:

  • ナイス!:

    4

  • 閲覧数:1465

印刷用のページを表示する

どういうわけか全ての素数を表す公式、もう少し正確にいうと例えば正の整数nを代入するとn番目の素数を表せる式はないと妄信している人たちがいるが、そんなことはない。素数を表す公式は山ほど見つかっている。計算量が多すぎて実用からは程遠いというのは事実だが。そのような公式の中でも簡単なものをいくつか紹介しよう。
p(n)でn番目の素数を表すことにする。つまり、p(1)=2, p(2)=3, p(3)=5, …である。
[x]でxを超えない最大の整数を表す。いわゆるGauss記号(床関数)である。
Σ{m=1,n}f(m)でf(1)+f(2)+…+f(n)を表すことにする。
公式その1
p(n)=1+Σ{m=1,2^n}[[n/Σ{k=1,m}([{cos(π((k-1)!+1)/k)}^2])]^(1/n)]
この式をちょっと変形すると
公式その2
p(n)=1+Σ{m=1,2^n}[[n/(Σ{k=1,m}([(((k-1)!+1)/k)-[(k-1)!/k]]))]^(1/n)]
 n番目の素数を表す式
Gauss記号は大かっこと紛らわしいので,
床関数の記号で書いた画像も貼っておく
(書いてあることは同じです)
 sosuu.png
ではこれらの公式を証明しよう
ステップ1
F(k)=[{cos(π((k-1)!+1)/k)}^2]とおく
するとk=1または素数のときF(k)=1, それ以外のときF(k)=0である
なぜならば、k=1のときは代入すればわかる
kが素数のときはWilsonの定理 (k-1)!≡-1 (mod k) により ((k-1)!+1)/k) は整数となるからである
またkが合成数のときもやはりWilsonの定理より ((k-1)!+1)/k) が整数とならないからである
ステップ2
次にπ(m)=-1+Σ{k=1,m}F(k)であることを示す
ここでπ(x)は素数個数関数、つまりx以下の素数の個数を表す関数である
(π(1)=0, π(2)=1, π(3)=2, π(4)=2, …)
この等式が成り立つことはステップ1より明らかである
ステップ3
p(n)=1+Σ{m=1,2^n}[[n/(1+π(m))]^(1/n)]であることを示す
まず[[n/(1+π(m))]^(1/n)]は1か0であることに注意しよう
つまりΣ~の最初の数項は1で残りは0になるのである
もう少し詳しく言うとπ(m)=nになる1つ手前までは1でそれ以降は0になるのである
(m=2^nまで足すのはπ(2^n)≧nだからであって特に本質的な意味はない)
よって1+Σ{m=1,2^n}[[n/(1+π(m))]^(1/n)]=1+(1+…+1+0+0+…)=p(n)となる
これで公式その1の証明が完成した
公式その2を証明するには
F(k)=[(((k-1)!+1)/k)-[(k-1)!/k]])
を示せばよいが、これもやはりWilsonの定理から得られる
以上で証明を終わる

参考にしたサイト

このノートに関するQ&A

このノートに関するQ&Aは、まだありません。

このノートについて質問する

このノートについてライターの方に質問できます。

※ライターの方から必ず回答をいただけるとは限りません

※別ウィンドウで開きます

あなたにおすすめの知恵ノート

この知恵ノートのライター

グレード

グレード知恵ノートのグレード:1-3

yuki_math_rh_bsd_nseさん男性

ピックアップ

【iPhone】修理交換の申込方法...
 ※追記※2015/1/30現在iPhone6及び6+が発売されたのを受け、情...
耳鼻科の先生に聞いた、しゃっ...
  皆さん、しゃっくりってわずらわしいですよね  ある時急に...
厄年について——意外と知られて...
厄年とは何か厄年とは文字どおり災厄に遭いやすいといわれる...
本文はここまでです このページの先頭へ