Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index

Chapter 4 Notes > Section 4 > Page 909 > Note (d) Previous note-----Next note
Notes for: Systems Based on Numbers | The Sequence of Primes

*Results about primes

Prime[n] is given approximately by n Log[n] + n Log[Log[n]]. (Prime[10^9] is 22,801,763,489 while the approximation gives 2.38 × 10^10.) A first approximation to PrimePi[n] is n/Log[n]. A somewhat better approximation is LogIntegral[n], equal to Integrate[1/Log[t], {t, 2, n}]. This was found empirically by Carl Friedrich Gauss in 1792, based on looking at a table of primes. (PrimePi[10^9] is 50,847,534 while LogIntegral[10^9] is about 50,849,235.) A still better approximation is obtained by subtracting Sum[LogIntegral[n^ri], {i, -∞,∞}] where the ri are the complex zeros of the Riemann zeta function Zeta[s], discussed on page 918. According to the Riemann Hypothesis, the difference between PrimePi[n] and LogIntegral[n] is of order Sqrt[n] Log[n]. More refined analytical estimates of PrimePi[n] are good enough that they are used by Mathematica to compute Prime[n] for large n.

It is known that the ratio of the number of primes of the form 4k+1 and 4k+3 asymptotically approaches 1, but almost nothing has been proved about the fluctuations.

The gap between successive primes Prime[n] - Prime[n-1] is thought to grow on average at most like Log[Prime[n]]^2. It is known that for sufficiently large n a gap of any size must exist. It is believed but not proved that there are an infinite number of "twin primes" with a gap of exactly 2.


Page image


Pages related to this note:


All notes on this page:

* History of primes
* Finding primes
* Decimation systems
* Divisors
* Results about primes
* History of number theory
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note