New fast methods to compute the number of primes less than a given value
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 act...
Gespeichert in:
| Datum: | 2022 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2022
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/6193 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860512289775419392 |
|---|---|
| author | Teruel, G. R. P. Teruel, G. R. P. |
| author_facet | Teruel, G. R. P. Teruel, G. R. P. |
| author_sort | Teruel, G. R. P. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2023-01-07T13:45:33Z |
| description |
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).$ |
| doi_str_mv | 10.37863/umzh.v74i9.6193 |
| first_indexed | 2026-03-24T03:26:26Z |
| format | Article |
| fulltext |
DOI: 10.37863/umzh.v74i9.6193
UDC 519.688
G. R. P. Teruel1 (Dep. Math., IES Carrús, Elche-Alicante, Spain)
NEW FAST METHODS TO COMPUTE THE NUMBER OF PRIMES
LESS THAN A GIVEN VALUE
НОВI ШВИДКI МЕТОДИ ОБЧИСЛЕННЯ КIЛЬКОСТI ПРОСТИХ ЧИСЕЛ,
МЕНШИХ ЗА ДЕЯКУ ЗАДАНУ ВЕЛИЧИНУ
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 \mathrm{L}\mathrm{i}(x) and, therefore, is better than
\mathrm{L}\mathrm{i}(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 \mathrm{L}\mathrm{i}(x) lies within \approx 40 for the same range) and
asymptotically g(x) \sim x
\mathrm{l}\mathrm{n}x
\mathrm{e}\mathrm{x}\mathrm{p}
\biggl(
1
\mathrm{l}\mathrm{n}x - 1
\biggr)
.
Описано новi швидкi алгоритми для обчислення \pi (x) на основi iнтегралiв гармонiчних та геометричних середнiх,
якi можна використовувати на будь-якому кишеньковому калькуляторi. Зокрема, формула h(x), що отримана на
основi середнього гармонiчного, знаходиться в межах \approx 15 вiд фактичного значення для 3 \leq x \leq 10000. Це
наближення задовольняє нерiвнiсть h(x) \leq \mathrm{L}\mathrm{i}(x) i тому є кращим за \mathrm{L}\mathrm{i}(x) для малих x. Показано, що h(x) та їхнi
розширення є точнiшими за iншi вiдомi наближення, такi як Локера – Ернста або Лежандра, i для великих x. Крiм
того, отримано ще одну функцiю g(x) на основi середньогеометричного iнтеграла, яка використовує h(x) як вхiдну
величину i дозволяє суттєво покращити такий метод. Показано, що g(x) знаходиться в межах \approx 25 вiд фактичного
значення для x \leq 50000 (для порiвняння, \mathrm{L}\mathrm{i}(x) знаходиться в межах \approx 40 в тому ж самому дiапазонi) i має таку
асимптотику: g(x) \sim x
\mathrm{l}\mathrm{n}x
\mathrm{e}\mathrm{x}\mathrm{p}
\biggl(
1
\mathrm{l}\mathrm{n}x - 1
\biggr)
.
1. Introduction. As is widely known, the prime counting function \pi (x) computes the number of
primes less than or equal to a given number x. Since there are no primes \leq 1, then \pi (1) = 0,
there are two primes \leq 3, so \pi (3) = 2. And so on. In the last two centuries, there have been
different attempts to approximate \pi (x) by a smooth and easy computable function. Already in
1808, Legendre [1] noticed that \pi (x) \approx x
\mathrm{l}\mathrm{n}x - B
, where he originally proposed B = 1.08366 . . . .
Some years before, Gauss[2] had already observed that the logarithmic integral, \mathrm{l}\mathrm{i}(x) =
\int x
0
dt
\mathrm{l}\mathrm{n} t
approximates \pi (x) quite accurately, but for small x it overestimates the number of primes less or
equal to x. To solve this problem, in 1859 Riemann [3] introduced
R(x) =
\infty \sum
n=1
\mu (n)
n
\mathrm{l}\mathrm{i}(x1/n) = 1 +
\infty \sum
k=1
(\mathrm{l}\mathrm{n}x)k
k!k\zeta (k + 1)
,
where \mu (n) is the Mobius function [4, 5], and the last form above for R(x) is the Gram series
which is the better way to calculate this function. Riemann’s approximation turns out to be 10 times
better than \mathrm{l}\mathrm{i}(x) for x \leq 109 but has been proven to be worse infinitely often by Littlewood [6, 7].
Other approximations to \pi (x) are Lehmer’s formula, Mapes’ method, or Meissel’s formula [8 – 12].
1 e-mail:gines.landau@gmail.com.
c\bigcirc G. R. P. TERUEL, 2022
1264 ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
NEW FAST METHODS TO COMPUTE THE NUMBER OF PRIMES LESS THAN A GIVEN VALUE 1265
Currently, the best known approximation to \pi (x) is due to A. V. Kulsha [14]:
\pi (x) \approx R(x) - 1
\mathrm{l}\mathrm{n}x
+
1
\pi
\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{a}\mathrm{n}
\pi
\mathrm{l}\mathrm{n}x
.
In this work, we present and derive several other approximations, the first one is denoted as h(x)
and is based on the harmonic integral (continuous harmonic mean) of the function 1/ \mathrm{l}\mathrm{n}x. We show
that it provides an accurate approximation of \pi (x), specially for small x. Asymptotically, it behaves
as x/(\mathrm{l}\mathrm{n}x - 1) which turns out to be superior than other famous approximations such as Legendre’s
or Locker – Ernst’s formula. In the following, we refer to the first method derived here as “harmonic
approximation”, and it should not be confused with the approximate method due to Locker – Ernst
[16 – 18]: \pi (x) \approx x
hx
, where hx = Hx - 3/2, with H(x) the harmonic number. The other algorithm
that we present in this letter to evaluate \pi (x) is a function denoted as g(x), based on the geometric
continuous mean. The function g(x) depends on h(x), it is also a fast an easy computable method
and provides a close approximation to \pi (x) improving the results of h(x).
This paper is organized as follows. In Section 2, we begin by rewriting the logarithmic integral
in a form that makes explicit their dependence on the average value from calculus. Then we explore
what happens if we replace in this formula the standard average value by other means, such as
the harmonic mean or the geometric mean, which unlike the standard average, can be analytically
computed. The approximation that arises by the first possibility is studied in detail, including some
natural generalizations. In the last part of the work, the second possibility that arises by replacing the
standard average by the geometric mean integral in the definition of \mathrm{L}\mathrm{i}(x) is considered. This is the
subject of Section 3.
We should mention that the new methods presented in this letter are not meant to replace the
current approximation methods of \pi (x); they merely add to the toolbox of available techniques and
approximations. However, they have the advantage of being smooth and easy computable functions
that may be used on any pocket calculator.
2. The harmonic mean integral approximation. Let us begin by writing the standard definition
of the offset logarithmic integral or Eulerian logarithmic integral
\mathrm{L}\mathrm{i}(x) =
x\int
2
dt
\mathrm{l}\mathrm{n} t
.
As is well-known, the offset logarithmic integral appears in estimates of the number of prime numbers
less than a given value. In particular, the prime number theorem states that \pi (x) \sim \mathrm{L}\mathrm{i}(x) for large
x, where \pi (x) is again the number of primes smaller than or equal to x. For small x, it has been
always found that \mathrm{L}\mathrm{i}(x) > \pi (x), namely, \mathrm{L}\mathrm{i}(x) overestimates the number of primes less or equal
than x.
For our purposes in this letter, it is more convenient to rewrite \mathrm{L}\mathrm{i}(x) in the following form:
\mathrm{L}\mathrm{i}(x) =
x\int
2
dt
\mathrm{l}\mathrm{n} t
= (x - 2)
\biggl\langle
1
\mathrm{l}\mathrm{n} t
\biggr\rangle x
2
, (1)
where we have defined
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
1266 G. R. P. TERUEL
\biggl\langle
1
\mathrm{l}\mathrm{n} t
\biggr\rangle x
2
=
1
x - 2
x\int
2
dt
\mathrm{l}\mathrm{n} t
,
as the standard average of the function 1/ \mathrm{l}\mathrm{n} t among 2 and x. Let us assume now that f(t) \not = 0 for
all t in [a, b]. The harmonic integral of f(t) can be defined by
\scrH b
a(f) =
b - a\int b
a
1
f(t)
dt
.
Then the continuous harmonic mean of f(t) = 1/ \mathrm{l}\mathrm{n} t among 2 and x is equal to the reciprocal of
the average of the reciprocal of 1/ \mathrm{l}\mathrm{n} t, that is,
\scrH x
2
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
=
1
\langle \mathrm{l}\mathrm{n} t\rangle x2
= (x - 2)
\left( x\int
2
\mathrm{l}\mathrm{n} t dt
\right) - 1
. (2)
Contrary to the case of the standard average of 1/ \mathrm{l}\mathrm{n} t which does not admit an elementary primitive,
the harmonic integral admits a completely elementary primitive, which can be found integrating by
parts, and is given by
\scrH x
2
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
=
x - 2
x(\mathrm{l}\mathrm{n}x - 1) - 2(\mathrm{l}\mathrm{n} 2 - 1)
.
Theorem 2.1.
\mathrm{L}\mathrm{i}(x) \geq (x - 2)2
x(\mathrm{l}\mathrm{n}x - 1) - 2(\mathrm{l}\mathrm{n} 2 - 1)
. (3)
Proof. We begin by noting that \biggl\langle
1
\mathrm{l}\mathrm{n} t
\biggr\rangle x
2
\geq \scrH x
2
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
.
This is nothing but the generalization to the continuum of the condition AM \geq HM of the discrete
case, i.e., the arithmetic mean AM is always at least as large as the harmonic mean HM. This
implies the inequality
1
x - 2
x\int
2
dt
\mathrm{l}\mathrm{n} t
\geq x - 2\int x
2
\mathrm{l}\mathrm{n} t dt
.
Reordering the last inequality\left( x\int
2
dt
\mathrm{l}\mathrm{n} t
\right) \left( x\int
2
\mathrm{l}\mathrm{n} t dt
\right) \geq (x - 2)2.
The second integral of the left-hand side can be computed analytically
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
NEW FAST METHODS TO COMPUTE THE NUMBER OF PRIMES LESS THAN A GIVEN VALUE 1267
Fig. 1. Representation of \pi (n) (blue) and several of their approximations, \mathrm{L}\mathrm{i}(n)
(black), L(n) (green), and the harmonic approximation h(n) (red).\left( x\int
2
dt
\mathrm{l}\mathrm{n} t
\right) \Bigl[
t \mathrm{l}\mathrm{n} t - t
\Bigr] x
2
\geq (x - 2)2.
Finally we obtain
x\int
2
dt
\mathrm{l}\mathrm{n} t
\geq (x - 2)2
x(\mathrm{l}\mathrm{n}x - 1) - 2(\mathrm{l}\mathrm{n} 2 - 1)
.
Define the function of the right-hand side of Eq. (3)
h(x) =
(x - 2)2
x(\mathrm{l}\mathrm{n}x - 1) - 2(\mathrm{l}\mathrm{n} 2 - 1)
. (4)
Since \mathrm{L}\mathrm{i}(x) > \pi (x) for small x, and given that \mathrm{L}\mathrm{i}(x) \geq h(x), then it seems natural to wonder if
h(x) could be a good approximation of \pi (x). In order to test h(x) as a possible approximation of
\pi (x), we have presented here some plots. In Fig. 1, we have plotted the prime-counting function
\pi (x) together with \mathrm{L}\mathrm{i}(x), Legendre’s L(x) and h(x) until x \sim 1200. Fig. 2 presents a graph of the
compared behavior of the harmonic integral approximation to Locker – Ernst’s until x \sim 10000.
Before concluding this section, let us mention that there are several possible generalizations of
h(x) that are quite natural. The first case are the functions of the type
h(x) =
(x - 2)2
x(\mathrm{l}\mathrm{n}x - 1) +A
with A an arbitrary constant. On the other hand, we have the family of functions
pp(x) := (x - p)\scrH x
p(f) = (x - p)2
\left( x\int
p
\mathrm{l}\mathrm{n} t dt
\right) - 1
=
(x - p)2
x(\mathrm{l}\mathrm{n}x - 1) - p(\mathrm{l}\mathrm{n} p - 1)
,
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
1268 G. R. P. TERUEL
Fig. 2. Comparison among \pi (n) - n
hn
(blue) and \pi (n) - h(n) (black), where n/hn is Locker – Ernst’s approximation
and h(n) the harmonic mean integral approximation. \pi (n) - h(n) has more zeros than \pi (n) - n
hn
. Moreover,
h(n) is within \approx 15 of the actual value for 3 \leq x \leq 10000, while Locker – Ernst’s is within \approx 25 for the
same range.
where p is any prime that satisfies the condition p < x. All these functions present a discontinuity at
x = p. The harmonic integral approximation h(x) corresponds to the case p = 2, i.e., h(x) = p2(x).
Regarding the case p = 3, we have
p3(x) := (x - 3)\scrH x
3(f) = (x - 3)2
\left( x\int
3
\mathrm{l}\mathrm{n} t dt
\right) - 1
=
(x - 3)2
x(\mathrm{l}\mathrm{n}x - 1) - 0.29583686601
.
On the other hand, the limit x \rightarrow p of pp(x) can be computed with the aid of the L’Hopital –
Bernoulli rule
\mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow p
(x - p)2
x(\mathrm{l}\mathrm{n}x - 1) - p(\mathrm{l}\mathrm{n} p - 1)
= \mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow p
2(x - p)
\mathrm{l}\mathrm{n}x
= 0.
It can be shown that \pi (x) \sim p3(x), i.e., this function is also a good approximation of \pi (x), in fact the
relative error is even lower that that provided by h(x) for small x. We show now that asymptotically,
pp(x) \sim x/(\mathrm{l}\mathrm{n}x - 1), which is a better asymptotic behavior than Legendre’s function (it is well-
known that 1 turns out to be a better constant for large x than 1.08366 . . .).
Lemma 2.1. For x >> p,
pp(x) \sim
x
\mathrm{l}\mathrm{n}x - 1
.
Proof. When x >> p, the factor p(\mathrm{l}\mathrm{n} p - 1) can be neglected with respect to x(\mathrm{l}\mathrm{n}x - 1)
(x - p)2
x(\mathrm{l}\mathrm{n}x - 1) - p(\mathrm{l}\mathrm{n} p - 1)
\sim x
\mathrm{l}\mathrm{n}x - 1
.
Theorem 2.2.
\mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)
pp(x)
= 1.
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
NEW FAST METHODS TO COMPUTE THE NUMBER OF PRIMES LESS THAN A GIVEN VALUE 1269
200 400 600 800 1000
x
-2
-1
1
2
p3(x) - π(x)
200 400 600 800 1000
x
-2
-1
1
2
R(x) - π(x)
Fig. 3. Representation of p3(x) - \pi (x) and R(x) - \pi (x), where R(x) is the Riemann function.
Proof. First, we use the result of the previous lemma and the factorization
x
\mathrm{l}\mathrm{n}x - 1
=
x
\mathrm{l}\mathrm{n}x
\biggl(
1 - 1
\mathrm{l}\mathrm{n}x
\biggr) - 1
.
Now, we can employ the binomial theorem to expand
\biggl(
1 - 1
\mathrm{l}\mathrm{n}x
\biggr) - 1
:
\mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)
pp(x)
\sim \mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)\biggl[
x
\mathrm{l}\mathrm{n}x
\biggl(
1 +
1
\mathrm{l}\mathrm{n}x
+
1
(\mathrm{l}\mathrm{n}x)2
+ . . .
\biggr) \biggr] \sim \mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)\Bigl[ x
\mathrm{l}\mathrm{n}x
\Bigr] .
Finally, the prime number theorem (PNT) states that
\mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)\Bigl[ x
\mathrm{l}\mathrm{n}x
\Bigr] = 1.
In Fig. 3, we have represented the quantities p3(x) - \pi (x) and R(x) - \pi (x), where R(x) is the
Riemann function. Although R(x) - \pi (x) has more zeros for 10 \leq x \leq 1000, p3(x) is not much
worse, and it is faster and easier to use on any scientific calculator. Notice also that p2 > pp for
p > 2, namely, in a representation, the graph of all of these functions would be located below p2. In
the next section, we will see that it is possible to significantly improve the quality of the harmonic
approximation h(x) and their family pp(x).
3. Improving \bfith (\bfitx ) by the geometric mean integral approximation. In Section 2 we showed
that, by virtue of Eq. (1), the offset logarithmic integral \mathrm{L}\mathrm{i}(x) can be rewritten as (x - 2)
\biggl\langle
1
\mathrm{l}\mathrm{n} t
\biggr\rangle x
2
this form of expressing \mathrm{L}\mathrm{i}(x) makes explicit their dependence on the standard average. It is therefore
natural to wonder what happens if one replaces in the latter formula the standard average by other
possible means. Having studied the case of the harmonic mean in the previous section, in this last
part of the work we investigate the replacement of the standard average by the geometric mean in
the definition of \mathrm{L}\mathrm{i}(x). Indeed, if f(t) > 0 for all t in [a, b] and f is integrable on [a, b], then the
geometric mean (product integral) of f(t) exists, and its definition is given by
\scrG b
a(f) = \mathrm{e}\mathrm{x}\mathrm{p}
\left(
\int b
a
\mathrm{l}\mathrm{n} f(t) dt
b - a
\right) . (5)
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
1270 G. R. P. TERUEL
Notice that \scrG b
a(f) satisfies the inequality
\langle f\rangle ba \geq \scrG b
a(f) \geq \scrH b
a(f). (6)
This is again the continuous analog of the inequality AM \geq GM \geq HM of the discrete case. A
consequence is that
\mathrm{L}\mathrm{i}(x) =
x\int
2
dt
\mathrm{l}\mathrm{n} t
= (x - 2)
\biggl\langle
1
\mathrm{l}\mathrm{n} t
\biggr\rangle x
2
\geq (x - 2)\scrG x
2
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
, (7)
where \scrG x
2
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
is given by
\scrG x
2
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
= \mathrm{e}\mathrm{x}\mathrm{p}
\left(
\int x
2
\mathrm{l}\mathrm{n}
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
dt
x - 2
\right) .
Integrating by parts, the integral that appears in the argument of the exponential can be expressed
in terms of a function, a constant, and the logarithmic integral
x\int
2
\mathrm{l}\mathrm{n}
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
dt = x \mathrm{l}\mathrm{n}
\biggl(
1
\mathrm{l}\mathrm{n}x
\biggr)
- 2 \mathrm{l}\mathrm{n}
\biggl(
1
\mathrm{l}\mathrm{n} 2
\biggr)
+
x\int
2
dt
\mathrm{l}\mathrm{n} t
.
By virtue of this relation, we have found that \scrG x
2
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
depends on \mathrm{L}\mathrm{i}(x) as
\scrG x
2
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
= \mathrm{e}\mathrm{x}\mathrm{p}
\left( x \mathrm{l}\mathrm{n}
\biggl(
1
\mathrm{l}\mathrm{n}x
\biggr)
- 2 \mathrm{l}\mathrm{n}
\biggl(
1
\mathrm{l}\mathrm{n} 2
\biggr)
+ \mathrm{L}\mathrm{i}(x)
x - 2
\right) .
Then, combining all these results, the inequality of Eq. (7) turns out
\mathrm{L}\mathrm{i}(x) \geq (x - 2) \mathrm{e}\mathrm{x}\mathrm{p}
\biggl(
2 \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n} 2) - x \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n}x) + \mathrm{L}\mathrm{i}(x)
x - 2
\biggr)
. (8)
Notice that, since \mathrm{L}\mathrm{i}(x) \geq h(x), where h(x) is the harmonic mean integral approximation given
by Eq. (4), it is also true that
\mathrm{L}\mathrm{i}(x) \geq (x - 2) \mathrm{e}\mathrm{x}\mathrm{p}
\biggl(
2 \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n} 2) - x \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n}x) + h(x)
x - 2
\biggr)
. (9)
Therefore, the functions of the right-hand sides of Eqs. (8), (9) are both smooth functions with a
closed and compact form that can be studied as two other possible algorithms for evaluating \pi (x).
Define the couple of functions g\mathrm{L}\mathrm{i}(x) and gh(x), respectively, as
g\mathrm{L}\mathrm{i}(x) = (x - 2) \mathrm{e}\mathrm{x}\mathrm{p}
\biggl(
2 \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n} 2) - x \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n}x) + \mathrm{L}\mathrm{i}(x)
x - 2
\biggr)
, (10)
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
NEW FAST METHODS TO COMPUTE THE NUMBER OF PRIMES LESS THAN A GIVEN VALUE 1271
10000 20000 30000 40000 50000
x
-25
-20
-15
-10
-5
5
g(x) - π(x)
10000 20000 30000 40000 50000
x
-50
-40
-30
-20
-10
h(x) - π(x)
10000 20000 30000 40000 50000
x
10
20
30
40
li(x) - π(x)
10000 20000 30000 40000 50000
x
-80
-60
-40
-20
x
hx
- π(x)
Fig. 4. Representation of the differences to \pi (x) for 2 < x \leq 50000, of four different approximations, where
g(x), h(x) and x/hx represent the geometric mean, the harmonic mean, and Locker – Ernst’s approximations,
respectively.
gh(x) = (x - 2) \mathrm{e}\mathrm{x}\mathrm{p}
\biggl(
2 \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n} 2) - x \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n}x) + h(x)
x - 2
\biggr)
. (11)
Given that \mathrm{L}\mathrm{i}(x) \geq h(x), it automatically follows an inequality among gh(x), g\mathrm{L}\mathrm{i}(x),
g\mathrm{L}\mathrm{i}(x) \geq gh(x).
The pair of functions g\mathrm{L}\mathrm{i}(x), gh(x) employ the couple \mathrm{L}\mathrm{i}(x), h(x) as inputs, but improve their
results for a wide range of values. For instance, in order to test the quality of gh(x) as approximation
of \pi (x), in Fig. 4 we have plotted the differences gh(x) - \pi (x), h(x) - \pi (x), \mathrm{L}\mathrm{i}(x) - \pi (x) and
x/hx - \pi (x), for 2 < x \leq 50000. The superiority of gh(x) over the rest of approximations for such
domain turns out to be manifest.
Before concluding, let us investigate the asymptotic behavior of gh(x). For this purpose, it is
convenient to factorize gh(x) in the form
gh(x) = (x - 2) \mathrm{e}\mathrm{x}\mathrm{p}
\biggl(
2 \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n} 2) - x \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n}x)
x - 2
\biggr)
\mathrm{e}\mathrm{x}\mathrm{p}
\biggl(
\scrH x
2
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr) \biggr)
, (12)
where we have used Eq. (2). Now we provide a proof that gh(x) approaches \pi (x) for x \rightarrow \infty .
Theorem 3.1. Let \pi (x), gh(x) be the prime counting function and the function defined by
Eq. (11), respectively. Then
\mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)
gh(x)
= 1.
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
1272 G. R. P. TERUEL
Proof. With the aid of the factorization given by Eq. (12), it is easy to see that asymptotically,
gh(x) \sim x e
- x \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n} x)
x e
1
\mathrm{l}\mathrm{n} x - 1 =
x
\mathrm{l}\mathrm{n}x
e
1
\mathrm{l}\mathrm{n} x - 1 .
Then, given that for sufficiently large x, e
1
\mathrm{l}\mathrm{n} x - 1 \sim 1, we have
\mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)
gh(x)
\sim \mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)\Bigl[ x
\mathrm{l}\mathrm{n}x
e
1
\mathrm{l}\mathrm{n} x - 1
\Bigr] \sim \mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)\Bigl[ x
\mathrm{l}\mathrm{n}x
\Bigr] .
Finally, according to the PNT
\mathrm{l}\mathrm{i}\mathrm{m}
x\rightarrow \infty
\pi (x)\Bigl[ x
\mathrm{l}\mathrm{n}x
\Bigr] = 1.
On the other hand, by virtue of Eq. (6) and the results obtained in this section, it is clear that,
\mathrm{L}\mathrm{i}(x) \geq g\mathrm{L}\mathrm{i}(x) \geq gh(x) \geq h(x).
Let us briefly mention that a natural generalization of g\mathrm{L}\mathrm{i}(x) can also be written down using (5)
(x - p)\scrG x
p
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
= (x - p) \mathrm{e}\mathrm{x}\mathrm{p}
\left(
\int x
p
\mathrm{l}\mathrm{n}
\biggl(
1
\mathrm{l}\mathrm{n} t
\biggr)
dt
x - p
\right) =
= (x - p) \mathrm{e}\mathrm{x}\mathrm{p}
\left( p \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n} p) - x \mathrm{l}\mathrm{n}(\mathrm{l}\mathrm{n}x) +
\int x
p
dt
\mathrm{l}\mathrm{n} t
x - p
\right) ,
where p is an arbitrary prime subjected to the constraint x > p. For p = 2, we naturally recover the
case of the function g\mathrm{L}\mathrm{i}(x).
It can be shown that gh(x) \sim x
\mathrm{l}\mathrm{n}x
e
1
\mathrm{l}\mathrm{n} x - 1 , is a more accurate approximation than h(x), Le-
gendre’s L(x) and any function that asymptotically converges to f(x) = x/(\mathrm{l}\mathrm{n}x - 1). The same
also applies to g\mathrm{L}\mathrm{i}(x), which is even better, although to compute g\mathrm{L}\mathrm{i}(x) we need to know first the
value of \mathrm{L}\mathrm{i}(x), and then insert it into Eq. (10).
As a quick example, for x = 1027 (the current record is x = 1029) we have gh(10
27) =
= 1.63500982221 \times 1025, L(1027) = 1.63703262434 \times 1025, h(1027) = 1.63479370652 \times 1025,
being the actual value \pi (1027) = 1.6352460426841680446427399 \times 1025. The prediction of gh(x)
is not as good as that provided by \mathrm{L}\mathrm{i}(x), but it gives a surprisingly accurate result for such an
algebraically simple function. In fact, the function gh(x) does have some advantages over \mathrm{L}\mathrm{i}(x);
unlike \mathrm{L}\mathrm{i}(x), gh(x) can be expressed in closed form, which renders it fairly easy to evaluate gh(x)
on any scientific calculator. Moreover, since the arithmetic mean is always at least as large as the
geometric mean, we always have that \mathrm{L}\mathrm{i}(x) \geq gh(x); it is well-known that \mathrm{L}\mathrm{i}(x) overestimates
\pi (x) for small x, therefore gh(x) can serve as a much more accurate approximation to \pi (x) for
such values of x.
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
NEW FAST METHODS TO COMPUTE THE NUMBER OF PRIMES LESS THAN A GIVEN VALUE 1273
4. Summary and conclusions. In this paper, we have added some new fast methods to the
toolbox of available approximations of \pi (x), which are very easy to use on any pocket calculator. A
natural question arises: which method is better for approximating \pi (x)? It depends on the domain
of values of interest. Our results show that gh(x), for instance, is a much better formula than \mathrm{L}\mathrm{i}(x)
until x \sim 106, and is much faster to use. However, if one requires high asymptotic precision, then
\mathrm{L}\mathrm{i}(x) is a better formula, although gh(x), h(x) are also good, and superior than other fast methods
based on simple functions like Legendre’s or Locker – Ernst’s.
De la Vallée-Poussin proved that \mathrm{L}\mathrm{i}(x) is better approximation of \pi (x) than any rational function
of x and \mathrm{l}\mathrm{n}x for large x. h(x) is a rational function of x and \mathrm{l}\mathrm{n}x, and therefore it will be inferior
than \mathrm{L}\mathrm{i}(x) in the long run, but gh(x) is not rational (contains an exponential). Unfortunately, we
do not know if gh(x) can improve the results of \mathrm{L}\mathrm{i}(x) for sufficiently large x, because there is no
record of the number of primes beyond x = 1029, the current available record announced in 2022 by
D. Baugh and K. Walisch.
References
1. A. M. Legendre, Essai sur la théorie des nombres, Courcier, Paris (1808).
2. C. F. Gauss, Werke, vol. II. Königliche Gesellschaft der Wissenschaften zu Göttingen, 444 – 447 (1863).
3. G. F. B. Riemann, Über die Anzahl der Primzahlen unter einer gegebenen Grösse, Monatsber. Königl. Preuss. Akad.
Wiss. Berlin, 671 – 680 (1859).
4. Hardy, G. H. Ramanujan, Twelve lectures on subjects suggested by his life and work, 3rd ed., Chelsea, New York
(1999).
5. 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).
6. E. W. Weisstein, Gram series; http://mathworld.wolfram.com/GramSeries.html.
7. A. E. Ingham, Ch. 5 in the distribution of prime numbers, Cambridge Univ. Press, New York (1990).
8. H. Riesel, Lehmer’s formula, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkhäuser, Boston,
MA (1994), p. 13 – 14.
9. D. C. Mapes, Fast method for computing the number of primes less than a given limit, Math. Comput., 17, 179 – 185
(1963).
10. H. Riesel, Mapes’ method, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkhäuser, Boston,
MA (1994), p. 23.
11. E. D. F. Meissel, Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde naturlicher Zahlen
vorkommen, Math. Ann., 25, 251 – 257 (1885).
12. H. Riesel, Meissel’s formula, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkhäuser, Boston,
MA (1994), p. 12 – 13.
13. R. Séroul, Meissel’s formula, § 8.7.3 in Programming for Mathematicians, Springer-Verlag, Berlin (2000), p. 179 – 181.
14. A. V. Kulsha, Values of \pi (x) and \Delta (x) for various values of x, Retrieved 2008-09-14.
15. C.-J. de la Vallée Poussin, Recherches analytiques la théorie des nombres premiers, Ann. Soc. Sci. Bruxelles, 20,
183 – 256 (1896).
16. L. Locker-Ernst, Bemerkung über die Verteilung der Primzahlen, Elem. Math. (Basel), 14, 1 – 5 (1959).
17. L. Panaitopol, Several approximations of \pi (x), Math. Inequal. Appl., 2, 317 – 324 (1999).
18. J. Havil, Gamma: exploring Euler’s constant, Princeton Univ. Press, Princeton, NJ (2003).
19. C. K. Caldwell, How many primes are there?; https://primes.utm.edu/howmany.htmlbetter.
20. https://oeis.org/A006880
Received 28.06.20
ISSN 1027-3190. Укр. мат. журн., 2022, т. 74, № 9
|
| id | umjimathkievua-article-6193 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-24T03:26:26Z |
| publishDate | 2022 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/d7/173b08b822e5e89e1e9d265ff5e6d8d7.pdf |
| spelling | umjimathkievua-article-61932023-01-07T13:45:33Z New fast methods to compute the number of primes less than a given value New fast methods to compute the number of primes less than a given value Teruel, G. R. P. Teruel, G. R. P. Locker – Ernst’s 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.&nbsp;&nbsp;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.$&nbsp;The approximation verifies the inequality, $h(x)\leq {\rm Li}(x)$ and, therefore, is better than ${\rm Li}(x)$ for small $x.$&nbsp;&nbsp;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.$&nbsp;&nbsp;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.&nbsp;&nbsp;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).$ УДК 519.688 Нові швидкі методи обчислення кількості простих чисел, менших за деяку задану величину Описано нові швидкі алгоритми для обчислення $\pi(x)$ на основі інтегралів гармонічних та геометричних середніх, які можна використовувати на будь-якому кишеньковому калькуляторі.&nbsp;&nbsp;Зокрема, формула $h(x), $ що отримана на основі середнього гармонічного, знаходиться в межах $\approx 15$ від фактичного значення для $3\leq x\leq 10000$.&nbsp;&nbsp;Це наближення задовольняє нерівність $h(x)\leq {\rm Li}(x)$ і тому є кращим за ${\rm Li}(x)$ для малих $x$.&nbsp;&nbsp;Показано, що $h(x)$ та їхні розширення є точнішими за інші відомі наближення, такі як Локера–Ернста або Лежандра, і для великих $x$.&nbsp;&nbsp;Крім того, отримано ще одну функцію $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)$. &nbsp; Institute of Mathematics, NAS of Ukraine 2022-11-08 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/6193 10.37863/umzh.v74i9.6193 Ukrains’kyi Matematychnyi Zhurnal; Vol. 74 No. 9 (2022); 1264 - 1273 Український математичний журнал; Том 74 № 9 (2022); 1264 - 1273 1027-3190 en https://umj.imath.kiev.ua/index.php/umj/article/view/6193/9302 Copyright (c) 2022 Ginés Teruel |
| spellingShingle | Teruel, G. R. P. Teruel, G. R. P. New fast methods to compute the number of primes less than a given value |
| title | New fast methods to compute the number of primes less than a given value |
| title_alt | New fast methods to compute the number of primes less than a given value |
| title_full | New fast methods to compute the number of primes less than a given value |
| title_fullStr | New fast methods to compute the number of primes less than a given value |
| title_full_unstemmed | New fast methods to compute the number of primes less than a given value |
| title_short | New fast methods to compute the number of primes less than a given value |
| title_sort | new fast methods to compute the number of primes less than a given value |
| topic_facet | Locker – Ernst’s |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/6193 |
| work_keys_str_mv | AT teruelgrp newfastmethodstocomputethenumberofprimeslessthanagivenvalue AT teruelgrp newfastmethodstocomputethenumberofprimeslessthanagivenvalue |