Approximations to the PrimePi Function

The PrimePi function (π[x]) shows the number of primes that are smaller than a certain value x. Throughout history, there have been several approximation models of the prime-counting function (π[x]). These models are important in that they reveal the long-term distribution of prime numbers (prime number theorem, or PNT) and help in the study of various mathematical concepts such as LogIntegral and Big O.

June 23, 2017—Sung Min Yoon

Distribution of Prime Numbers

Let’s first look at the simple characteristics of prime numbers.

Make a list of divisors for numbers from 2 to 10:

In[]:=

Table[Divisors[n],{n,2,10}]

Out[]=

{{1,2},{1,3},{1,2,4},{1,5},{1,2,3,6},{1,7},{1,2,4,8},{1,3,9},{1,2,5,10}}

A prime number has only have trivial divisors (i.e. 1 and itself). Thus, prime numbers have only two divisors.

Select a list of divisors with length 2 for numbers from 2 to 10:

In[]:=

Select[Table[Divisors[n],{n,2,10}],Length[Level[#,1]]2&]

Out[]=

{{1,2},{1,3},{1,5},{1,7}}

Now let’s find the number of primes that are smaller than 100.

Select prime numbers that are less than 100:

In[]:=

Select[Table[Prime[n],{n,100}],#<100&]

Out[]=

{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}

Here is the number of primes that are less than 100:

In[]:=

Length[Select[Table[Prime[n],{n,100}],#<100&]]

Out[]=

Let’s now look at the distribution of primes by looking at the number of primes that are smaller than

Make a table of values with columns

, number of primes smaller than

and frequency of primes under

In[]:=

Grid[Join[{{"n","PrimePi[n]","frequency"}},Table[{n,PrimePi[n],Round[PrimePi[n]/n,0.001]},{n,Table[10^k,{k,2,14}]}]],AlignmentLeft]

Out[]=

n	PrimePi[n]	frequency
100	25	0.25
1000	168	0.168
10000	1229	0.123
100000	9592	0.096
1000000	78498	0.078
10000000	664579	0.066
100000000	5761455	0.058
1000000000	50847534	0.051
10000000000	455052511	0.046
100000000000	4118054813	0.041
1000000000000	37607912018	0.038
10000000000000	346065536839	0.035
100000000000000	3204941750802	0.032

To see the distribution of prime numbers, let’s look at how the number of primes changes with respect to positive integer n.

Make a plot of the PrimePi function:

In[]:=

Plot[PrimePi[n],{n,0,1000},PlotRange{0,200}]

Out[]=

First Approximation to the PrimePi Function

LogIntegral Function

Further Improvements

FURTHER EXPLORATIONS

Investigate the relationship between the PrimePi function and the Riemann hypothesis

Investigate the Big O value for each number and make a better approximation model

AUTHORSHIP INFORMATION

Sung Min Yoon

6/23/17