27 Functions of Number Theory Multiplicative Number Theory 27.11 Asymptotic Formulas: Partial Sums 27.13 Functions

§27.12 Asymptotic Formulas: Primes

ⓘ

Keywords:: asymptotic formula, prime numbers
Notes:: See Crandall and Pomerance (2005, pp. 131–152), Davenport (2000), Narkiewicz (2000), Rosser (1939). (27.12.7) is based on results of Schoenfeld (1976) and von Koch (1901); see Crandall and Pomerance (2005, pp. 37, 60). The proof that there are infinitely many Carmichael numbers is given in Alford et al. (1994).
Referenced by:: §27.2(i), Ch.27, §6.16(ii), Erratum (V1.0.19) for Notation, Erratum (V1.0.26) for Paragraph Prime Number Theorem (in §27.12)
Permalink:: http://dlmf.nist.gov/27.12
See also:: Annotations for Ch.27

$p_{n}$ is the $n$ th prime, beginning with $p_{1}=2$ . $\pi\left(x\right)$ is the number of primes less than or equal to $x$ .

27.12.1		$\lim_{n\to\infty}\frac{p_{n}}{n\ln n}=1,$
ⓘ Symbols: $\ln\NVar{z}$ : principal branch of logarithm function, $n$ : positive integer and $p,p_{1},\ldots$ : prime numbers Permalink: http://dlmf.nist.gov/27.12.E1 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$ . See also: Annotations for §27.12 and Ch.27

27.12.2		$p_{n}>n\ln n,$
$n=1,2,\dots$ .
ⓘ Symbols: $\ln\NVar{z}$ : principal branch of logarithm function, $n$ : positive integer and $p,p_{1},\ldots$ : prime numbers Permalink: http://dlmf.nist.gov/27.12.E2 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$ . See also: Annotations for §27.12 and Ch.27

27.12.3		$\pi\left(x\right)=\left\lfloor x\right\rfloor-1-\sum_{p_{j}\leq\sqrt{x}}\left% \lfloor\frac{x}{p_{j}}\right\rfloor+\sum_{r\geq 2}(-1)^{r}\*\sum_{p_{j_{1}}<p_% {j_{2}}<\cdots<p_{j_{r}}\leq\sqrt{x}}\left\lfloor\frac{x}{p_{j_{1}}p_{j_{2}}% \cdots p_{j_{r}}}\right\rfloor,$
$x\geq 1$ ,
ⓘ Symbols: $\left\lfloor\NVar{x}\right\rfloor$ : floor of $x$ , $\pi\left(\NVar{x}\right)$ : number of primes not exceeding a number, $p,p_{1},\ldots$ : prime numbers and $x$ : real number Permalink: http://dlmf.nist.gov/27.12.E3 Encodings: TeX, pMML, png See also: Annotations for §27.12 and Ch.27

where the series terminates when the product of the first $r$ primes exceeds $x$ .

As $x\to\infty$

27.12.4		$\pi\left(x\right)\sim\sum_{k=1}^{\infty}\frac{(k-1)!\,x}{(\ln x)^{k}}.$
ⓘ Symbols: $\sim$ : Poincaré asymptotic expansion, $!$ : factorial (as in $n!$ ), $\ln\NVar{z}$ : principal branch of logarithm function, $\pi\left(\NVar{x}\right)$ : number of primes not exceeding a number, $k$ : positive integer and $x$ : real number Permalink: http://dlmf.nist.gov/27.12.E4 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$ . See also: Annotations for §27.12 and Ch.27

Prime Number Theorem

ⓘ

Keywords:: Carmichael numbers, Mersenne prime, Riemann hypothesis, equivalent statements, largest known, multiplicative number theory, number theory, prime number theorem, prime numbers, pseudoprime test
Referenced by:: Erratum (V1.0.26) for Paragraph Prime Number Theorem (in §27.12)
Update (effective with 1.0.26):: The largest known prime, which is a Mersenne prime, was updated from $2^{43,112,609}-1$ (2009) to $2^{82,589,933}-1$ (2018).
Suggested 2019-12-28 by Bill McEachen
See also:: Annotations for §27.12 and Ch.27

There exists a positive constant $c$ such that

27.12.5		$\left\|\pi\left(x\right)-\operatorname{li}\left(x\right)\right\|=O\left(x\exp% \left(-c(\ln x)^{1/2}\right)\right),$
$x\to\infty$ .
ⓘ Symbols: $O\left(\NVar{x}\right)$ : order not exceeding, $\exp\NVar{z}$ : exponential function, $\operatorname{li}\left(\NVar{x}\right)$ : logarithmic integral, $\ln\NVar{z}$ : principal branch of logarithm function, $\pi\left(\NVar{x}\right)$ : number of primes not exceeding a number and $x$ : real number Referenced by: Erratum (V1.0.18) for Equation (27.12.5) Permalink: http://dlmf.nist.gov/27.12.E5 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.18): Replaced $\sqrt{\ln x}$ with $(\ln x)^{1/2}$ to be consistent with other equations in this section. Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$ . See also: Annotations for §27.12, §27.12 and Ch.27

For the logarithmic integral $\operatorname{li}\left(x\right)$ see (6.2.8). The best available asymptotic error estimate (2009) appears in Korobov (1958) and Vinogradov (1958): there exists a positive constant $d$ such that

27.12.6		$\left\|\pi\left(x\right)-\operatorname{li}\left(x\right)\right\|=O\left(x\exp% \left(-d(\ln x)^{3/5}\,(\ln\ln x)^{-1/5}\right)\right).$
ⓘ Symbols: $O\left(\NVar{x}\right)$ : order not exceeding, $\exp\NVar{z}$ : exponential function, $\operatorname{li}\left(\NVar{x}\right)$ : logarithmic integral, $\ln\NVar{z}$ : principal branch of logarithm function, $\pi\left(\NVar{x}\right)$ : number of primes not exceeding a number, $d$ : positive integer and $x$ : real number Permalink: http://dlmf.nist.gov/27.12.E6 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$ . See also: Annotations for §27.12, §27.12 and Ch.27

$\pi\left(x\right)-\operatorname{li}\left(x\right)$ changes sign infinitely often as $x\to\infty$ ; see Littlewood (1914), Bays and Hudson (2000).

The Riemann hypothesis (§25.10(i)) is equivalent to the statement that for every $x\geq 2657$ ,

27.12.7		$\left\|\pi\left(x\right)-\operatorname{li}\left(x\right)\right\|<\frac{1}{8\pi}% \sqrt{x}\,\ln x.$
ⓘ Symbols: $\pi$ : the ratio of the circumference of a circle to its diameter, $\operatorname{li}\left(\NVar{x}\right)$ : logarithmic integral, $\ln\NVar{z}$ : principal branch of logarithm function, $\pi\left(\NVar{x}\right)$ : number of primes not exceeding a number and $x$ : real number Referenced by: §27.12 Permalink: http://dlmf.nist.gov/27.12.E7 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$ . See also: Annotations for §27.12, §27.12 and Ch.27

If $a$ is relatively prime to the modulus $m$ , then there are infinitely many primes congruent to $a\pmod{m}$ .

The number of such primes not exceeding $x$ is

27.12.8		$\frac{\operatorname{li}\left(x\right)}{\phi\left(m\right)}+O\left(x\exp\left(-% \lambda(\alpha)(\ln x)^{1/2}\right)\right),$
$m\leq(\ln x)^{\alpha}$ , $\alpha>0$ ,
ⓘ Symbols: $O\left(\NVar{x}\right)$ : order not exceeding, $\phi\left(\NVar{n}\right)$ : Euler’s totient, $\exp\NVar{z}$ : exponential function, $\operatorname{li}\left(\NVar{x}\right)$ : logarithmic integral, $\ln\NVar{z}$ : principal branch of logarithm function, $m$ : positive integer and $x$ : real number Referenced by: Erratum (V1.0.17) for Equation (27.12.8) Permalink: http://dlmf.nist.gov/27.12.E8 Encodings: TeX, pMML, png Errata (effective with 1.0.17): Originally the first term was given incorrectly by $\frac{x}{\phi\left(m\right)}$ . Reported 2017-12-04 by Gergő Nemes Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$ . See also: Annotations for §27.12, §27.12 and Ch.27

where $\lambda(\alpha)$ depends only on $\alpha$ , and $\phi\left(m\right)$ is the Euler totient function (§27.2).

A Mersenne prime is a prime of the form $2^{p}-1$ . The largest known prime (2018) is the Mersenne prime $2^{82,589,933}-1$ . For current records see The Great Internet Mersenne Prime Search.

A pseudoprime test is a test that correctly identifies most composite numbers. For example, if $2^{n}\not\equiv 2\pmod{n}$ , then $n$ is composite. Descriptions and comparisons of pseudoprime tests are given in Bressoud and Wagon (2000, §§2.4, 4.2, and 8.2) and Crandall and Pomerance (2005, §§3.4–3.6).

A Carmichael number is a composite number $n$ for which $b^{n}\equiv b\pmod{n}$ for all $b\in\mathbb{N}$ . There are infinitely many Carmichael numbers.

27.11 Asymptotic Formulas: Partial Sums 27.13 Functions

Site Privacy Accessibility Privacy Program Copyrights Vulnerability Disclosure No Fear Act Policy FOIA Environmental Policy Scientific Integrity Information Quality Standards Commerce.gov Science.gov USA.gov

§27.12 Asymptotic Formulas: Primes

Prime Number Theorem

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!