Ramanujan and Labos Primes, Their Generalizations, and Classifications of Primes

Vladimir Shevelev Department of Mathematics Ben-Gurion University of the Negev Beer-Sheva 84105 Israel

                      shevelev@bgu.ac.il

Abstract

We study the parallel properties of the Ramanujan primes and a symmetric counterpart, the Labos primes. Further, we study all primes with these properties (generalized Ramanujan and Labos primes) and construct two kinds of sieves for them. Finally, we give a further natural generalization of these constructions and pose some conjectures and open problems.

1 Introduction

The very well-known Bertrand postulate (1845) states that, for every x > 1, there exists a prime in the interval (x, 2x). This postulate quickly became a theorem when, in 1851, it was unexpectedly proved by Chebyshev (for a very elegant version of his proof, see Theorem 9.2 in [8]). In 1919, Ramanujan ([6]; [7, pp. 208–209]) gave a quite new and very simple proof of Bertrand’s postulate. Moreover, in his proof of a generalization of Bertrand’s, the following sequence of primes appeared ([11], A104272)

2, 11, 17, 29, 41, 47, 59, 67, 71, 97, 101, 107, 127, 149, 151, 167, …  (1)

Definition 1. For n ≥ 1, the n-th Ramanujan prime is the largest prime (R_{n}) for which π(R_{n}) − π(R_{n}/2) = n.

Let us show that, equivalently, R_{n} is the smallest positive integer g(n) with the property that, if x ≥ g(n), then π(x) − π(x/2) ≥ n.

Proof. Indeed, evidently, g(n) is prime. Note that, if for x > R_{n}, we have π(x) − π(x/2) ≤ n − 1, then, evidently, there exists a prime q > x for which π(q) − π(q/2) = n. This contradicts the maximality of R_{n}. Thus g(n) ≤ R_{n}. On the other hand, if g(n) < R_{n}, then for all x ∈ [g(n), R_{n}] we have π(x) − π(x/2) ≥ n. Let p ≥ g(n) be the nearest prime less than R_{n}. Then, for k ≥ 0, π(p) − π(p/2) = n + k. Since π(R_{n}) − π(R_{n}/2) = n, there exists exactly k + 1 primes ν_{1} < ⋯ < ν_{k+1} in interval [\frac{p+1}{2}, \frac{q−1}{2}]. For x = 2ν_{k+1} ∈ [p + 1, q − 1], we have

π(x) − π(x/2) = π(2ν_{k+1}) − π(ν_{k+1}) ≤ π(p) − π(p/2) − k − 1 = n − 1.

The contradiction shows that g(n) = R_{n}.

In [12], Sondow obtained some estimates for R_{n} and, in particular, proved that R_{n} > p_{2n} for every n > 1. Laishram [3] proved that R_{n} < p_{3n} (a short proof of this result follows from the more general Theorem 30 in this paper, see Remark 29). Further, Sondow proved that R_{n} ∼ p_{2n} as n → ∞. From this, denoting the counting function of the Ramanujan primes by π_{R}, we have R_{π_{R}(x)} ∼ 2π_{R}(x) ln π_{R}(x). Since R_{π_{R}(x)} ≤ x < R_{π_{R(x)}+1}, we have x ∼ p_{2π_{R}(x)} ∼ 2π_{R}(x) ln π_{R}(x) as x → ∞, and may conclude that

π_{R}(x) ∼ \frac{x}{2 ln x} ∼ \frac{π(x)}{2}.  (2)

Below we prove several other properties of the Ramanujan primes. Everywhere below p_{n} denotes the n-th prime. An important role is played by the following property.

Theorem 2. If p is an odd Ramanujan prime such that p_{m} < p/2 < p_{m+1}, then the interval (p, 2p_{m+1}) contains a prime.

In 2003, Labos introduced the following sequence of primes (cf. [11], sequence A080359). We call them Labos primes, denoting the n-th Labos prime by L_{n}.

Definition 3. For n ≥ 1, the n-th Labos prime is the smallest positive integer (L_{n}) for which π(L_{n}) − π(L_{n}/2) = n.

The first Labos primes are (see sequence A080359 in [11]):

2, 3, 13, 19, 31, 43, 53, 61, 71, 73, 101, 103, 109, 113, 139, 157, 173, …  (3)

Note that, since (see [11])

π(R_{n}) − π(R_{n}/2) = n,  (4)

by Definition 3 we have

L_{n} ≤ R_{n}.  (5)

Note also that, obviously, L_{n} ∼ p_{2n} as n → ∞.

For the Labos primes we prove a symmetric statement to Theorem 2.

Theorem 4. If p is an odd Labos prime, such that p_{m} < p/2 < p_{m+1}, then the interval (2p_{m}, p) contains a prime.

It is clear that Theorems 2-4 are connected with some left-right symmetry in the distribution of primes. Unfortunately, we do not lave a precise left-right symmetry since the inequalities of type R_{1} ≤ L_{1} ≤ R_{2} ≤ L_{2} ≤ ⋯ are broken from the very outset. In Theorem 17 we show that this deficiency could be removed by the consideration some additional primes with the close properties. Based on this theorem, we give a natural simple classification of the primes.

2 Proof of Theorems 2,4

We start with four conditions on an odd prime p.

Condition 5. Let p = p_{n}, with n > 1. All integers (p + 1)/2, (p + 3)/2, …, (p_{n+1} − 1)/2 are composite numbers.

Condition 6. Let p ≥ 5 and p_{m} < p/2 < p_{m+1}. The interval (p, 2p_{m+1}) contains a prime.

Condition 7. Let p = p_{n} with n ≥ 3. All integers (p − 1)/2, (p − 3)/2, …, (p_{n−1} + 1)/2 are composite numbers.

Condition 8. Let p_{m} < p/2 < p_{m+1}. The interval (2p_{m}, p) contains a prime.

Lemma 9. Conditions 5 and 6 are equivalent.

Proof. If Condition 5 is valid, and p_{m} < p/2 < p_{m+1}, then p_{m+1} > (p_{n+1} − 1)/2, i.e., p_{m+1} ≥ (p_{n+1} + 1)/2. Thus 2p_{m+1} > p_{n+1} > p_{n} = p, and Condition 6 is valid. Conversely, let Condition 6 be satisfied and p = p_{n}. Then from the condition p_{m+1} > p/2 > p_{m} we have 2p_{m} < p_{n} < p_{n+1} < 2p_{m+1}, or p_{m} < p_{n}/2 < p_{n+1}/2 < p_{m+1}. Since the interval (p_{m}, p_{m+1}) contains no primes, the interval (p_{n}/2, p_{n+1}/2) ⊂ (p_{m}, p_{m+1}) also contains no primes, and Condition 5 follows.

Analogously, we obtain the equivalence of the second pair of conditions.

Lemma 10. Conditions 7 and 8 are equivalent.

Now we are able to prove Theorems 2-4.

Proof. In view of Lemma 9, to prove of Theorem 1 it is sufficient to prove that, for Ramanujan primes, Condition 5 is satisfied. If Condition 5 is not satisfied, then suppose that p_{m} = R_{n} < p_{m+1} and k is the least positive integer such that q = (p_{m} + k)/2 is a prime not exceeding (p_{m+1} − 1)/2. Thus

R_{n} = p_{m} < 2q < p_{m+1} − 1.  (6)

From Definition 1 it follows that R_{n} − 1 is the maximum integer for which the equality

π(R_{n} − 1) − π((R_{n} − 1)/2) = n − 1  (7)

holds. However, according to (6), π(2q) = π(R_{n} − 1) + 1, and in view of the minimality of the prime q, in the interval ((R_{n} − 1)/2, q) there is no prime. Thus π(q) = π((R_{n} − 1)/2) + 1 and

π(2q) − π(q) = π(R_{n} − 1) − π((R_{n} − 1)/2) = n − 1.

Since, by (6), 2q > R_{n}, this contradicts the property of maximality of R_{n} in (7). Thus Theorem 2 follows. Theorem 4 is proved quite analogously, using Lemma 10.

3 Pseudo-Ramanujan primes, over-Ramanujan primes and their Pseudo-Labos and over-Labos analogues

Definition 11. Non-Ramanujan primes satisfying Condition 6 (or, equivalently, Condition 5) are pseudo-Ramanujan primes.

Denote the sequence of pseudo-Ramanujan primes by {R_{n}^{∗}} (see sequence (1.7)). The first pseudo-Ramanujan primes are (see sequence A164288 in [11]):

109, 137, 191, 197, 283, 521, 617, 683, 907, 991, 1033, 1117, 1319, …

Definition 12. An over-Ramanujan prime is a prime satisfying Condition 6 (or, equivalently, Condition 5).

Denote the sequence of over-Ramanujan primes by {R′_{n}} (see sequence A164368 in [11]). Note that all Ramanujan primes greater than 2 are also over-Ramanujan primes. It is easy to see that R′_{1} = 11. Furthermore, let us prove the following simple criterion.

Proposition 13. p_{n} ≥ 5 is an over-Ramanujan prime if and only if π(\frac{p_{n}}{2} ) = π(\frac{p_{n+1}}{2} ).

Proof. 1) Let π(\frac{p_{n}}{2} ) = π(\frac{p_{n+1}}{2} ). From this it follows that, if p_{k} < p_{n}/2 < p_{k+1}, then there are no primes between p_{n}/2 and p_{n+1}/2. Thus p_{n+1}/2 < p_{k+1} as well. Therefore, we have 2p_{k} < p_{n} < p_{n+1} < 2p_{k+1}, i.e., p_{n} is an over-Ramanujan prime. Conversely, if p_{n} is an over-Ramanujan prime, then 2p_{k} < p_{n} < p_{n+1} < 2p_{k+1}, and π(\frac{p_{n}}{2} ) = π(\frac{p_{n+1}}{2} ).

Definition 14. Non-Labos primes satisfying Condition 8 (or, equivalently, Condition 7) are pseudo-Labos primes.

Denote the sequence of pseudo-Labos primes by {L_{n}^{∗}}. The first pseudo-Labos primes are (A164294 in [11]):

131, 151, 229, 233, 311, 571, 643, 727, 941, 1013, 1051, 1153, 1373, …

Definition 15. An over-Labos prime is a prime satisfying Condition 8 (or, equivalently, Condition 7).

Denote the sequence of over-Labos primes by {L′_{n}} (see sequence A194598 in [11]). Note that all Labos primes grater than 3 are also over-Labos primes. It is easy to verify that L′_{1} = 13. Analogously to Proposition 13 we obtain the following criterion for over-Labos primes.

Proposition 16. p_{n} ≥ 5 is an over-Labos prime if and only if π(\frac{p_{n−1}}{2} ) = π(\frac{p_{n}}{2} ).

Theorem 17. Consider ALL primes {R′_{n}} and {L′_{n}} for which Theorems 2-4 are correspondingly true, then

R′_{1} ≤ L′_{1} ≤ R′_{2} ≤ L′_{2} ≤ ⋯  (8)

Proof. Note that intervals of the form (2p_{m}, 2p_{m+1}) containing not more than one prime, contain neither over-Ramanujan nor over-Labos primes. If an interval contains only two primes, then the first prime is an over-Ramanujan prime (R′), while the second one is an over-Labos prime (L′), and we see that R′ < L′; on the other hand, if it contains k primes, then beginning with the second one and up to the (k − 1)-st we have primes which are simultaneously over-Ramanujan and over-Labos primes. Thus, taking into account that the last prime is only an over-Labos prime we have for this interval

R′_{1} < L′_{1} = R′_{2} < L′_{2} = R′_{3} < ⋯ < L′_{k−1} = R′_{k−1} < L′_{k}.

The following interval containing at least two primes begins with an over-Ramanujan prime and the process repeats.

4 On difference R_{n} − L_{n}

Consider positive records of the difference R_{n} − L_{n}. They are (A182366 in [11])

8, 10, 24, 36, 60, 64, 84, 114, 124, 144, 202, 226, 228, …  (9)

at

n = 2, 4, 10, 14, 43, 95, 145, 167, 287, 415, 560, 635, 982, ….

However, we do not know a proof that lim sup_{n→∞}(R_{n} − L_{n}) = ∞. We prove a weaker statement.

Proposition 18. lim sup_{n→∞}(R_{n+1} − L_{n}) = ∞.

Proof. If there exists a constant C, such that R_{n+1} − L_{n} ≤ C, then for every n ≥ 1, there exist not more than C intervals (2, 4), (3, 6), … containing exactly n primes. Therefore, we have ≤ C of the first intervals containing one prime, ≤ 2C of the first intervals containing one or two primes,…, ≤ nC of the first intervals containing not more than n primes. Hence interval ((n + 1)C, 2(n + 1)C contains more than n primes. However, for large n it is impossible, since the number of primes in the interval (1, N) for N = 2(n + 1)C is equivalent to N/ ln N = o(n).

Now consider the following problem. Let us call a prime p compatible with another prime q, if the intervals (p/2, q/2) and (p, q], if q > p, (or intervals (q/2, p/2) and (q, p ], if q < p) contain the same number of primes. It is clear that, if p compatible with q, then q compatible with p. If p is compatible with no other prime, we call it a peculiar prime. It is required to describe the peculiar primes. We give a solution of this problem in the following form.

Proposition 19. A prime p is peculiar if and only if it is simultaneously Ramanujan and Labos prime.

Proof. Let p = L_{n} = R_{n} (a case L_{n−1} = R_{n}, evidently, is impossible). Then, by the Definitions 1-3, p is the smallest and the largest prime for which π(p) − π(p/2) = n. Thus the difference π(x)−π(x/2) = n, where x is prime, occurs only once. However, if there exists q ≠ p for which π(q) − π(q/2) = π(p) − π(p/2) = n, then the difference π(x) − π(x/2) = n with a prime x occurs at least twice. The contradiction shows that p is a peculiar prime. Conversely, if a prime p is peculiar, then, for any q ≠ p, we have π(p/2)−π(q/2) ≠ π(p)−π(q) and, consequently, π(q) − π(q/2) ≠ π(p) − π(p/2). Thus the difference π(x) − π(x/2) = π(p) − π(p/2), where x is prime, appears only once. This means that L_{n} = R_{n} = p, where n = π(p) − π(p/2).

Thus the peculiar primes are (A164554 in [11])

2, 71, 101, 181, 239, 241, 269, 349, 373, 409, 419, 433, 439, 491, …  (10)

Corollary 20. If there exist infinitely many peculiar primes, then lim inf_{n→∞}(R_{n} − L_{n}) = 0.

5 Prime gaps

Note that, as it follows from Lemma 9 and Theorem 2, if we consider a run of consecutive Ramanujan primes p = R_{l}, …, q = R_{k}, then the interval [\frac{1}{2}(p + 1), \frac{1}{2}(q + 1)] is free from primes. However, this note is far from a complete characterization of the prime gaps. For example, we have a run {2521, 2531} of consecutive Ramanujan primes which gives a “prime gap” [\frac{2521+1}{2}, \frac{2531+1}{2}] = [1261, 1266]. However, the real prime gap is much larger: (1259,1277). A better result can be obtained using over-Ramanujan primes. Indeed, the considered property of Ramanujan primes is valid for all over-Ramanujan primes, while runs of consecutive over-Ramanujan primes, generally speaking, are longer. For example, instead of the run {2521, 2531} of Ramanujan primes, we have the run {2521, 2531, 2539, 2543, 2549} of over-Ramanujan primes. This gives the interval [\frac{2521+1}{2}, \frac{2549+1}{2}] = [1261, 1275], which is free from primes and very close to the real gap. In general, since over-Ramanujan primes satisfy Condition 1, to every run of consecutive over-Ramanujan primes p = R′_{l}, …, q = R′_{k} there corresponds the interval [\frac{1}{2}(p + 1), \frac{1}{2}(q + 1)] which contains no primes. Note that the prime q′ following q gives an additional improvement of the lower estimate of size (l) of the considered prime gap. Indeed, we know that q′ is necessarily an over-Labos prime. Since the over-Labos primes satisfy Condition 3, all numbers \frac{q′−1}{2}, \frac{q′−3}{2}, …, \frac{q+1}{2} are composite. Hence l ≥ \frac{q′−p}{2}. For example, consider the run \{227, 229, 233, 239, 241\} of over-Ramanujan primes (all of which are Ramanujan). The following prime is q′ = 251. Thus, for the gap containing (227 + 1)/2 = 114 we have l ≥ \frac{251−227}{2} = 12 (the exact value of l here is 14).

6 The first sieve for the selection of the over-Ramanujan primes from all primes

Recall that Bertrand’s sequence {b(n)} is defined by b(1) = 2, and, for n ≥ 2, b(n) is the largest prime less than 2b(n − 1) (see A006992 in [11]):

2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 5003, …  (11)

Put

B_{0} = {b^{(0)}(n)} = {b(n)}.  (12)

Further we build sequences B_{1} = {b^{(1)}(n)}, B_{2} = {b^{(2)}(n)}, … according to the following inductive rule: if the sequences B_{0}, …, B_{k−1} have been defined already, let us consider the minimal prime p^{(k)} ∉ ⋃_{i=1}^{k−1} B_{i}. Then the sequence {b^{(k)}(n)} is defined by b^{(k)}(1) = p^{(k)}, and, for n ≥ 2, b^{(k)}(n) is the largest prime less than 2b^{(k)}(n − 1). Consequently:

B_{1} = {11, 19, 37, 73, …},  (13)

B_{2} = {17, 31, 61, 113, …},  (14)
B_{3} = {29, 53, 103, 199, …},  (15)

etc., such that, putting p^{(1)} = 11, we obtain the sequence

{p^{(k)}}_{k≥1} = {11, 17, 29, 41, 47, 59, 67, 71, 97, 101, 107, 109, 127, …}.  (16)

Sequence (16) coincides with sequence (1) of Ramanujan primes from the second term up to the 12-th term, but the 13-th term of this sequence is 109 which is the first term of the pseudo-Ramanujan primes.

Theorem 21. For n ≥ 1 :

p^{(n)} = R′_{n}.  (17)

Proof. The least omitted prime in (11) is p^{(1)} = 11 = R′_{1}; the least omitted prime in the union of (12) and (13) is p^{(2)} = 17 = R′_{2}. We use induction. Suppose we have already defined the primes

p^{(1)} = 11, p^{(2)}, …, p^{(n−1)} = R′_{n−1}.

Let q be the least prime which is omitted in the union ⋃_{i=1}^{n−1} B_{i}, such that q/2 is in the interval (p_{m}, p_{m+1}). According to our algorithm, q which is dropped should not be the largest prime in the interval (p_{m+1}, 2p_{m+1}). Then there are primes in the interval (q, 2p_{m+1}); let r be one of them. We have 2p_{m} < q < r < 2p_{m+1}. This means that q, in view of its minimality among the dropped primes which are more than R′_{n−1} = p^{(n−1)}, is the least over-Ramanujan prime larger than R′_{n−1} and the least prime of the form p^{(k)} larger than p^{(n−1)}. Therefore, q = p^{(n)} = R′_{n}.

Analogously, using sequence {c_{n}} defined by c(1) = 2, and, for n ≥ 2, c(n) is the smallest prime more than 2c(n − 1) (see A055496 in [11]), one can construct a sieve for over-Labos primes.

7 The second sieve for the selection of the over-Ramanujan primes from all primes

Theorem 17 on the precise symmetry between distributions of the sequences {R′_{n}} and {L′_{n}} allows us to construct the second sieve for over-Ramanujan primes.

Consider consecutive intervals of the form (2p_{n}, 2p_{n+1}), n = 1, 2, … Remove all the intervals containing less than two primes. For every remaining interval, we write the primes (in increasing order) except for the last one. Then all remaining primes are over-Ramanujan. Indeed, by the definition, an over-Ramanujan prime cannot be the last prime in every such interval. Let us demonstrate this sieve. For the primes 2,3,5,7,11,… consider the intervals

(4, 6), (6, 10), (10, 14), (14, 22), (22, 26), (26, 34), (34, 38), ….  (18)

Remove those intervals containing less than two primes. We have the following sequence of intervals:

(10, 14), (14, 22), (26, 34,), (38, 46), (46, 58), (58, 62), (62, 74), ….  (19)

Now we write all primes from these intervals, excluding the last primes. Then we obtain sequence (16). Analogously we obtain the second sieve for over-Labos primes. This sequence can be obtained in a parallel way, since, by definition, an over-Labos prime cannot be the first prime in any interval of the considered form. Therefore, here, for every remaining interval, we write the primes (in increasing order) except of the first one. Then all remaining primes are over-Labos (cf. sequence A164333 in [11]):

13, 19, 31, 43, 53, 61, 71, 73, 101, 103, 109, 113, 131, 139, 151, 157, ….  (20)

8 A classification of primes

In connection with the considered construction, let us consider the following classification of primes.

1) The first two primes 2,3 form a separate set of primes. 2) If p ≥ 11 is an over-Ramanujan but not an over-Labos prime, then, in connection with the second sieve, we call p a right prime (cf. A166307 in [11]):

11, 17, 29, 41, 47, 59, 67, 97, 107, 127, 137, 149, 167, 179, 197, 227, ….

3) If p ≥ 5 is an over-Labos but not an over-Ramanujan prime, then we call p a left prime The first terms of this sequence are (cf. A182365 in [11]):

13, 19, 31, 43, 53, 61, 73, 103, 113, 131, 139, 157, 173, 193, 199, 251, ….

4) If p is simultaneously an over-Ramanujan and an over-Labos prime, then we call it a central prime (sequence A166252 in [11]):

71, 101, 109, 151, 181, 191, 229, 233, 239, 241, 269, 283, 311, 349, ….

Note that, by Proposition 19, every peculiar prime more than 2 is central. Conversely is not true. The non-peculiar central primes are (cf. A182451 in [11]):

109, 151, 191, 229, 233, 283, 311, 571, 643, 683, 727, 941, 991, 1033, …

5) Finally, the rest of the primes are naturally called isolated primes (sequence A166251 in [11]):

5, 7, 23, 37, 79, 83, 89, 163, 211, 223, 257, 277, 317, 331, 337, 359, ….

Note that from the second sieve the following results follow.

Proposition 22. Let l_{n}, r_{n} denote the n-th left prime and the n-th right prime, respectively. Then l_{n} ∼ r_{n} as n → ∞.

Proof. The prime number theorem yields p_{n+1} − p_{n} = o(p_{n}). Since, by the construction, l_{n} and r_{n} belong to the same interval of the form (2p_{m(n)}, 2p_{m(n)+1}), we have r_{n} − l_{n} < 2(p_{m(n)+1} − p_{m(n)}) = o(l_{n}), and the statement follows.

Proposition 23. The sequence of lengths of the runs of the consecutive isolated primes is unbounded if and only if there exist arbitrary long sequences of consecutive primes p_{k}, p_{k+1}, …, p_{m}, such that every interval (\frac{p_{i}}{2} , \frac{p_{i+1}}{2} ), i = k, k + 1, …, m − 1, contains a prime.

Proof. Since the isolated primes more than 3 are the only primes which are neither over-Labos nor over-Ramanujan, then the statement follows from the condition and Propositions 13,16.

9 On density of over-Ramanujan and over-Labos primes

Let π_{R′}(x) be the counting function of over-Ramanujan numbers not exceeding x. It follows from (2), Theorem 2 and Definition 12 that, if lim_{n→∞} π_{R′}(x)/π(x) exists, then it is more than or equal to \frac{1}{2}. Berend [2] beautifully shown that this fact follows from Definition 12 only.

Proposition 24. ([2])

lim inf_{n→∞} π_{R′}(x)/π(x) ≥ \frac{1}{2}.

Proof. In the range from 7 up to n there are π(n) − 3 primes. Put

h = h(n) = π(n/2) − 2.

Then p_{h+2} ≤ n/2 and interval (p_{h+2}, n/2] is free from primes. Furthermore, consider intervals

(2p_{2}, 2p_{3}), (2p_{3}, 2p_{4}), …, (2p_{h+1}, 2p_{h+2}).

Our π(n) − 3 primes are somehow distributed in these h intervals. Suppose k = k(n) of these intervals contain at least one prime and h − k contain no primes. Then, for exactly k primes, there is no primes between them and the next 2p_{j}, and for the other π(n) − 3 − k there is. Therefore, since k(n) ≤ h(n) ≤ π(n/2) − 2, then, for ε > 0 and n > n_{ε}, we have:

\frac{π(n) − k(n)}{π(n)} ≥ \frac{π(n) − π(n/2)}{π(n)} ≥ \frac{1}{2} − ε.

Unfortunately, the analysis of the sieves obtained in section 7 seems much more difficult than the analysis of the sieve of Eratosthenes for primes. Nevertheless, some very simple probabilistic arguments lead to a very plausible conjecture about the density of over-Ramanujan and over-Labos primes. First of all, let us show that events R′ : “a prime is over-Ramanujan” and L′ : “a prime is over-Labos” are independent.

Proof. Indeed, denoting events r : “a prime is right”, l : “a prime is left” and Is : “a prime is isolated”, we have

P[R′|L′] = 1 − P[l] − P[Is]; P[R′|\overline{L′}] = 1 − P[r] − P[Is].  (21)

Hence, in view of P[l] = P[r] (cf. Proposition 5), we have

P[R′|L′] = P[R′|\overline{L′}].  (22)

Conjecture 25.

π_{R′}(x) ∼ (1 − e^{−1})π(x) = 0.63212 ⋯ π(x).  (23)

The following proof is heuristic.

Proof. Consider asymptotically \frac{π(n)}{2} intervals of the form (2p_{m}, 2p_{m+1}) covering all π(n) primes. It is well known ([5]) that, for large n, an interval between two random consecutive primes on the average has length ln p_{n}. Thus a random interval of the considered form has length 2 ln p_{n} and, according to the Cramér model, the number of primes in such a random interval has the binomial (2 ln p_{n}, \frac{1}{ln p_{n}}) distribution which, for large ln p_{n}, has a good approximation by a Poisson distribution with parameter λ = 2. Thus we accept that a random interval contains k primes with probability P[X = k] = \frac{2^{k}}{k!} e^{−2}, k = 0, 1, 2 …. Since P[X = 0] = e^{−2}, then the number of intervals containing at least one prime is about \frac{π(n)}{2}(1−e^{−2}). This number corresponds to our condition, since we consider only such intervals. Furthermore, since P[X = 1] = 2e^{−2}, then the probability that such an interval contains an only prime is 2e^{−2}/(1−e^{−2}) and, consequently, we have about \frac{π(n)}{2}(1−e^{−2})· \frac{2e^{−2}}{(1−e^{−2})} = π(n)e^{−2} intervals containing, by our terminology, isolated primes and this number coincides with the number of isolated primes. This means that the probability that a prime is isolated is e^{−2}. On the other hand, this probability equals P[\overline{R′} · \overline{L′}] = (P[\overline{R′}])^{2}. Therefore, P[\overline{R′}] = e^{−1} and P[R′] = 1 − e^{−1} which justifies the conjecture.

Greg Martin [4] did the corresponding calculations for the first million primes p, and found that approximately 61.2% of them have a prime in the interval (p, 2p_{n+1}). Since in this case ln p_{n} is small (less than 17), an error of about 2% is quite acceptable.

Remark 26. It could be done also the following simple explanation of appearance of the constant 1−1/e in Conjecture 25. Consider a random prime p. Let it be in interval (2p_{n}, 2p_{n+1}). We accept that p could be to the left or to the right from the midpoint p_{n} + p_{n+1} with the same frequency. Thus the mathematical expectation of the distance between p and 2p_{n+1} is the difference p_{n+1} − p_{n} which in average is ln n. Accepting for large n that the frequency of appearance a prime approximately is \frac{1}{ln n}, we see that it is natural to accept that the frequency of the appearance of a prime to the right from p in the considered interval is close to 1 − (1 − \frac{1}{ln n})^{ln n} which for large n is close to 1 − e^{−1}. Thus the frequency that a random p is over-Ramanujan is 1 − e^{−1}.

Note that, if Conjecture 25 is true, then, using (2), for the counting function π_{R^{∗}}(x) of pseudo-Ramanujan primes we have

π_{R^{∗}}(x) ∼ (\frac{1}{2} − \frac{1}{e})π(x) = 0.13212...π(x),  (24)

so that the proportion of Ramanujan primes among all over-Ramanujan primes is approximately 0.79099. Using Theorem 17, we note that, if Conjecture 25 is true, then, for the counting function π_{L′}(x) of over-Labos primes we have

π_{L′}(x) ∼ π_{R′}(x) ∼ (1 − e^{−1})π(x).  (25)

Therefore, if Conjecture 25 is true, then, for the counting functions π_{l}(x), π_{r}(x), π_{c}(x) and π_{is}(x) of the left, right, central and isolated primes, respectively, of our classes of primes, we have

π_{l}(x) ∼ π_{r}(x) ∼ (1 − e^{−1})e^{−1}π(x) = 0.2325 ⋯ π(x),  (26)
π_{c}(x) ∼ (1 − e^{−1})^{2}π(x) = 0.3995 ⋯ π(x),  (27)
π_{is}(x) ∼ e^{−2} = 0.1353 ⋯ π(x),  (28)

so that π_{r}(x) + π_{l}(x) + π_{c}(x) + π_{is}(x) = π(x).

10 A generalization

Let us consider a natural generalization of Ramanujan primes.

Definition 27. For a real v > 1, a v-Ramanujan prime is the largest prime (R_{v}(n)) for which π(R_{v}(n)) − π(R_{v}(n/v)) = n.

As in case v = 2, equivalently R_{v}(n) is the smallest integer with the property: if x ≥ R_{v}(n), then π(x) − π(x/v) ≥ n. Note that, evidently,

R_{v}(n) ∼ p_{((v/(v−1))n)}  (29)

as → ∞. Let π_{R}^{(v)}(x) be the counting function of v-Ramanujan primes. Then (cf. (2))

π_{R}^{(v)}(x) ∼ (1 − 1/v)π(x).  (30)

Put

κ(v) = \begin{cases}0, & if v is not the ratio between two primes; \\ r, & if v = \frac{r}{q} where r and q are primes. \end{cases}  (31)

The following theorem is proved in the same way as Theorem 1.

Theorem 28. Let v > 1 be a given real number. If p > max(2v, κ(v)) is v-Ramanujan prime such that p_{m} < p/v < p_{m+1}, then the interval (p, ⌈vp_{m+1}⌉ + ε) contains a prime.

Remark 29. The condition p > max(2v, κ(v)) allows us to avoid the cases p = 2v and p = vq with a prime q, when the condition p_{n} < p/v < p_{n+1} is impossible.

Let us find an upper bound on the n-th v-Ramanujan prime.

Theorem 30. If n ≥ \frac{1}{k} max(6k, e^{v}, v^{(0.79677 \frac{k−1}{k} v−1)^{−1}}), then, for v ≥ 1.25507\frac{k}{k−1}, we have

R_{v}(n) ≤ p_{kn}.  (32)

Proof. It is sufficient to show that π(\frac{p_{kn}}{v}) ≤ (k −1)n. Indeed, then we have π(p_{kn})−π(\frac{p_{kn}}{v}) ≥ kn − (k − 1)n = n. We use the following known results ([1], [9]-[10]):

p_{n} < n ln n + n ln ln n, n ≥ 6;  (33)

p_{n} > n ln n;  (34)
π(x) < 1.25506\frac{x}{ln x}, x > 1.  (35)

Note that \frac{p_{kn}}{v} > \frac{kn}{v} > \frac{kn}{e^{v}}. Hence, by the condition, \frac{p_{kn}}{v} > 1. By (33)-(35),

π(\frac{p_{kn}}{v}) < 1.25506\frac{p_{kn}}{v ln(\frac{p_{kn}}{v})} < 1.25506\frac{kn}{v} · \frac{ln(kn) + ln(ln(kn))}{ln(\frac{kn ln(kn)}{v})}

= 1.25506\frac{kn}{v}(1 + \frac{ln v}{ln(\frac{kn ln(kn)}{v})}).

Taking into account that, by the condition, ln(kn) > v, we have

π(\frac{p_{kn}}{v}) < 1.25506\frac{kn}{v}(1 + \frac{ln v}{ln(kn)}).

Finally, note that, by the condition, \frac{ln v}{ln(kn)} ≤ 0.7968\frac{k−1}{k}v − 1. Therefore,

π(\frac{p_{kn}}{v}) < 1.25506 · 0.79677(k − 1)n < (k − 1)n.

Corollary 31.

R_{3}(n) < p_{2n}, n ≥ 1.  (36)
R_{1.8}(n) < p_{4n}, n ≥ 1.  (37)

Proof. By Theorem 30, for v = 3, k = 2, we get the required inequality for n ≥ 279. Using a computer verification for n < 279, we obtain (36). In case v = 1.8, k = 4, we get the required inequality for n ≥ 2370. Using a computer verification for n < 2370, we obtain (10.9).

The first 1.8-Ramanujan primes are

2, 11, 17, 37, 43, 59, 61, 79, 97, 101, 103, 137, 163, 167, 191, 211, ….  (38)

Remark 32. In case v = 2, k = 3, by Theorem 6, we find that R_{n} = R_{2}(n) < p_{3n}, for n ≥ 22398. Computer verification for n < 22398 leads to Laishram’s result [3].

Definition 33. A prime p > max(2v, κ(v)) is a v-over-Ramanujan prime if, as soon as p_{m} < p/v < p_{m+1}, the interval (p, vp_{m+1}) contains a prime.

Definition 34. A v-over-Ramanujan not v-Ramanujan prime is a v-pseudo-Ramanujan prime.

Now v-Labos primes, v-over-Labos primes and v-pseudo-Labos primes are introduced quite symmetrically (see Section 3). In particular, the following statements are valid.

Theorem 35. Let v > 1 be a given real number. If p > max(2v, κ(v)) is v-Labos prime, such that p_{m} < p/v < p_{m+1}, then the interval (⌊vp_{m}⌋ − ε, p) contains a prime.

Theorem 36. For the sequences {R′_{v}(n)} and {L′_{v}(n)} of v-over-Ramanujan and v-over-Labos primes, we have

R′_{v}(1) ≤ L′_{v}(1) ≤ R′_{v}(2) ≤ L′_{v}(2) ≤ ⋯  (39)

A generalization of the first sieve for v-over-Ramanujan primes, v ≥ 2, is based on the Bertrand-like sequence {b_{v}(n)}, defined by b_{v}(1) = 2, and, for n ≥ 2, as the largest prime less than ⌈vb_{v}(n − 1)⌉ + ε. A generalization of the second sieve for v-over-Ramanujan primes is based on the sequence of intervals

(⌊2v⌋ − ε, ⌈3v⌉ + ε), (⌊3v⌋ − ε, ⌈5v⌉ + ε), (⌊5v⌋ − ε, ⌈7v⌉ + ε), …  (40)

with the removing intervals containing less than two primes (cf. (19)). For every remaining interval, we write the primes (in increasing order) except for the last one. Then all remaining primes are v-over-Ramanujan. For example, if v = 3, we obtain the following sequence of 3-over-Ramanujan primes (sequence A164952 in [11]):

2, 3, 11, 17, 23, 29, 41, 43, 59, 61, 71, 73, 79, 97, 101, 103, 107, ….  (41)

Furthermore, one can obtain a v-classification of primes, including v-left, v-right, v-central and v-isolated primes (see Section 8). In particular, if l_{v}(n), r_{v}(n) denote the n-th v-left prime and the n-th v-right prime, respectively, then l_{n} ∼ r_{n} as n → ∞. Consider now a natural generalization of Proposition 19 with the similar proof.

Proposition 37. Let π_{R′_{v}}(x) be the counting function of v-over-Ramanujan numbers not exceeding x. Then

lim inf_{n→∞} π_{R′_{v}}(x)/π(x) ≥ 1 − \frac{1}{v}.

A generalization of Conjecture 25 (with a similar heuristic proof) is the following.

Conjecture 38.

π_{R′_{v}}(x) ∼ (1 − e^{−(v−1)})π(x).  (42)

Note that, if Conjecture 38 is true, then, using (30), for the counting function π_{R_{v}^{∗}}(x) of v-pseudo-Ramanujan primes we have

π_{R_{v}^{∗}}(x) ∼ (\frac{1}{v} − e^{−(v−1)})π(x),  (43)

so that the proportion of v-pseudo-Ramanujan primes among all v-over-Ramanujan primes is (\frac{1}{v} − e^{−(v−1)})/(1 − e^{−(v−1)}). This proportion tends to 1 as v → 1, and decreases to 0 as v → ∞. Using Theorem 36, we note that, if Conjecture 38 is true, then, for the counting function π_{L′_{v}}(x) of v-over-Labos primes, we have

π_{L′_{v}}(x) ∼ π_{R′_{v}}(x) ∼ (1 − e^{−(v−1)})π(x).  (44)

Furthermore, if Conjecture 38 is true, then, for the counting functions π_{l_{v}}(x), π_{r_{v}}(x), π_{c_{v}}(x) and π_{is_{v}}(x) of the v-left, v-right, v-central and v-isolated primes, respectively, of the considered classes of primes, we have

π_{l_{v}}(x) ∼ π_{r_{v}}(x) ∼ (1 − e^{−(v−1)})e^{−(v−1)}π(x),  (45)

π_{c_{v}}(x) ∼ (1 − e^{−(v−1)})^{2}π(x),  (46)
π_{is_{v}}(x) ∼ e^{−2(v−1)}π(x),  (47)

so that π_{r_{v}}(x) + π_{l_{v}}(x) + π_{c_{v}}(x) + π_{is_{v}}(x) = π(x).

11 Other open problems

Conjecture 39. (cf. P roposition 23). There exist arbitrary long sequences of consecutive primes p_{k}, p_{k+1}, …, p_{m}, such that every interval (\frac{p_{i}}{2} , \frac{p_{i+1}}{2} ), i = k, k + 1, …, m − 1, contains a prime.

Conjecture 40. (cf. P roposition 18). lim sup_{n→∞}(R_{n} − L_{n}) = ∞.

Conjecture 41. (cf. P roposition 19). There exist infinitely many peculiar primes.

Problem 42. For v > 1, to estimate the smallest pseudo-v-Ramanujan prime, the smallest v-central prime and the smallest v-isolated prime.

12 Acknowledgments

The author is grateful to Daniel Berend (Ben-Gurion University, Israel) and Greg Martin (University of British Columbia, Canada) for important private communications [2], [4] and very useful discussions. He is also grateful to Peter J. C. Moses (UK) for improvement the text and to the anonymous referee for very important remarks.

References

[1] E. Bach, and J. Shallit, Algorithmic Number Theory, MIT Press, 233 (1996). ISBN 0-262-02405-5.

[2] D. Berend, Private communication.

[3] S. Laishram, On a conjecture on Ramanujan primes, Int. J. Number Theory 6 (2010), 1869–1873.

[4] G. Martin, Private communication.

[5] K. Prachar, Primzahlverteilung, Springer-Verlag, 1957.

[6] S. Ramanujan, A proof of Bertrand’s postulate, J. Indian Math. Soc. 11 (1919), 181– 182.

[7] S. Ramanujan, in G. H. Hardy, S. Aiyar, P. Venkatesvara, and B. M. Wilson, eds., Collected Papers of Srinivasa Ramanujan, Amer. Math. Soc., 2000.

[8] D. Redmond, Number Theory, An Introduction, Marcel Dekker, 1996.

[9] J. B. Rosser, The n-th prime is greater than n log n, Proc. Lond. Math. Soc. 45 (1938), 21–44.

[10] J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–97.

[11] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[12] J. Sondow, Ramanujan primes and Bertrand’s postulate, Amer. Math. Monthly, 116 (2009), 630–635.

2010 Mathematics Subject Classification: Primary 11N05. Keywords: Bertrand postulate, Ramanujan prime, Labos prime, over-Ramanujan prime, over-Labos prime, prime gaps.

(Concerned with sequences \underline{A006992}, \underline{A055496}, \underline{A060715}, \underline{A080359}, \underline{A104272}, \underline{A164288}, \underline{A164294}, \underline{A164333}, \underline{A164368}, \underline{A164554}, \underline{A164952}, \underline{A166251}, \underline{A166252}, \underline{A166307}, \underline{A182365}, \underline{A182366}, \underline{A182391}, \underline{A182392}, \underline{A182423}, \underline{A182426}, \underline{A182451}, \underline{A193507}, \underline{A193761}, \underline{A193880}, \underline{A194184}, \underline{A194186}, \underline{A194217}, and \underline{A194598}.)

Received August 4 2011; revised versions received September 7 2011; May 8 2012; May 16 2012. Published in Journal of Integer Sequences, May 29 2012.

Return to Journal of Integer Sequences home page.