Meissel's Formula

A modification of Legendre's formula for the prime counting function . It starts with

(1)

where  is the floor function,  is the number of integers  with , and  is the number of integers  with , and so on.

Identities satisfied by the s include

(2)

for  and

			(3)
			(4)

Meissel's formula is

(5)

where

			(6)
			(7)

Taking the derivation one step further yields Lehmer's formula.

REFERENCES:

Gram, J. "Rapport sur quelques calculs entrepris par M. Bertelsen et concernant les nombres premiers." Acta Math. 17, 301-314, 1893.

Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, p. 46, 1999.

Mathews, G. B. Ch. 10 in Theory of Numbers. New York: Chelsea, 1961.

Meissel, E. D. F. "Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde naturlicher Zahlen vorkommen." Math. Ann. 25, 251-257, 1885.

Riesel, H. "Meissel's Formula." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 12-13, 1994.

Séroul, R. "Meissel's Formula." §8.7.3 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 179-181, 2000.