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

Анотація

УДК 519.688

Нові швидкі методи обчислення кількості простих чисел, менших за деяку задану величину

Описано нові швидкі алгоритми для обчислення $\pi(x)$ на основі інтегралів гармонічних та геометричних середніх, які можна використовувати на будь-якому кишеньковому калькуляторі. Зокрема, формула $h(x), $ що отримана на основі середнього гармонічного, знаходиться в межах $\approx 15$ від фактичного значення для $3\leq x\leq 10000$. Це наближення задовольняє нерівність $h(x)\leq {\rm Li}(x)$ і тому є кращим за ${\rm Li}(x)$ для малих $x$. Показано, що $h(x)$ та їхні розширення є точнішими за інші відомі наближення, такі як Локера–Ернста або Лежандра, і для великих $x$. Крім того, отримано ще одну функцію $g(x)$ на основі середньогеометричного інтеграла, яка використовує $h(x)$ як вхідну величину і дозволяє суттєво покращити такий метод. Показано, що $g(x)$ знаходиться в межах $\approx 25$ від фактичного значення для $x\leq 50000$ (для порівняння, ${\rm Li}(x)$ знаходиться в межах $\approx 40$ в тому ж самому діапазоні) і має таку асимптотику: $g(x)\sim \dfrac{x}{\ln x}\exp\left(\dfrac{1}{\ln x-1}\right)$.

Посилання

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