A couple of weeks ago we posted an article on “Calculus for Cats” and the Prime Number Theorem, which featured the, the prime-counting function π(x):

Basically, this function counts the number of primes less than or equal to a particular number. For example π(20) would be all the prime numbers less than 20: 2, 3, 5, 7, 11, 13, 17 and 19. So π(20) = 8.

So to calculate π(1000) would one have to literally count all the prime numbers less than 1000, including figuring out which numbers are prime? And what about π(1000000)? Unfortunately, the answer is yes.

Unfortunately, the answer is no, as Victor points out in the comments. Or more specifically, Victor's cat Blue Chip says “Neow!” I think is the point where one is supposed to say “my bad.” Victor is in fact V. S. Miller who co-authored the paper “Computing pi(x): The Meissel-Lehmer Method”.

The oldest method for computing π(x) is to use the sieve of Eratosthenes, which is literally counting all the primes below x. More efficient methods have existed for quite a while, notably astronomer E. D. F. Meissel found a method in the 1870s that he used to compute π(100,000,000) as 5,761,455; and π(1,000,000,000), though his result was found to be slightly off (too small by 56). It should be noted that Meissel carried out his calculations without the aid of a digital computer. D.H. Lemher extended and simplified Meissel's method in the context of modern computers, and calculated π(10¹⁰).

Miller and his co-authors present new algorithms that refine the Meissel-Lehmer method, including new sieving techniques and optimizations for parallel computing. Those interested in the technique are encouraged to read the paper. The “Extended Meiseel-Lehmer” technique is used to compute π(10¹⁶) as 279,238,341,033,925.

They also include an interesting chart comparing large values of π(x) and Li (x), the offset logarithmic integral that we presented in our article. Recall that Li(x) is an upper bound on the value of π(x). And for 10¹⁶, the difference between Li(x) and π(x) is 3,214,632. Only off by three million, which isn't too bad…

This post was included in Carnival of Mathematics #33 at Walking Randomly.