Thomas R. Nicely

Current e-mail address

Last updated 0453 GMT 21 August 2009.

See "A table of prime counts pi(x) to 1e16" for an explanation of the functions pi(x), Li(x), and R(x) discussed in this paper.

Gauss and Riemann conjectured that Li(n) > pi(n) for all sufficiently large integers n. Excluded trivial exceptions include all n < 2; n=2,3,4,5,7 if Li(2, n) is used; and scattered values of n as large as n=23 if a rounded or truncated value of Li(2, n) is used. The inequality is true for all other integers for which pi(n) has been computed to date. However, it was proven by J. E. Littlewood (1914) that it is false for infinitely many values of n; more specifically, there exists a strictly monotonically increasing infinite sequence of integers over which the sign of Li(n) - pi(n) is strictly alternating. Thus there must exist an integer N > 23 such that Li(n) > pi(n) for all integers n, 23 < n < N, but Li(N) <= pi(N).

However, Littlewood's proof was not constructive, and the problem of determining an upper bound for N was first attacked by S. Skewes, who proved (1933) that the Riemann Hypothesis implies N < exp(exp(exp(79))) < 10^(10^(10^34)))---the infamous "Skewes' number." Skewes also proved a weaker (even larger) upper bound unconditionally (1955), namely N < exp(exp(exp(exp(7.7)))) < 10^(10^(10^1000))) (the final exponent can in fact be replaced by 959). In consequence, the problem of determining N, or at least confining it within ever narrower bounds, is often referred to as "Skewes' problem." R. S. Lehman (1966) improved the upper bound to N < 1.65e1165, and H. J. J. te Riele (1986) improved it to N < 6.69e370. Most recently, Carter Bays and Richard H. Hudson (2000) proved that N < 1.39822e316.

It is not entirely clear which of these upper bounds were established for Li(0, N) and which ones were established for Li(2, N). More likely than not, each one is valid for both quantities; and in any case, an upper bound valid for Li(0, N) would also be valid for the smaller quantity Li(2, N). It is also unlikely that the distinction between Li(x) < pi(x) and Li(x) <= pi(x) is relevant; indeed, I would conjecture that Li(x) cannot be an integer for any integer x > 2.

Lower bounds for N (applicable to both Li(0, N) and Li(2, N)) have been less well investigated. Apparently Gauss himself verified that N > 3000000. J. B. Rosser and L. Schoenfeld extended this to N > 1e8 ("Approximate formulas for some functions of prime numbers," Illinois J. Math. 6 (1962), 64-94). Richard P. Brent verified that N > 1e11 ("Irregularities in the distribution of primes and twin primes, " Math. Comp. 29:129 (1975), 43-56, MR 51 #5522; also Corrigendum, ibid. 30:133 (1976), 198, MR 53 #302, and Addendum, "Tables concerning irregularities in the distribution of primes and twin primes to 1e11," (August, 1975), reviewed ibid. 30:379 (1976)). Andrew Odlyzko improved the lower bound to N > 1.59e13 (1993, unpublished). Most recently, Tadej Kotnik has verified computationally that N > 10^14; see "The prime-counting function and its analytic approximations," Adv. Comput. Math. 29:55-70 (Springer, 2008, DOI 10.1007/s10444-007-9039-2). Kotnik also contributed some of the information herein presented.

Douglas A. Stoll reports the following results concerning extreme values of the discrepancies dL = Li(x) - pi(x) and dR = R(x) - pi(x). Function domains are taken to be only those integers > 1. Domains, intervals, and regions have been determined by Thomas R. Nicely.

- (Stoll, 14 November 2008) The smallest values of x for which Li(x) is closer to pi(x) than is R(x) are 2, 3445027, 3445028, 3445029, 3445030, and 3445031.
- dL has a relative minimum at x=110102617, value 238.6246724694... The domain of minimality is [33896929, U], where U > 650e9.
- The functions dL and dR have relative minima at x=330957852107,
while |dR| has a relative maximum there.
- These extreme values are
dLmin=7626.29999... ,dRmin=-16339.6068... , and|dR|max=16339.6068... - The domain of minimality of dL is [148200499927, U], where U > 650e9.
- The domain of minimality of dR is [2, 538639974870].
- The domain of maximality of |dR| is [2, 538639974870].
- The extreme point x=330957852107 is one point of the interval [330581114971, 331480917106], throughout which Li(x) is a better approximation to pi(x) than is R(x)---that is, |dL| < |dR| for every integer in the interval.

- These extreme values are
- (Nicely, 13 August 2009) The largest x known for which |dL| < |dR| is x=3.9e20, where dL=2.04676e8 and dR=-2.312923e8. This point was discovered with the assistance of the tables of pi(x) compiled by Tomás Oliveira e Silva. Clearly there is a large interval (perhaps 4e9 in radius) containing 3.9e20 throughout which this property holds.
- Both dL and dR (and their absolute values) have relative maxima at
x=36219717668608.
- These maximum values are
dLmax=369491.0622... anddRmax=161158.8897... - The domain of maximality of dL is [L, U], where L < 36219e9 and 36220e9 < U < 57583e9.
- The domain of maximality of dR is [L, U], where L < 36219e9 and 36220e9 < U < 84346e9.
- The domain of maximality of |dR| is [L, U], where L < 36219e9 and 36220e9 < U < 71811e9.

- These maximum values are
- (Nicely, 11 August 2009) At x=604346776188, R(x) approximates pi(x)
correctly to 19 significant decimal digits (63 significant bits):

This is the most accurate approximation of pi(x), by either R(x) or Li(x), of which I am aware, for any integer x > 1.x = 604346776188 pi(x) = 23167757274 R(x) = 23167757274.0000000025880346109002343123324439... R(x) - pi(x) = 2.5880346109002343123324439e-9

- Top of page
- Computer codes for Li(x) and R(x)
- Demonstration computer codes for pi(x)
- Computer codes for pi(x) implementing the Legendre-Meissel-Lehmer algorithm
- trn.zip library support files
- A table of prime counts pi(x) to 1e16
- Home page