소수 계량 함수

3. 명시적 공식

폰 망골트(von Mangoldt)는 다음 공식을 증명하였다.^[51]

:$\backslash psi(x)\; =\; x\; -\; \backslash sum\_\{\backslash rho\backslash in\; S\}\; \backslash frac\{x^\backslash rho\}\{\backslash rho\}\; -\; \backslash ln\; 2\backslash pi\; -\; \backslash frac12\; \backslash ln(1-x^\{-2\})$

여기서

• $S$는 리만 제타 함수의 임계구역(critical strip)에 있는 영점들이다.

• 합 $\backslash sum\_\{\backslash rho\backslash in\; S\}$는 절대수렴하지 않는다. 이 경우 합은 $|\backslash operatorname\{Im\}\backslash rho|$의 순으로 계산하여 수렴하게 만든다.
• 위 공식은 ''x''가 특정한 정수가 아니면서 1보다 큰 실수인 경우에 유효하다. 만약 $x$가 특정한 정수 (소수 및 소수의 자연수 거듭제곱)인 경우, 해당 점에서의 좌변의 좌극한과 우극한의 평균값이 우변과 같게 된다.

4. π(x), x/ln x, 및 li(x)의 수치적 계산 결과

위 표는 소수 계량 함수 π(''x'')와 두 근사 함수 ''x'' / ln ''x'', li(''x'')의 값을 10의 거듭제곱에서 비교한 결과를 보여준다. x가 증가함에 따라 π(x)는 ''x'' / ln ''x''와 li(''x'')에 점근적으로 가까워진다.

5. π(x) 계산 알고리즘

에라토스테네스의 체를 사용하여 $x$ 이하의 소수를 생성한 다음 그 수를 세는 것은 $\pi(x)$를 찾는 간단한 방법이다.

르장드르는 포함-배제 원리를 사용하여 $\pi(x)$를 찾는 더 정교한 방법을 제시했다. 주어진 $x$에 대해, $p_1, p_2, \dots, p_n$이 서로 다른 소수라면, $p_i$로 나누어 떨어지지 않는 $x$ 이하의 정수의 개수는 다음과 같다.

:

(여기서 $\lfloor x \rfloor$는 바닥 함수를 나타낸다). 이 수는 $p_1, p_2, \dots, p_n$이 $x$의 제곱근 이하의 소수일 때 다음과 같다.

:$\backslash pi(x)-\backslash pi\backslash left(\backslash sqrt\{x\}\backslash right)+1$

에른스트 마이즐은 1870년과 1885년 사이에 발표된 일련의 논문에서 $\pi(x)$를 평가하는 실용적인 조합적 방법을 설명하고 사용했다. $p_1, p_2, \dots, p_n$을 처음 $n$개의 소수라고 하고, $\Phi(m,n)$을 $m$보다 크지 않고 모든 $i \le n$에 대해 $p_i$로 나누어지지 않는 자연수의 개수로 나타낸다. 그러면

:$\backslash Phi(m,n)=\backslash Phi(m,n-1)-\backslash Phi\backslash left(\backslash frac\; m\; \{p\_n\},n-1\backslash right).$

자연수 $m$이 주어지고, $n = \pi(\sqrt[3]{m})$이고 $\mu = \pi(\sqrt{m}) - n$이면,

:$\backslash pi(m)\; =\; \backslash Phi(m,n)+n(\backslash mu+1)+\backslash frac\{\backslash mu^2-\backslash mu\}\; 2\; -\; 1\; -\; \backslash sum\_\{k=1\}^\backslash mu\backslash pi\backslash left(\backslash frac\; m\; \{p\_\{n+k\}\}\backslash right)\; .$

이 방식을 사용하여 메이즐은 $x$가 $5 \times 10^5$, $10^6$, $10^7$, 그리고 $10^8$일 때 $\pi(x)$를 계산했다.

데릭 헨리 레머는 1959년에 메이즐의 방법을 확장하고 단순화했다. 실수 $m$과 자연수 $n$과 $k$에 대해, $P_k(m,n)$을 $m$보다 크지 않고 정확히 $k$개의 소인수를 가지며, 모두 $p_n$보다 큰 숫자의 개수로 정의한다. 또한, $P_0(m,n) = 1$로 설정한다. 그러면

:$\backslash Phi(m,n)\; =\; \backslash sum\_\{k=0\}^\{+\backslash infty\}\; P\_k(m,n)$

여기서 합은 실제로 유한 개의 0이 아닌 항만 갖는다. $\sqrt[3]{m} \le y \le \sqrt{m}$이고 $n = \pi(y)$인 정수 $y$를 나타냅니다. 그러면 $P_1(m,n) = \pi(m) - n$이고 $k \ge 3$일 때 $P_k(m,n) = 0$이다. 따라서,

:$\backslash pi(m)\; =\; \backslash Phi(m,n)\; +\; n\; -\; 1\; -\; P\_2(m,n)$

$P_2(m,n)$의 계산은 다음과 같이 얻을 수 있다.

:

여기서 합은 소수를 대상으로 한다.

한편, $\Phi(m,n)$의 계산은 다음 규칙을 사용하여 수행할 수 있다.

# $\backslash Phi(m,0)\; =\; \backslash lfloor\; m\backslash rfloor$

# $\backslash Phi(m,b)\; =\; \backslash Phi(m,b-1)\; -\; \backslash Phi\backslash left(\backslash frac\; m\{p\_b\},b-1\backslash right)$

레머는 그의 방법과 IBM 701을 사용하여 $\pi(10^9)$의 정확한 값을 계산할 수 있었고, $\pi(10^{10})$의 정확한 값에서 1만큼 차이가 났다.^[20]

이 방법에 대한 추가 개선은 라가리아스, 밀러, 오들리즈코, 들레글리즈, 그리고 리바에 의해 이루어졌다.^[21]

6. 부등식

Pierre Dusart|피에르 뒤사르^영어가 2010년에 제시한 부등식은 다음과 같다.^[32]

:

뒤사르는 최근 다음 부등식을 증명했다.^[33]

:$\backslash frac\{x\}\{\backslash log\; x\}\; \backslash left(\; 1\; +\; \backslash frac\{1\}\{\backslash log\; x\}\; +\; \backslash frac\{2\}\{\backslash log^2\; x\}\; \backslash right)\; \backslash le\; \backslash pi(x)\; \backslash le\; \backslash frac\{x\}\{\backslash log\; x\}\; \backslash left(\; 1\; +\; \backslash frac\{1\}\{\backslash log\; x\}\; +\; \backslash frac\{2\}\{\backslash log^2\; x\}\; +\; \backslash frac\{7.59\}\{\backslash log^3\; x\}\; \backslash right)$

이 부등식은 각각 와 에 대해 성립한다.

번째 소수 에 대한 부등식은 다음과 같다.

:

왼쪽 부등식은 에 대해 성립하며, 오른쪽 부등식은 에 대해 성립한다.

2010년에 뒤사르는 다음 부등식을 증명했다.^[6]

:$n\; \backslash left(\; \backslash log\; n\; +\; \backslash log\; \backslash log\; n\; -\; 1\; +\; \backslash frac\{\backslash log\; \backslash log\; n\; -\; 2.1\}\{\backslash log\; n\}\; \backslash right)\; \backslash le\; p\_n\; \backslash le\; n\; \backslash left(\; \backslash log\; n\; +\; \backslash log\; \backslash log\; n\; -\; 1\; +\; \backslash frac\{\backslash log\; \backslash log\; n\; -\; 2\}\{\backslash log\; n\}\; \backslash right)$

이 부등식은 각각 와 에 대해 성립한다.

피에르 데저트는 2010년에 다음 6개의 부등식을 제시했다.^[50]

• (단, ''x'' ≥ 599)
• (단, ''x'' ≥ 1)
• (단, ''x'' ≥ 5393)
• (단, ''x'' ≥ 60184)
• (단, ''x'' ≥ 88783)
• (단, ''x'' ≥ 2953652287)

7. 기타 소수 계량 함수

리만의 소수 거듭제곱 계량 함수는 보통 $\Pi_0(x)$ 또는 $J_0(x)$로 표기한다. 이 함수는 소수 거듭제곱 $p^n$에서 $\frac{1}{n}$의 점프를 가지며, $\pi(x)$의 불연속점에서 양쪽 값의 중간 값을 취한다. 이러한 세부 사항은 함수가 역 멜린 변환으로 정의될 수 있기 때문에 사용된다.

공식적으로, $\Pi_0(x)$를 다음과 같이 정의할 수 있다.

:

여기서 각 합의 변수 $p$는 지정된 한계 내의 모든 소수를 나타낸다.

또한 다음과 같이 쓸 수 있다.

:$\backslash Pi\_0(x)\; =\; \backslash sum\_\{n=2\}^x\; \backslash frac\{\backslash Lambda(n)\}\{\backslash log\; n\}\; -\; \backslash frac\{\backslash Lambda(x)\}\{2\backslash log\; x\}\; =\; \backslash sum\_\{n=1\}^\backslash infty\; \backslash frac\; 1\; n\; \backslash pi\_0\backslash left(x^\{1/n\}\backslash right)$

여기서 $\Lambda$는 폰 망골트 함수이고

:$\backslash pi\_0(x)\; =\; \backslash lim\_\{\backslash varepsilon\; \backslash to\; 0\}\; \backslash frac\{\backslash pi(x-\backslash varepsilon)\; +\; \backslash pi(x+\backslash varepsilon)\}\{2\}.$

뫼비우스 반전 공식은 다음을 제공한다.

:$\backslash pi\_0(x)\; =\; \backslash sum\_\{n=1\}^\backslash infty\; \backslash frac\{\backslash mu(n)\}\{n\}\backslash \; \backslash Pi\_0\backslash left(x^\{1/n\}\backslash right),$

여기서 $\mu(n)$는 뫼비우스 함수이다.

리만 제타 함수의 로그와 폰 망골트 함수 $\Lambda$ 사이의 관계를 알고, 페론 공식을 사용하면 다음을 얻는다.

:$\backslash log\; \backslash zeta(s)\; =\; s\; \backslash int\_0^\backslash infty\; \backslash Pi\_0(x)\; x^\{-s-1\}\backslash ,\; \backslash mathrm\{d\}x$

체비쇼프 함수는 소수 또는 소수 거듭제곱 $p^n$에 $\log p$의 가중치를 부여한다.

:$\backslash begin\{align\}$

\vartheta(x) &= \sum_{p\le x} \log p \\

\psi(x)&=\sum_{p^n \le x} \log p = \sum_{n=1}^\infty \vartheta \left( x^{1/n} \right) = \sum_{n \le x}\Lambda(n) .

\end{align}

$x \ge 2$에 대해,^[22]

:$\backslash vartheta(x)\; =\; \backslash pi(x)\backslash log\; x\; -\; \backslash int\_2^x\; \backslash frac\{\backslash pi(t)\}\{t\}\backslash ,\; \backslash mathrm\{d\}t$

이고

:$\backslash pi(x)=\backslash frac\{\backslash vartheta(x)\}\{\backslash log\; x\}\; +\; \backslash int\_2^x\; \backslash frac\{\backslash vartheta(t)\}\{t\backslash log^\{2\}(t)\}\; \backslash mathrm\{d\}\; t\; .$

참조

_[1] 서적 Algorithmic Number Theory MIT Press
_[2] 웹사이트 Prime Counting Function https://mathworld.wo[...]
_[3] 웹사이트 How many primes are there? http://primes.utm.ed[...] Chris K. Caldwell 2008-12-02
_[4] 서적 History of the Theory of Numbers, Vol. I: Divisibility and Primality Dover Publications
_[5] 서적 A Classical Introduction to Modern Number Theory Springer
_[6] 서적 The Distribution of Prime Numbers Cambridge University Press 2000
_[7] 간행물 Vinogradov's Integral and Bounds for the Riemann Zeta Function https://faculty.math[...] 2002-11
_[8] 간행물 Nonnegative trigonometric polynomials and a zero-free region for the Riemann zeta-function
_[9] 웹사이트 Implementation of Riemann's Explicit Formula for Rational and Gaussian Primes in Sage http://ism.uqam.ca/~[...] 2017
_[10] 간행물 Some calculations related to Riemann's prime number formula https://www.ams.org/[...] American Mathematical Society
_[11] 웹사이트 Tables of values of π(x) and of π2(x) https://sweet.ua.pt/[...] Tomás Oliveira e Silva 2024-03-31
_[12] 웹사이트 A table of values of π(x) http://numbers.compu[...] Xavier Gourdon, Pascal Sebah, Patrick Demichel 2008-09-14
_[13] 웹사이트 Conditional Calculation of π(1024) https://t5k.org/note[...] Chris K. Caldwell 2024-03-30
_[14] 간행물 Computing π(x) Analytically 2015-05
_[15] 웹사이트 Analytic Computation of the prime-counting Function http://www.math.uni-[...] J. Buethe 2014-05-27
_[16] Thesis The combinatorial algorithm for computing π(x) http://dalspace.libr[...] Dalhousie University 2015-08-19
_[17] 웹사이트 New confirmed π(1027) prime counting function record http://www.mersennef[...] 2015-09-06
_[18] 웹사이트 New prime counting function record, pi(10^28) https://www.mersenne[...] 2020-08-30
_[19] 웹사이트 New prime counting function record: PrimePi(10^29) https://www.mersenne[...] 2022-03-04
_[20] 간행물 On the exact number of primes less than a given limit https://projecteucli[...] 2017-02-01
_[21] 간행물 Computing π(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method https://www.ams.org/[...] 1996-01
_[22] 서적 Introduction to Analytic Number Theory Springer
_[23] 서적 The Theory of Functions, 2nd ed. Oxford University Press
_[24] 웹사이트 Riemann Prime Counting Function https://mathworld.wo[...]
_[25] 서적 Prime Numbers and Computer Methods for Factorization Birkhäuser
_[26] 웹사이트 Gram Series https://mathworld.wo[...]
_[27] 웹사이트 Solution of a Problem Posed by Jörg Waldvogel http://www-m3.ma.tum[...]
_[28] 문서 Montgomery showed that (assuming the Riemann hypothesis) at least two thirds of all zeros are simple.
_[29] 웹사이트 The encoding of the prime distribution by the zeta zeros http://www.secamloca[...] Matthew Watkins 2008-09-14
_[30] 웹사이트 Ramanujan's Notebooks, Part IV https://books.google[...] Springer Science & Business Media 2012-12-06
_[31] 간행물 Approximate formulas for some functions of prime numbers https://projecteucli[...]
_[32] 간행물 Estimates of Some Functions Over Primes without R.H. 2010-02-02
_[33] 간행물 Explicit estimates of some functions over primes 2018-01
_[34] 간행물 The kth prime is greater than k(ln k + ln ln k − 1) for k ≥ 2 https://www.ams.org/[...] 1999-01
_[35] 간행물 Explicit bounds for some functions of prime numbers 1941-01
_[36] 논문 Approximate formulas for some functions of prime numbers 1962-03
_[37] 논문 New estimates for the ''n''th prime number https://cs.uwaterloo[...] 2019
_[38] 웹사이트 Bounds for ''n''-th prime https://math.stackex[...] 2015-12-31
_[39] 논문 New Estimates for Some Functions Defined Over Primes https://math.colgate[...] 2018
_[40] 논문 Effective Estimates for Some Functions Defined over Primes https://math.colgate[...] 2024
_[41] 논문 Sharper bounds for the Chebyshev functions ''θ''(''x'') and ''ψ''(''x''). II American Mathematical Society 1976
_[42] 서적 Algorithmic Number Theory MIT Press
_[43] MathWorld Prime Counting Function
_[44] 웹사이트 How many primes are there? http://primes.utm.ed[...] Chris K. Caldwell 2008-12-02
_[45] 서적 History of the Theory of Numbers, Vol. I: Divisibility and Primality Dover Publications
_[46] 서적 素数の世界 共立出版
_[47] 서적 A Classical Introduction to Modern Number Theory Springer
_[48] 논문 Sharper bounds for the Chebyshev functions ''θ''(''x'') and ''ψ''(''x''). II American Mathematical Society 1976
_[49] 논문 Approximate formulas for some functions of prime numbers 1962
_[50] 웹사이트 "ESTIMATES OF SOME FUNCTIONS OVER PRIMES WITHOUT R.H." https://arxiv.org/PS[...] arxiv.org 2014-04-22
_[51] 서적 https://books.google[...]