In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the prime-counting function is the
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
counting the number of
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s less than or equal to some
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
''x''.
It is denoted by (''x'') (unrelated to the
number ).
History
Of great interest in
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
is the
growth rate of the prime-counting function.
It was
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...
d in the end of the 18th century by
Gauss
Johann Carl Friedrich Gauss (; german: GauĂ ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
and by
Legendre to be approximately
:
where log is the
natural logarithm
The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
, in the sense that
:
This statement is the
prime number theorem
In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying ...
. An equivalent statement is
:
where li is the
logarithmic integral
In mathematics, the logarithmic integral function or integral logarithm li(''x'') is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is a ...
function. The prime number theorem was first proved in 1896 by
Jacques Hadamard
Jacques Salomon Hadamard (; 8 December 1865 â 17 October 1963) was a French mathematician who made major contributions in number theory, complex analysis, differential geometry and partial differential equations.
Biography
The son of a teac ...
and by
Charles de la Vallée Poussin independently, using properties of the
Riemann zeta function
The Riemann zeta function or EulerâRiemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
introduced by
Riemann
Georg Friedrich Bernhard Riemann (; 17 September 1826 â 20 July 1866) was a German mathematician who made contributions to analysis, number theory, and differential geometry. In the field of real analysis, he is mostly known for the first rig ...
in 1859. Proofs of the prime number theorem not using the zeta function or
complex analysis
Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates Function (mathematics), functions of complex numbers. It is helpful in many branches of mathemati ...
were found around 1948 by
Atle Selberg
Atle Selberg (14 June 1917 â 6 August 2007) was a Norwegian mathematician known for his work in analytic number theory and the theory of automorphic forms, and in particular for bringing them into relation with spectral theory. He was awarde ...
and by
Paul ErdĆs (for the most part independently).
In 1899,
de la Vallée Poussin proved that
(see also Theorem 23 of)
:
for some positive constant . Here, is the
big notation.
More precise estimates of
are now known. For example, in 2002,
Kevin Ford proved that
:
Mossinghoff and Trudgian proved an explicit upper bound for the difference between
and
:
:
for
.
For most values of
we are interested in (i.e., when
is not unreasonably large)
is greater than
. However,
is known to change sign infinitely many times. For a discussion of this, see
Skewes' number
In number theory, Skewes's number is any of several large numbers used by the South African mathematician Stanley Skewes as upper bounds for the smallest natural number x for which
:\pi(x) > \operatorname(x),
where is the prime-counting function ...
.
Exact form
For
let
when
is a prime number, and
otherwise. Of profound importance,
Bernhard Riemann
Georg Friedrich Bernhard Riemann (; 17 September 1826 â 20 July 1866) was a German mathematician who made contributions to analysis, number theory, and differential geometry. In the field of real analysis, he is mostly known for the first rig ...
proved that
is equal to
:
where
:
is the
Möbius function
The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most of ...
, is the
logarithmic integral function
In mathematics, the logarithmic integral function or integral logarithm li(''x'') is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is a ...
, ''Ï'' indexes every zero of the
Riemann zeta function
The Riemann zeta function or EulerâRiemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
, and is not evaluated with a
branch cut but instead considered as where is the
exponential integral
In mathematics, the exponential integral Ei is a special function on the complex plane.
It is defined as one particular definite integral of the ratio between an exponential function and its argument.
Definitions
For real non-zero values of  ...
. If the trivial zeros are collected and the sum is taken ''only'' over the non-trivial zeros ''Ï'' of the
Riemann zeta function
The Riemann zeta function or EulerâRiemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
, then
may be approximated by
:
The
Riemann hypothesis
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...
suggests that every such non-trivial zero lies along .
Table of (''x''), ''x'' / log ''x'', and li(''x'')
The table shows how the three functions (''x''), ''x'' / log ''x'' and li(''x'') compare at powers of 10. See also,
and
:
![Prime number theorem ratio convergence](https://upload.wikimedia.org/wikipedia/commons/8/87/Prime_number_theorem_ratio_convergence.svg)
In the
On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to t ...
, the (''x'') column is sequence , is sequence , and is sequence .
The value for (10
24) was originally computed by J. Buethe,
J. Franke, A. Jost, and T. Kleinjung assuming the
Riemann hypothesis
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...
.
It was later verified unconditionally in a computation by D. J. Platt.
The value for (10
25) is due to J. Buethe,
J. Franke, A. Jost, and T. Kleinjung.
The value for (10
26) was computed by D. B. Staple.
All other prior entries in this table were also verified as part of that work.
The value for 10
27 was announced in 2015 by David Baugh and Kim Walisch.
The value for 10
28 was announced in 2020 by David Baugh and Kim Walisch.
The value for 10
29 was announced in 2022 by David Baugh and Kim Walisch.
Algorithms for evaluating (''x'')
A simple way to find
, if
is not too large, is to use the
sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime n ...
to produce the primes less than or equal to
and then to count them.
A more elaborate way of finding
is due to
Legendre (using the
inclusionâexclusion principle
In combinatorics, a branch of mathematics, the inclusionâexclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
: , A \cu ...
): given
, if
are distinct prime numbers, then the number of integers less than or equal to
which are divisible by no
is
:
(where
denotes the
floor function
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...
). This number is therefore equal to
:
when the numbers
are the prime numbers less than or equal to the square root of
.
The MeisselâLehmer algorithm
In a series of articles published between 1870 and 1885,
Ernst Meissel
Daniel Friedrich Ernst Meissel (31 July 1826, Eberswalde, Brandenburg Province â 11 March 1895, Kiel) was a German astronomer who contributed to various aspects of number theory.
See also
*MeisselâLehmer algorithm
*MeisselâMertens constant
...
described (and used) a practical combinatorial way of evaluating
. Let
be the first
primes and denote by
the number of natural numbers not greater than
which are divisible by no
where
. Then
:
Given a natural number
, if
and if
, then
:
Using this approach, Meissel computed
, for
equal to 5, 10
6, 10
7, and 10
8.
In 1959,
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer (February 23, 1905 â May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Ădouard Lucas' work in the 1930s and ...
extended and simplified Meissel's method. Define, for real
and for natural numbers
and
,
as the number of numbers not greater than ''m'' with exactly ''k'' prime factors, all greater than
. Furthermore, set
. Then
:
where the sum actually has only finitely many nonzero terms. Let
denote an integer such that
, and set
. Then
and
when
. Therefore,
:
The computation of
can be obtained this way:
:
where the sum is over prime numbers.
On the other hand, the computation of
can be done using the following rules:
#
#
Using his method and an
IBM 701, Lehmer was able to compute the correct value of
and missed the correct value of
by 1.
Further improvements to this method were made by Lagarias, Miller, Odlyzko, Deléglise and Rivat.
Other prime-counting functions
Other prime-counting functions are also used because they are more convenient to work with. One is Riemann's prime-power counting function, usually denoted as
or
. This has jumps of 1/''n'' for prime powers ''p''
''n'', with it taking a value halfway between the two sides at discontinuities. That added detail is used because then the function may be defined by an inverse
Mellin transform In mathematics, the Mellin transform is an integral transform that may be regarded as the multiplicative version of the two-sided Laplace transform. This integral transform is closely connected to the theory of Dirichlet series, and is
often used i ...
. Formally, we may define
by
:
where ''p'' is a prime.
We may also write
:
where
is the
von Mangoldt function
In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive.
Definition
The von Mango ...
and
:
The
Möbius inversion formula
In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 1832 by August Ferdinand Möbius.
A large gener ...
then gives
:
Knowing the relationship between the logarithm of the
Riemann zeta function
The Riemann zeta function or EulerâRiemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
and the
von Mangoldt function
In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive.
Definition
The von Mango ...
, and using the
Perron formula we have
:
The
Chebyshev function
In mathematics, the Chebyshev function is either a scalarising function (Tchebycheff function) or one of two related functions. The first Chebyshev function or is given by
:\vartheta(x)=\sum_ \ln p
where \ln denotes the natural logarithm, ...
weights primes or prime powers ''p''
''n'' by log(''p''):
:
:
Formulas for prime-counting functions
Formulas for prime-counting functions come in two kinds: arithmetic formulas and analytic formulas. Analytic formulas for prime-counting were the first used to prove the
prime number theorem
In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying ...
. They stem from the work of Riemann and
von Mangoldt, and are generally known as
explicit formulas.
We have the following expression for ''Ï'':
:
where
:
Here ''Ï'' are the zeros of the
Riemann zeta function
The Riemann zeta function or EulerâRiemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
in the critical strip, where the real part of ''Ï'' is between zero and one. The formula is valid for values of ''x'' greater than one, which is the region of interest. The sum over the roots is conditionally convergent, and should be taken in order of increasing absolute value of the imaginary part. Note that the same sum over the trivial roots gives the last
subtrahend
Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peachesâmeaning 5 peaches with 2 taken ...
in the formula.
For
we have a more complicated formula
:
![Riemann Explicit Formula](https://upload.wikimedia.org/wikipedia/commons/8/89/Riemann_Explicit_Formula.gif)
Again, the formula is valid for ''x'' > 1, while ''Ï'' are the nontrivial zeros of the zeta function ordered according to their absolute value. The integral is equal to the series over the trivial zeros:
:
The first term li(''x'') is the usual
logarithmic integral function
In mathematics, the logarithmic integral function or integral logarithm li(''x'') is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is a ...
; the expression li(''x''
''Ï'') in the second term should be considered as Ei(''Ï'' log ''x''), where Ei is the
analytic continuation
In complex analysis, a branch of mathematics, analytic continuation is a technique to extend the domain of definition of a given analytic function. Analytic continuation often succeeds in defining further values of a function, for example in a n ...
of the
exponential integral
In mathematics, the exponential integral Ei is a special function on the complex plane.
It is defined as one particular definite integral of the ratio between an exponential function and its argument.
Definitions
For real non-zero values of  ...
function from negative reals to the complex plane with branch cut along the positive reals.
Thus,
Möbius inversion formula
In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 1832 by August Ferdinand Möbius.
A large gener ...
gives us
:
valid for ''x'' > 1, where
:
is Riemann's R-function
and is the
Möbius function
The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most of ...
. The latter series for it is known as
Gram
The gram (originally gramme; SI unit symbol g) is a Physical unit, unit of mass in the International System of Units (SI) equal to one one thousandth of a kilogram.
Originally defined as of 1795 as "the absolute weight of a volume of pure wate ...
series.
Because
for all
, this series converges for all positive ''x'' by comparison with the series for
. The logarithm in the Gram series of the sum over the non-trivial zero contribution should be evaluated as
and not
.
Folkmar Bornemann proved, when assuming the
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...
that all zeros of the Riemann zeta function are simple,
[ Montgomery showed that (assuming the Riemann hypothesis) at least 2/3 of all zeros are simple.] that
:
where
runs over the non-trivial zeros of the Riemann zeta function and
.
The sum over non-trivial zeta zeros in the formula for
describes the fluctuations of
while the remaining terms give the "smooth" part of prime-counting function,
so one can use
:
as a good estimator of
for ''x'' > 1. In fact, since the second term approaches 0 as
, while the amplitude of the "noisy" part is heuristically about
estimating
by
alone is just as good, and fluctuations of the
distribution of primes may be clearly represented with the function
:
Inequalities
Here are some useful inequalities for (''x'').
:
for ''x'' â„ 17.
The left inequality holds for ''x'' â„ 17 and the right inequality holds for ''x'' > 1. The constant 1.25506 is
to 5 decimal places, as
has its maximum value at ''x'' = 113.
Pierre Dusart
Pierre Dusart is a French mathematician at the Université de Limoges who specializes in number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the ...
proved in 2010:
:
for
, and
:
for
.
Here are some inequalities for the ''n''th prime, ''p''
''n''. The upper bound is due to Rosser (1941), the lower one to Dusart (1999):
for ''n'' â„ 6.
The left inequality holds for ''n'' â„ 2 and the right inequality holds for ''n'' â„ 6.
An approximation for the ''n''th prime number is
:
Ramanujan proved that the inequality
:
holds for all sufficiently large values of
.
In
Dusart proved (Proposition 6.6) that, for
,
:
and (Proposition 6.7) that, for
,
:
More recently, Dusart
has proved (Theorem 5.1) that, for
,
:
,
and that, for
,
:
The Riemann hypothesis
The
Riemann hypothesis
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...
implies a much tighter bound on the error in the estimate for
, and hence to a more regular distribution of prime numbers,
:
Specifically,
:
See also
*
Foias constant
*
Bertrand's postulate
*
Oppermann's conjecture
*
Ramanujan prime
References
Notes
External links
*Chris Caldwell
''The Nth Prime Page''at The
Prime Pages The PrimePages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin.
The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" ...
.
*TomĂĄs Oliveira e Silva
Tables of prime-counting functions
{{DEFAULTSORT:Prime-Counting Function
Analytic number theory
Prime numbers
Arithmetic functions