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

§27.12 Asymptotic Formulas: Primes

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 H. von Koch; see Crandall and Pomerance (2005, pp. 37, 60). The proof that there are infinitely many Carmichael numbers is given in Alford et al. (1994).
Keywords:: prime numbers
Referenced by:: §27.2(i), Ch.27, §6.16(ii)
Permalink:: http://dlmf.nist.gov/27.12

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

27.12.1 $\lim_{{n\to\infty}}\frac{p_{n}}{n\mathop{\mathrm{log}\,\/}\nolimits n}=1,$

Symbols:: : positive integer and $p,p_{1},\ldots$ : prime numbers
Permalink:: http://dlmf.nist.gov/27.12.E1
Encodings:: TeX, pMML, png

27.12.2 $p_{n}>n\mathop{\mathrm{log}\,\/}\nolimits n,$ $n=1,2,\dots$ .

Symbols:: : positive integer and $p,p_{1},\ldots$ : prime numbers
Permalink:: http://dlmf.nist.gov/27.12.E2
Encodings:: TeX, pMML, png

27.12.3 $\mathop{\pi\/}\nolimits\!\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 x\right\rfloor$ : floor of , $\mathop{\pi\/}\nolimits\!\left(x\right)$ : number of primes not exceeding , $p,p_{1},\ldots$ : prime numbers and : real number
Permalink:: http://dlmf.nist.gov/27.12.E3
Encodings:: TeX, pMML, png

where the series terminates when the product of the first primes exceeds .

As $x\to\infty$

27.12.4 $\mathop{\pi\/}\nolimits\!\left(x\right)\sim\sum_{{k=1}}^{{\infty}}\frac{(k-1)!% \,x}{(\mathop{\mathrm{log}\,\/}\nolimits x)^{k}}.$

Symbols:: : : factorial, $\mathop{\pi\/}\nolimits\!\left(x\right)$ : number of primes not exceeding , $\sim$ : asymptotic equality, : positive integer and : real number
Permalink:: http://dlmf.nist.gov/27.12.E4
Encodings:: TeX, pMML, png

¶ Prime Number Theorem

Keywords:: Carmichael numbers, Mersenne prime, Riemann hypothesis, multiplicative number theory, number theory, prime numbers, prime number theorem, pseudoprime test

There exists a positive constant such that

27.12.5 $\left|\mathop{\pi\/}\nolimits\!\left(x\right)-\mathop{\mathrm{li}\/}\nolimits% \!\left(x\right)\right|=\mathop{O\/}\nolimits\!\left(x\mathop{\exp\/}\nolimits% \left(-c\sqrt{\mathop{\mathrm{log}\,\/}\nolimits x}\right)\right),$ $x\to\infty$ .

Symbols:: $\mathop{O\/}\nolimits\!\left(x\right)$ : order not exceeding, $\mathop{\exp\/}\nolimits z$ : exponential function, $\mathop{\mathrm{li}\/}\nolimits\!\left(x\right)$ : logarithmic integral, $\mathop{\pi\/}\nolimits\!\left(x\right)$ : number of primes not exceeding and : real number
Permalink:: http://dlmf.nist.gov/27.12.E5
Encodings:: TeX, pMML, png

For the logarithmic integral $\mathop{\mathrm{li}\/}\nolimits\!\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 such that

27.12.6 $\left|\mathop{\pi\/}\nolimits\!\left(x\right)-\mathop{\mathrm{li}\/}\nolimits% \!\left(x\right)\right|=\mathop{O\/}\nolimits\!\left(x\mathop{\exp\/}\nolimits% \!\left(-d(\mathop{\mathrm{log}\,\/}\nolimits x)^{{3/5}}\,(\mathop{\mathrm{log% }\,\/}\nolimits\mathop{\mathrm{log}\,\/}\nolimits x)^{{-1/5}}\right)\right).$

Symbols:: $\mathop{O\/}\nolimits\!\left(x\right)$ : order not exceeding, $\mathop{\exp\/}\nolimits z$ : exponential function, $\mathop{\mathrm{li}\/}\nolimits\!\left(x\right)$ : logarithmic integral, $\mathop{\pi\/}\nolimits\!\left(x\right)$ : number of primes not exceeding , : positive integer and : real number
Permalink:: http://dlmf.nist.gov/27.12.E6
Encodings:: TeX, pMML, png

$\mathop{\pi\/}\nolimits\!\left(x\right)-\mathop{\mathrm{li}\/}\nolimits\!\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|\mathop{\pi\/}\nolimits\!\left(x\right)-\mathop{\mathrm{li}\/}\nolimits% \!\left(x\right)\right|<\frac{1}{8\pi}\sqrt{x}\,\mathop{\mathrm{log}\,\/}% \nolimits x.$

Symbols:: $\mathop{\mathrm{li}\/}\nolimits\!\left(x\right)$ : logarithmic integral, $\mathop{\pi\/}\nolimits\!\left(x\right)$ : number of primes not exceeding and : real number
Referenced by:: §27.12
Permalink:: http://dlmf.nist.gov/27.12.E7
Encodings:: TeX, pMML, png

If is relatively prime to the modulus , then there are infinitely many primes congruent to $a\;\;(\mathop{{\rm mod}}m)$ .

The number of such primes not exceeding is

27.12.8 $\frac{x}{\mathop{\phi\/}\nolimits\!\left(m\right)}+\mathop{O\/}\nolimits\!% \left(x\mathop{\exp\/}\nolimits\!\left(-\lambda(\alpha)(\mathop{\mathrm{log}\,% \/}\nolimits x)^{{1/2}}\right)\right),$ $m\leq(\mathop{\mathrm{log}\,\/}\nolimits x)^{{\alpha}}$ , $\alpha>0$ ,

Symbols:: $\mathop{O\/}\nolimits\!\left(x\right)$ : order not exceeding, $\mathop{\phi_{{k}}\/}\nolimits\!\left(n\right)$ : sum of powers of integers relatively prime to , $\mathop{\exp\/}\nolimits z$ : exponential function, : positive integer and : real number
Permalink:: http://dlmf.nist.gov/27.12.E8
Encodings:: TeX, pMML, png

where $\lambda(\alpha)$ depends only on $\alpha$ , and $\mathop{\phi\/}\nolimits\!\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 (2009) is the Mersenne prime $2^{{43,112,609}}-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\;\;(\mathop{{\rm mod}}n)$ , then 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 for which $b^{n}\equiv b\;\;(\mathop{{\rm mod}}n)$ for all $b\in\NatNumber$ . There are infinitely many Carmichael numbers.

© 2010–2013 NIST / Privacy Policy / Disclaimer / Feedback; Version 1.0.6; Release date 2013-05-06 Math-Image version (See MathML) . A Printed Companionis available. 27.11 Asymptotic Formulas: Partial Sums 27.13 Functions