Over 2000 years ago,
Euclid proved that the number of
primes is
infinite. This brings up two questions:
- How many primes are there less than the number x?
- How big is the infinity of primes?
To begin with, create a function called pi(x). This value of pi(x) is the number of primes less than or equal to x. The primes that are under 25 are: 2, 3, 5, 7, 11, 13, 17, 19, and 23. Hence, pi(3) = 2; pi(10) = 4; and pi(25) = 9. Plotted out over a larger area, this looks like:
25.................................................................................................****
******** .
****** . .
**** . .
****** . . .
20.......................................................................**............................
**** . . .
****** . . . .
** . . . .
****** . . . . .
15...............................................******................................................
**** . . . . . .
** . . . . . .
**** . . . . . .
****** . . . . . . .
10.............................**......................................................................
****** . . . . . . . .
**** . . . . . . . .
** . . . . . . . . .
**** . . . . . . . . .
5...........**........................................................................................
**** . . . . . . . . .
** . . . . . . . . . .
** . . . . . . . . . .
1 * . . . . . . . . . .
0 * . . . . . . . . . .
01234567891123456789212345678931234567894123456789512345678961234567897123456789812345678991234567891
0 0 0 0 0 0 0 0 0 0
0
While pi(x) is "locally" irregular, there is a trend to its values. This function smooths out if viewed from a large enough range.
For values of x less than 1010, the easiest way to compute pi(x) is to just count the primes. Long before the days of the computers, tables of primes were formed. The most distributed table was that of D. N. Lehmer's table of primes up to 10,006,721. Kulik completed a table of primes up to 100,330,200 in 1867.
In the 1870's, Meissel found a way to compute pi(x) for values far beyond x = 108. He attempted to calculate (and was slightly off), pi(109). Meissel's methods were simplified by Lehmer in 1959 and then again in 1985 using sieve techniques by Lagaris, Miller, and Odlyzko.
In 1994, Deléglise and Rivat improved the technique again to find pi(1017) and pi(1018). Deléglise continued on to find pi(1020 and other values in 1996 (pi(4185296581467695669) = 100,000,000,000,000,000). In October 2000, Xavier Gourdon's distributed
computing project calculated pi(1021). pi(1022) was calculated in December 2000 to be 201,467,286,689,315,906,290. This project continues and can be found at http://xavier.gourdon.free.fr/Constants/Primes/countingPrimes.html.
The distribution of primes seems to be random, the function pi(x) is very well behaved. It has been proved that the number of primes not exceeding x is asymptotic to x/ln(x)
pi(x) ~ x/ln(x)
This has several consequences:
- It is possible to approximate pi(x) with x/(ln(x-1)).
I recently was asked what percent of primes are there between 4,000,000 and 5,000,000. Knowing
this approximation, its fairly easy to come to a very close guess:
(pi(5,000,000) - pi(4,000,000))/1,000,000
5,000,000/(log(5,000,000)-1) - 4,000,000/(log(4,000,000) - 1) = 64967
About 6.5% of the numbers between 4,000,000 and 5,000,000 are prime.
- The nth prime is about n*ln(n)
- The chance of a random integer x being prime is approximately 1/ln(x)
Primary source: http://www.utm.edu/research/primes/howmany.shtml