素数計数関数
素数計数関数(英: Prime-counting function)とは、正の実数にそれ以下の素数の個数を対応させる関数のことであり、π(x) で表す[1][2]。
歴史編集
数論の歴史において π(x) の増大度は重要な関心事とされてきた[3][4]。
18世紀の数学者オイラーは、素数列の逆数の和が発散することを示した(素数の無限性の証明を参照)。平方数の逆数の和は収束するため、これは π(x) が平方数ほど速く増大しないことを示している[5]。
ここで はメビウス関数、 はガウス記号であり、和は √N 以下のすべての素数の積 P のすべての正の約数 d を動く。この式より、
が導かれる[5]。
素数定理編集
18世紀末には、π(x) が に漸近近似できること、即ち
が成り立つであろうということが、ガウスにより予想されていた。1850年頃にチェビシェフは、この等式の左辺がもし極限を持つならば、それは1でなくてはならないことを示した[5]。その後もこの予想は長らく証明されなかったが、1896年になってジャック・アダマールとシャルル=ジャン・ド・ラ・ヴァレー・プーサンにより独立に証明され、現在では素数定理と呼ばれている。彼らの証明は、リーマンゼータ関数の性質を用いている。
長い間、解析的方法を用いなければ素数定理を証明することはできないと信じられていたが[5]、1948年頃、セルバーグとエルデシュは複素解析を用いない素数定理の証明を(ほぼ独立に)発見した[6]。それらの証明では、数論的関数の初等的評価のみを用いていた。
リーマン予想との関係編集
- 詳細は「リーマンの素数公式」を参照
1859年リーマンは、π(x) をゼータ関数の零点を用いて表す式を発見した[5]。
ここで は、
と定義され、和の ρ はゼータ関数の全ての零点をわたる。
- また、リーマン予想と下の式が正しいことは同値である。
また、 は、ランダウの記号である。 また、リーマン予想が正しい場合、以下の式が成り立つことが知られている。[7]
数表編集
以下に π(x), x / ln x および li x の3つの関数を10の冪において比較した表を掲載する[3][8][9][10] 。
x | π(x) | π(x) − x / ln x | li x − π(x) | x / π(x) |
---|---|---|---|---|
10 | 4 | −0.3 | 2.2 | 2.500 |
102 | 25 | 3.3 | 5.1 | 4.000 |
103 | 168 | 23 | 10 | 5.952 |
104 | 1,229 | 143 | 17 | 8.137 |
105 | 9,592 | 906 | 38 | 10.425 |
106 | 78,498 | 6,116 | 130 | 12.740 |
107 | 664,579 | 44,158 | 339 | 15.047 |
108 | 5,761,455 | 332,774 | 754 | 17.357 |
109 | 50,847,534 | 2,592,592 | 1,701 | 19.667 |
1010 | 455,052,511 | 20,758,029 | 3,104 | 21.975 |
1011 | 4,118,054,813 | 169,923,159 | 11,588 | 24.283 |
1012 | 37,607,912,018 | 1,416,705,193 | 38,263 | 26.590 |
1013 | 346,065,536,839 | 11,992,858,452 | 108,971 | 28.896 |
1014 | 3,204,941,750,802 | 102,838,308,636 | 314,890 | 31.202 |
1015 | 29,844,570,422,669 | 891,604,962,452 | 1,052,619 | 33.507 |
1016 | 279,238,341,033,925 | 7,804,289,844,393 | 3,214,632 | 35.812 |
1017 | 2,623,557,157,654,233 | 68,883,734,693,281 | 7,956,589 | 38.116 |
1018 | 24,739,954,287,740,860 | 612,483,070,893,536 | 21,949,555 | 40.420 |
1019 | 234,057,667,276,344,607 | 5,481,624,169,369,960 | 99,877,775 | 42.725 |
1020 | 2,220,819,602,560,918,840 | 49,347,193,044,659,701 | 222,744,644 | 45.028 |
1021 | 21,127,269,486,018,731,928 | 446,579,871,578,168,707 | 597,394,254 | 47.332 |
1022 | 201,467,286,689,315,906,290 | 4,060,704,006,019,620,994 | 1,932,355,208 | 49.636 |
1023 | 1,925,320,391,606,803,968,923 | 37,083,513,766,578,631,309 | 7,250,186,216 | 51.939 |
1024 | 18,435,599,767,349,200,867,866 | 339,996,354,713,708,049,069 | 17,146,907,278 | 54.243 |
1025 | 176,846,309,399,143,769,411,680 | 3,128,516,637,843,038,351,228 | 55,160,980,939 | 56.546 |
1026 | 1,699,246,750,872,437,141,327,603 | 28,883,358,936,853,188,823,261 | 155,891,678,121 | 58.850 |
オンライン整数列大辞典において π(x) , π(x) − x / ln x、li x − π(x) の値はそれぞれA006880, A057835, A057752に掲載されている。
π(1024) の値は初めJ. Buethe、J. Franke、A. Jost、およびT. Kleinjungらによりリーマン予想の仮定の下で計算されたが[11] 、後にD. J. Plattによりコンピュータを用いて検証された[12]。
π(x) の公式編集
上述のルジャンドルやリーマンらによる公式以外にも、π(x) を表す公式がいくつか存在する。例えばWilliansは、ウィルソンの定理に基づき次の初等的な公式を与えている[5]。
ここで は、ガウス記号を用いて
と定義される関数である。これが π(x) を表す理由は単純で、F(j) は合成数ならば 0、その他の値に対しては 1 を取るからである。ウィルソンの定理と同様、この公式も実用的な計算には用いることができない。
その他、ドイツの数学者Meisselによる巧妙な漸化関係を持つ公式などが知られている[5]。Meisselは1885年自身の公式を用いて π(109) の値を求めた。
不等式編集
π(x) と xln x の関係として以下の不等式が知られている[13]。
左の不等号は x ≥ 17 で、右の不等号は x > 1 で成り立つ。
- (ただし x ≥ 599)
- (ただし x ≥ 1)
- (ただし x ≥ 5393)
- (ただし x ≥ 60184)
- (ただし x ≥ 88783)
- (ただし x ≥ 2953652287)
を示した[14]。
関連項目編集
出典編集
- ^ Bach, Eric; Shallit, Jeffrey (1996). Algorithmic Number Theory. MIT Press. volume 1 page 234 section 8.8. ISBN 0-262-02405-5
- ^ Weisstein, Eric W. "Prime Counting Function". MathWorld (英語).
- ^ a b “How many primes are there?”. Chris K. Caldwell. 2008年12月2日閲覧。
- ^ Dickson, Leonard Eugene (2005). History of the Theory of Numbers, Vol. I: Divisibility and Primality. Dover Publications. ISBN 0-486-44232-2
- ^ a b c d e f g h Paulo Ribenboim著 吾郷 孝視訳編 『素数の世界』2001年、共立出版
- ^ Ireland, Kenneth; Rosen, Michael (1998). A Classical Introduction to Modern Number Theory (Second ed.). Springer. ISBN 0-387-97329-X
- ^ Schoenfeld, Lowell (1976). “Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II”. Mathematics of Computation (American Mathematical Society) 30 (134): 337–360. doi:10.2307/2005976. ISSN 0025-5718. JSTOR 2005976. MR0457374.
- ^ “Tables of values of pi(x) and of pi2(x)”. Tomás Oliveira e Silva. 2008年9月14日閲覧。
- ^ “Values of π(x) and Δ(x) for various x's”. Andrey V. Kulsha. 2008年9月14日閲覧。
- ^ “A table of values of pi(x)”. Xavier Gourdon, Pascal Sebah, Patrick Demichel. 2008年9月14日閲覧。
- ^ “Conditional Calculation of pi(1024)”. Chris K. Caldwell. 2010年8月3日閲覧。
- ^ “Computing π(x) Analytically)”. 2012年7月25日閲覧。
- ^ Rosser, J. Barkley; Schoenfeld, Lowell (1962). “Approximate formulas for some functions of prime numbers”. Illinois J. Math. 6: 64–94. ISSN 0019-2082. Zbl 0122.05001 .
- ^ Dusart, Pierre. “"ESTIMATES OF SOME FUNCTIONS OVER PRIMES WITHOUT R.H."”. arxiv.org. 2014年4月22日閲覧。
外部リンク編集
- Chris Caldwell, The Nth Prime Page at The Prime Pages.
- Tomás Oliveira e Silva, Tables of prime-counting functions.