This site is supported by donations to The OEIS Foundation.

Prime counting function

From OeisWiki
Jump to: navigation, search
As an arithmetic function defined over the positive integers, the prime counting function
π (x)
counts how many primes there are up to
x
.
π (x) = 0
for
x < 2
.
For example,
π (100) = 25
since the set of primes up to
100
is
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
.

A000720
pi (n)
, the number of primes
  ≤   n
. (Sometimes called
PrimePi (n)
to distinguish it from the number
3.14159...
)
{0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, ...}
The sequence gives
π (x)
for integer values of
x
starting with
x = 1
. Note that although the value of the stepwise function is always an integer, its argument may be any real number, rational or irrational. Thus,
π(
22
7
) = 2, π (π) = 2
and
π (e) = 1
.[1]

Algorithms

There are several efficient algorithms for computing the value of
π (x)
which fall into the two categories of


The value is available in PARI/GP as "primepi(x)" and "PrimePi[x] in Mathematica.

Dirichlet generating function

The Dirichlet generating function for the prime counting function is

where
pi
is the
i
th prime and
b (s)
is the Dirichlet generating function for the characteristic function of prime numbers (A010051).

Asymptotic behavior

The prime number theorem gives us a means to obtain an estimate which becomes more accurate (in terms of relative error) the larger
x
is
[2]

since

[3]
In Wilson's prime recurrence
Wn
(see A007097), we have
π (Wn) = Wn   − 1
, since
Wn
is the
Wn   − 1
th prime. We could consider the prime counting function to be the specific case
π1(x)
of the function
πk (x)
which tallies how many numbers up to
x
have
k
prime factors. From the prime number theorem we can derive the following approximation (when
k = 1
, the whole second multiplicand becomes just
1
)

Alternate definitions

The prime-counting function is the summatory function of the characteristic function of prime numbers

where
n#
is the primorial of
n
and
[·]
is the Iverson bracket.

As an arithmetic function defined over the real numbers, we get

We could also define it as

where
[·]
is the Iverson bracket, or as

or (is the following true?)

with
σ0(n)
(
τ (n)
, tau(n)) being the number of divisors function,
σ1(n)
(
σ (n)
, sigma(n)) being the sum of divisors function and
σk (n)
(divisor function) being the sum of kth powers of divisors function.

Number of primes less than b^n

The number of primes less than or equal to
bn
gives the number of divisions required to determine the primality of
b 2n
by trial division.

Number of primes less than or equal to 2^n

A007053 Number of primes
  ≤   2n, n   ≥   0
.
{0, 1, 2, 4, 6, 11, 18, 31, 54, 97, 172, 309, 564, 1028, 1900, 3512, 6542, 12251, 23000, 43390, 82025, 155611, 295947, 564163, 1077871, 2063689, 3957809, 7603553, 14630843, 28192750, 54400028, ...}

Number of primes less than or equal to 2^(2^n)

A153450 Number of primes
  ≤   2 2n = PiPrime(A001146), n   ≥   0
.
{1, 2, 6, 54, 6542, 203280221, ...}
The primes up to
2 2n
are exactly determined from the primes up to
2 2n   − 1, n   ≥   1,
with the sieve of Eratosthenes. This gives an inductive algorithm to find all primes up to any integer (modulo space and time constraints...) This means that all odd primes are ultimately determined by the only even prime, namely 2, the oddest prime... The primes less than or equal to
2 2n, n   ≥   0,
where each subset is exactly determined by the preceding subset, are
{{2}, {2, 3}, {2, 3, 5, 7, 11, 13}, {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251}, ...}

Number of primes less than e^n

A040014 Number of primes
< en, n   ≥   0
.
{0, 1, 4, 8, 16, 34, 79, 183, 429, 1019, 2466, 6048, 14912, 37128, 93117, 234855, 595341, 1516233, 3877186, 9950346, 25614562, 66124777, 171141897, 443963543, 1154106844, 3005936865, ...}

Number of primes less than 10^n

A006880 Number of primes
< 10n, n   ≥   0
.
{0, 4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534, 455052511, 4118054813, 37607912018, 346065536839, 3204941750802, 29844570422669, 279238341033925, 2623557157654233, ...}

See also

Notes

  1. π (x)
    being the prime counting function while
    π
    is the constant pi,
    ϕ
    being the Golden ratio.
  2. In number theory, the function
    log x
    always refers to the natural logarithm, i.e. the logarithm to the base
    e
    ,
    loge x
    ,
    e
    being Euler's number. The reason this needs to be clarified here is that in the slew of books on the Riemann hypothesis that came out before Dan Rockmore's Stalking the Riemann Hypothesis, you will more likely see this formula stated with "ln" rather than "log".
  3. Manfred R. Schroeder, Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing and Self-Similarity, 5th Ed. Springer (2009) p. 50.