New fast methods to compute the number of primes less than a given value

G. R. P. Teruel

doi:10.37863/umzh.v74i9.6193

G. R. P. Teruel Dep. Math., IES Carru ́s, Elche-Alicante, Spain https://orcid.org/0000-0001-8363-1366

DOI: https://doi.org/10.37863/umzh.v74i9.6193

Keywords: Locker – Ernst’s

Abstract

UDC 519.688

The paper describes new fast algorithms for evaluating $\pi(x)$ inspired by the harmonic and geometric mean integrals that can be used on any pocket calculator. In particular, the formula $h(x)$ based on the harmonic mean is within $\approx 15$ of the actual value for $3\leq x\leq 10000.$ The approximation verifies the inequality, $h(x)\leq {\rm Li}(x)$ and, therefore, is better than ${\rm Li}(x)$ for small $x.$ We show that $h(x)$ and their extensions are more accurate than other famous approximations, such as Locker–Ernst's or Legendre's also for large $x.$ In addition, we derive another function $g(x)$ based on the geometric mean integral that employs $h(x)$ as an input, and allows one to significantly improve the quality of this method. We show that $g(x)$ is within $\approx 25$ of the actual value for $x\leq 50000$ (to compare ${\rm Li}(x)$ lies within $\approx 40$ for the same range) and asymptotically $g(x)\sim \dfrac{x}{\ln x}\exp\left(\dfrac{1}{\ln x-1}\right).$

References

A. M. Legendre, Essai sur la th'eorie des nombres, Courcier, Paris (1808).

C. F. Gauss, Werke, vol. II. K"onigliche Gesellschaft der Wissenschaften zu G"ottingen, 444 – 447 (1863).

G. F. B. Riemann, "Uber die Anzahl der Primzahlen unter einer gegebenen Gr"osse, Monatsber. K"onigl. Preuss. Akad. Wiss.

Berlin, 671 – 680 (1859).

Hardy, G. H. Ramanujan, Twelve lectures on subjects suggested by his life and work, 3rd ed., Chelsea, New York (1999).

J. M. Borwein, D. M. Bradley, R. E. Crandall, Computational strategies for the Riemann Zeta function, J. Comput. and Appl. Math., 121, 247 – 296 (2000). DOI: https://doi.org/10.1016/S0377-0427(00)00336-8

E. W. Weisstein, Gram series}; http://mathworld.wolfram.com/GramSeries.html.

A. E. Ingham, Ch. 5 in the distribution of prime numbers, Cambridge Univ. Press, New York (1990).

H. Riesel, Lehmer's formula, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkh"auser, Boston, MA (1994), p. 13 – 14.

D. C. Mapes, Fast method for computing the number of primes less than a given limit, Math. Comput., 17, 179 – 185 (1963). DOI: https://doi.org/10.1090/S0025-5718-1963-0158508-8

H. Riesel, Mapes!' method, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkh"auser, Boston, MA (1994), p. 23.

E. D. F. Meissel, Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde naturlicher Zahlen vorkommen, Math. Ann., 25, 251 – 257 (1885). DOI: https://doi.org/10.1007/BF01446409

H. Riesel, Meissel's formula, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkh"auser, Boston, MA (1994), p. 12 – 13. DOI: https://doi.org/10.1007/978-1-4612-0251-6

R. S'eroul, Meissel's formula, S,8.7.3 in Programming for Mathematicians, Springer-Verlag, Berlin (2000), p. 179 – 181.

A. V. Kulsha, Values of $pi(x)$ and $Delta(x)$ for various values of $x$, Retrieved 2008-09-14.

C.-J. de la Vall'ee Poussin, Recherches analytiques la th'eorie des nombres premiers, Ann. Soc. Sci. Bruxelles, 20, 183 – 256 (1896).

L. Locker-Ernst, Bemerkung "uber die Verteilung der Primzahlen, Elem. Math. (Basel), 14, 1 – 5 (1959).

L. Panaitopol, Several approximations of $pi(x)$, Math. Inequal. Appl., 2, 317 – 324 (1999). DOI: https://doi.org/10.7153/mia-02-29

J. Havil, Gamma: exploring Euler's constant, Princeton Univ. Press, Princeton, NJ (2003).

C. K. Caldwell, How many primes are there}?; https://primes.utm.edu/howmany.htmlbetter.

https://oeis.org/A006880