Prime counting function

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

.

Algorithms

There are several efficient algorithms for computing the value of 

π (x)

which fall into the two categories of

• combinatorial algorithms (which calculate the number of primes by inclusion-exclusion),
• analytic algorithms (which calculate the Riemann zeta function 

  ζ (x)

  or other functions to high precision).

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

$D_{\{\pi (n)\}}(s):=\sum _{n=1}^{\infty }{\frac {\pi (n)}{n^{s}}}=\sum _{i=1}^{\infty }{\frac {s^{p_{i}}}{1-s}}={\frac {b(s)}{1-s}},\,$

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

$\pi (x)\sim {\frac {x}{\log x}},\,$

since

$\lim _{x\to \infty }{\frac {\pi (x)\log x}{x}}=1.\,$

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

)

$\pi _{k}(x)\sim {\frac {x}{\log x}}{\frac {(\log \log x)^{k-1}}{(k-1)!}}.\,$

Alternate definitions

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

$\pi (n):=\sum _{i=1}^{n}\chi _{\{{\mbox{prime}}\}}(i)=\sum _{i=1}^{n}[\gcd(i,\lfloor {\sqrt {i}}\rfloor \#)=1],\,$

where 

n#

is the primorial of 

n

and 

[·]

is the Iverson bracket.

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

$\pi (x)=\sum _{i=1}^{\lfloor x\rfloor }\chi _{\{{\mbox{prime}}\}}(i).\,$

We could also define it as

$\pi (x)=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{0}(i)=i^{0}+1]=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{0}(i)=2],\,$

where 

[·]

is the Iverson bracket, or as

$\pi (x)=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{1}(i)=i^{1}+1]=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{1}(i)=i+1],\,$

or (is the following true?)

$(?)\ \pi (x)=\sum _{i=1}^{\lfloor x\rfloor }[\sigma _{k}(i)=i^{k}+1],\,$

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 

b n

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 

≤   2 n, 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 2 n = PiPrime(A001146), n   ≥   0

.

 

{1, 2, 6, 54, 6542, 203280221, ...}

The primes up to 

2 2 n

are exactly determined from the primes up to 

2 2 n   − 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 2 n, 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 

< e n, 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 

< 10 n, n   ≥   0

.

 

{0, 4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534, 455052511, 4118054813, 37607912018, 346065536839, 3204941750802, 29844570422669, 279238341033925, 2623557157654233, ...}

See also

• Characteristic function of prime numbers