New fast methods to compute the number of primes less than a given value
DOI:
https://doi.org/10.37863/umzh.v74i9.6193Keywords:
Locker – Ernst’sAbstract
UDC 519.688
The paper describes new fast algorithms for evaluating π(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 ≈15 of the actual value for 3≤x≤10000. The approximation verifies the inequality, h(x)≤Li(x) and, therefore, is better than 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 ≈25 of the actual value for x≤50000 (to compare Li(x) lies within ≈40 for the same range) and asymptotically g(x)∼xlnxexp(1lnx−1).
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.
