Prime Number Theorem
Number theory is the study of the set of positive whole numbers (integers) such as 1,2,3,4,5,6,7,8,....,
Prime Number Theorem is the study of the distribution of prime numbers. As we saw on the home page, Euclid proved that there is an infinite number of prime numbers. The Prime Number Theorem is the study of where these numbers lie on the number line.
It is intuitive that prime numbers are less common as we move to higher numbers and on the home page you can see a table that demonstrates this, but is there a formula to predict how many prime numbers there will be in a certain point on the number line?
Here are some attempts at predicting the frequency of prime numbers on the number line.
Gauss (1796)
Carl Frederic Gauss in 1796 (when he was 15) conjectured that the number of prime numbers less than a certain number can be predicted using the formula x/log(x). Note that log here refers to natural log, i.e.logarithm to the base e (2.71828 …).
If you look at the table below you get an idea of how good this formula is at predicting the number of primes less than a certain number.
| x | Actual Number of Primes | Predicted Number of Primes using x/log(x) | % Error |
| 10 | 4 | 4.3 | -8.57% |
| 100 | 25 | 21.7 | 13.14% |
| 1,000 | 168 | 144.8 | 13.83% |
| 10,000 | 1,229 | 1,085.7 | 11.66% |
| 100,000 | 9,592 | 8,685.9 | 9.45% |
| 1,000,000 | 78,498 | 72,382.4 | 7.79% |
| 10,000,000 | 664,579 | 620,420.7 | 6.64% |
| 100,000,000 | 5,761,455 | 5,428,681.0 | 5.78% |
| 1,000,000,000 | 50,847,534 | 48,254,942.4 | 5.10% |
| 10,000,000,000 | 455,052,511 | 434,294,481.9 | 4.56% |
You can see from the % errors that this formula is not very perfect at predicting how many primes exist.
It is interesting that the distribution of prime numbers should be in any way related to natural logs.
This formula has interesting implications
Legendre
The year after Gauss came out with his formula, Adrien-Marie Legendre modified the formula slightly. Gauss' formula was x/log(x). Legandre improved of this formula by adding a constant B to the denominator. His formula is x/(log(x)-B). He described B as a constant but did not specify a number. In 1808 he re-published his book and specified B as -1.08366.
The table below show the accuracy of Legendre's formula using B = -1.08366.
| x | Actual Number of Primes | Predicted Number of Primes using x/(log(x)-B) | % Error |
| 10 | 4 | 8.2 | -105.10% |
| 100 | 25 | 28.4 | -13.59% |
| 1,000 | 168 | 171.7 | -2.20% |
| 10,000 | 1,229 | 1,230.5 | -0.12% |
| 100,000 | 9,592 | 9,588.4 | 0.04% |
| 1,000,000 | 78,498 | 78,543.2 | -0.06% |
| 10,000,000 | 664,579 | 665,139.7 | -0.08% |
| 100,000,000 | 5,761,455 | 5,768,003.7 | -0.11% |
| 1,000,000,000 | 50,847,534 | 50,917,518.8 | -0.14% |
| 10,000,000,000 | 455,052,511 | 455,743,003.6 | -0.15% |
You can see for the number ranges here that Legandre's formula is better at predicting the number of primes.
Gauss(1849)
Carl Frederic Gauss in 1849 (or sometime before that) came up with a better formula. This one was the number of prime numbers less than a certain number can be predicted using the formula li(x) where li is the logarithmic integral. This formula is not getting really close.
| x | Actual Number of Primes | Predicted Number of Primes using li(x) | % Error |
| 10 | 4 | 6.2 | -54.13998% |
| 100 | 25 | 30.1 | -20.50457% |
| 1,000 | 168 | 177.6 | -5.72003% |
| 10,000 | 1,229 | 1,246.1 | -1.39440% |
| 100,000 | 9,592 | 9,629.8 | -0.39417% |
| 1,000,000 | 78,498 | 78,627.5 | -0.16503% |
| 10,000,000 | 664,579 | 664,918.4 | -0.05107% |
| 100,000,000 | 5,761,455 | 5,762,209.4 | -0.01309% |
| 1,000,000,000 | 50,847,534 | 50,849,235.0 | -0.00335% |
| 10,000,000,000 | 455,052,511 | 455,055,614.6 | -0.00068% |
| 100,000,000,000 | 4,118,054,813 | 4,118,066,400.6 | -0.00028% |