On Intervals (kn, (k + 1)n) Containing a Prime for All n > 1

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

                            shevelev@bgu.ac.il

Charles R. Greathouse IV 3214 Whitethorn Road Cleveland Heights, OH 44118 USA

                        charles.greathouse@case.edu

Peter J. C. Moses Moparmatic Co. 1154 Evesham Road Astwood Bank, Redditch, Worcestershire B96 6DT England

                         mows@mopar.freeserve.co.uk

Abstract We study values of k for which the interval (kn, (k + 1)n) contains a prime for every n > 1. We prove that the list of such integers k includes 1, 2, 3, 5, 9, 14 and no others, at least for k ≤ 100, 000, 000. Moreover, for every known k in this list, we give a good upper bound for the smallest N_{k}(m), such that if n ≥ N_{k}(m), then the interval (kn, (k + 1)n) contains at least m primes.

1 Introduction and main results

In 1850, Chebyshev proved the famous Bertrand postulate (1845) that every interval [n, 2n] contains a prime (for a very elegant version of his proof, see Redmond [10, Theorem 9.2]).

Other nice proofs were given by Ramanujan in 1919 [8] and Erdős in 1932 (reproduced in Erdős and Surányi [4, p. 171–173]). In 2006, El Bachraoui [1] proved that every interval [2n, 3n] contains a prime, while Loo [6] proved the same statement for every interval [3n, 4n]. Moreover, Loo found a lower bound for the number of primes in the interval [3n, 4n]. In 1952, Nagura [7] proved that there is always a prime between n and \frac{6}{5}n for n ≥ 25. From his result, it follows that the interval [5n, 6n] always contains a prime. In this paper we prove the following:

Theorem 1. The list of integers k for which every interval (kn, (k + 1)n), n > 1, contains a prime includes k = 1, 2, 3, 5, 9, 14 and no others, at least for k ≤ 100, 000, 000.

To prove Theorem 1, in Section 3 we introduce and study the so-called k-Chebyshev primes. We give them, and the generalized Ramanujan primes, the best estimates of the form p_{tn}, where p_{n} is the n-th prime. Note that the core of the proof of Theorem 1 is Proposition 9, which in turn depends on Proposition 8.

In passing, for every k = 1, 2, 3, 5, 9, 14, we give an algorithm for finding the smallest N_{k}(m), such that for n ≥ N_{k}(m), the interval (kn, (k + 1)n) contains at least m primes.

Proof of Theorem 1 is completed in Section 7 by computer research of sequence \underline{A218831} in [13].

2 Case k = 1

Ramanujan [8] not only proved Bertrand’s postulate, but also provided the smallest integers \{R(m)\}, such that if x ≥ R(m), then the interval (\frac{x}{2}, x] contains at least m primes, or equivalently, π(x) − π(x/2) ≥ m. It is easy to see that it is sufficient to consider integer x, and it is also evident that every term of {R(m)} is prime. The numbers {R(m)} are called Ramanujan primes [14]. It is sequence \underline{A104272} in [13]:

2, 11, 17, 29, 41, 47, 59, 67, 71, 97, …  (1)

Since π(x) − π(x/2) is not a monotonic function, to calculate the Ramanujan numbers one should have an effective upper bound for R(m). Ramanujan [8] showed that

π(x) − π(x/2) > \frac{1}{ln x} (\frac{x}{6} − 3\sqrt{x}) , x > 300.  (2)

In particular, for x ≥ 324, the left-hand side is positive and thus ≥ 1. Using direct descent, he found that π(x) − π(x/2) ≥ 1 from x ≥ 2. Thus R(1) = 2, which proves the Bertrand postulate. Further, e.g., for x ≥ 400, the left-hand side of (2) is more than 1 and thus ≥ 2. Again, using direct descent, he found that π(x) − π(x/2) ≥ 2 from x ≥ 11. Thus R(2) = 11, etc. Sondow [14] found that R(m) < 4m ln(4m) and conjectured that

R(m) < p_{3m}  (3)

which was proved by Laishram [5]. Since, for n ≥ 2, p_{n} ≤ en ln n (cf. [3, Section 4]), then (3) yields R(m) ≤ 3em ln(3m), m ≥ 1. Let x = 2n. If 2n ≥ R(m), then π(2n) − π(n) ≥ m. Thus the interval (n, 2n) contains at least m primes, if

n ≥ ⌈\frac{R(m) + 1}{2}⌉ = \begin{cases}2, & if m = 1; \\ \frac{R(m)+1}{2}, & if m ≥ 2. \end{cases}

Let N_{1}(m) denote the smallest number such that if n ≥ N_{1}(m), then the interval (n, 2n) contains at least m primes. It is clear that N_{1}(1) = R(1) = 2. If m ≥ 2, formally the condition x = 2n ≥ 2N_{1}(m) is not stronger than the condition x ≥ R(m), since the latter holds for x even and odd. Therefore, for m ≥ 2, we have N_{1}(m) ≤ \frac{R(m)+1}{2}. Let us show that, in fact, we have the equality

Proposition 2. For m ≥ 2,

N_{1}(m) = \frac{R(m) + 1}{2}.  (4)

Proof. Note that the interval (\frac{R(m)−1}{2}, R(m) − 1) cannot contain more than m − 1 primes.

Indeed, it is an interval of type (\frac{x}{2}, x) for integer x and the following such interval is

(\frac{R(m)}{2}, R(m)). By definition, R(m) is the smallest number such that if x ≥ R(m), then

\{(\frac{x}{2}, x)\} contains ≥ m primes. Therefore, the supposition that the interval (\frac{R(m)−1}{2}, R(m) − 1) contains ≥ m primes contradicts the minimality of R(m). Since the following interval of type (y, 2y) with integer y ≥ \frac{R(m)−1}{2} is (\frac{R(m)+1}{2}, R(m) + 1), Eq. (4) then follows.

So the sequence \{N_{1}(m)\}, by (1), is \underline{A084140} in [13]:

2, 6, 9, 15, 21, 24, 30, 34, 36, 49, …  (5)

3 Generalized Ramanujan numbers

Our research is based on a generalization of Ramanujan’s method. With this aim, we define generalized Ramanujan numbers (cf. [12, Section 10], and the earlier comment in \underline{A164952} in [13]).

Definition 3. Let v > 1 be a real number. A v-Ramanujan number, R_{v}(m), is the smallest integer such that if x ≥ R_{v}(m), then π(x) − π(x/v) ≥ m.

It is known [10] that all v-Ramanujan numbers are primes. In particular, R_{2}(m) = R(m), m = 1, 2, … are the proper Ramanujan primes.

Definition 4. For a real number v > 1 the v-Chebyshev number, C_{v}(m), is the smallest integer such that if x ≥ C_{v}(m), then ϑ(x) − ϑ(x/v) ≥ m ln x, where ϑ(x) = ∑_{p≤x} ln p is the Chebyshev function.

Since \frac{ϑ(x)−ϑ(x/v)}{ln x} can increase by 1 only when x is prime, then all v-Chebyshev numbers are primes.

Proposition 5. We have

R_{v}(m) ≤ C_{v}(m).  (6)

Proof. Let x ≥ C_{v}(m). Then we have

m ≤ \frac{ϑ(x) − ϑ(x/v)}{ln x} = ∑_{\frac{x}{v} <p≤x} \frac{ln p}{ln x} ≤ ∑_{\frac{x}{v} <p≤x} 1 = π(x) − π(x/v).  (7)

Thus, if x ≥ C_{v}(m), then always π(x) − π(x/v) ≥ m. By Definition 3, this means that R_{v}(m) ≤ C_{v}(m).

Now we give upper bounds for C_{v}(m) and R_{v}(m).

Proposition 6. Let x = x_{v}(m) ≥ 2 be any number for which

\frac{x}{ln x} (1 − \frac{1300}{ln^{4} x}) ≥ \frac{vm}{v − 1}.  (8)

Then

R_{v}(m) ≤ C_{v}(m) ≤ x_{v}(m).  (9)

Proof. We use the following inequality of Dusart [3] (see his Theorem 5.2):

|ϑ(x) − x| ≤ \frac{1300x}{ln^{4} x}, x ≥ 2.

Thus we have

ϑ(x) − ϑ(x/v) ≥ x (1 − \frac{1}{v} − 1300 (\frac{1}{ln^{4} x} − \frac{1}{v ln^{4} \frac{x}{v}} ))

≥ x (1 − \frac{1}{v}) (1 − \frac{1300}{ln^{4} x}) .

If now

x (1 − \frac{1}{v}) (1 − \frac{1300}{ln^{4} x}) ≥ m ln x, x ≥ x_{v}(m),

then

ϑ(x) − ϑ(x/v) ≥ m ln x, x ≥ x_{v}(m)

and, by Definition 4, C_{v}(m) ≤ x_{v}(m). So, according to (6), we conclude that R_{v}(m) ≤ x_{v}(m).

Proposition 6 gives the terms of sequences {C_{v}(m)}, {R_{v}(m)} for every v > 1, m ≥ 1. In particular, if k = 1 we find {C_{2}(m)}:

11, 17, 29, 41, 47, 59, 67, 71, 97, 101, 107, 127, 149, 151, 167, 179, 223,
229, 233, 239, 241, 263, 269, 281, 307, 311, 347, 349, 367, 373, 401, 409,  (10)
419, 431, 433, 443, …

This sequence requires a separate comment. We observe that up to C_{2}(100) = 1489 only two terms of this sequence (C_{2}(17) = 223 and C_{2}(36) = 443) are not Ramanujan numbers, and the sequence is missing only the following 6 Ramanujan numbers: 181,227,439,491,1283,1301 and no others up to the 104-th Ramanujan number 1489. The latter observation shows how much the ratio \frac{ϑ(x)}{ln x} exactly approximates π(x). Similar observations are also valid for the following sequences for v = \frac{k+1}{k} (and undoubtedly require an additional special study):

for k = 2, {C_{v}(m)},

13, 37, 41, 67, 73, 97, 127, 137, 173, 179, 181, 211, 229, 239, …;  (11)

for k = 2, {R_{v}(m)},

2, 13, 37, 41, 67, 73, 97, 127, 137, 173, 179, 181, 211, 229, 239, …;  (12)

for k = 3, {C_{v}(m)},

29, 59, 67, 101, 149, 157, 163, 191, 227, 269, 271, 307, 379, …;  (13)

for k = 3, {R_{v}(m)},

11, 29, 59, 67, 101, 149, 157, 163, 191, 227, 269, 271, 307, 379, …;  (14)

for k = 5, {C_{v}(m)},

59, 137, 139, 149, 223, 241, 347, 353, 383, 389, 563, 569, 593, …;  (15)

for k = 5, {R_{v}(m)},

29, 59, 137, 139, 149, 223, 241, 347, 353, 383, 389, 563, 569, 593, …;  (16)

for k = 9, {C_{v}(m)},

223, 227, 269, 349, 359, 569, 587, 593, 739, 809, 857, 991, 1009, …;  (17)

for k = 9, {R_{v}(m)},

127, 223, 227, 269, 349, 359, 569, 587, 593, 739, 809, 857, 991, 1009, …;  (18)

for k = 14, {C_{v}(m)},

307, 347, 563, 569, 733, 821, 1427, 1429, 1433, 1439, 1447, 1481, …;  (19)

for k = 14, {R_{v}(m)},

127, 307, 347, 563, 569, 733, 1423, 1427, 1429, 1433, 1439, 1447, …  (20)

Remark 7. In fact, Dusart [3, Theorem 5.2] gives several inequalities of the form

|ϑ(x) − x| ≤ \frac{ax}{ln^{b} x}, x ≥ x_{0}(a, b)

From a computing point of view, the values a = 1300, b = 4 from Dusart’s theorem are not always the best. The analysis for x ≥ 25 shows that the condition

x (1 − \frac{1}{v}) (1 − \frac{ax}{ln^{b} x}) ≥ m ln x

is satisfied for the smallest x_{v}(m) = x_{v}(m; a, b), using the following values of a and b from Dusart’s theorem:

a = 3.965, b = 2 for x in range (25, 7 · 10^{7}]; a = 1300, b = 4 for x in range (7 · 10^{7}, 10^{9}]; a = 0.001, b = 1 for x in range (10^{9}, 8 · 10^{9}]; a = 0.78, b = 3 for x in range (8 · 10^{9}, 7 · 10^{33}]; a = 1300, b = 4 for x > 7 · 10^{33},

which minimizes the amount of calculations for v-Chebyshev primes.

4 Bounds of type (3)

Proposition 8. We have

C_{2}(m − 1) ≤ p_{3m}, m ≥ 2;  (21)
R_{\frac{3}{2}} (m) ≤ p_{4m}, m ≥ 1; C_{\frac{3}{2}} (m − 1) ≤ p_{4m}, m ≥ 2;  (22)
R_{\frac{4}{3}} (m) ≤ p_{6m}, m ≥ 1; C_{\frac{4}{3}} (m − 1) ≤ p_{6m}, m ≥ 2;  (23)
R_{\frac{6}{5}} (m) ≤ p_{11m}, m ≥ 1; C_{\frac{6}{5}} (m − 1) ≤ p_{11m}, m ≥ 2;  (24)
R_{\frac{10}{9}} (m) ≤ p_{31m}, m ≥ 1; C_{\frac{10}{9}} (m − 1) ≤ p_{31m}, m ≥ 2;  (25)
R_{\frac{15}{14}} (m) ≤ p_{32m}, m ≥ 1; C_{\frac{15}{14}} (m − 1) ≤ p_{32m}, m ≥ 2.  (26)

Proof. Firstly, let us find some values of m_{0} = m_{0}(k), such that, at least, for m ≥ m_{0} all formulas (21)–(26) hold. According to (8) and (9), it is sufficient to show that, for m ≥ m_{0}, we can take p_{tm}, where t = 3, 4, 6, 11, 31, 32 for formulas (21)-(26) respectively, in the capacity of x_{v}(m). As we noted in Remark 7, in order to find possibly smaller values of m_{0}, we use the bound

\frac{x}{ln x} (1 − \frac{3.965}{ln^{2} x}) ≥ \frac{vm}{v − 1}  (27)

instead of (8). In order to get x = p_{mt} satisfying this inequality, note that [11]

p_{n} ≥ n ln n.

Therefore, it is sufficient to consider p_{mt} satisfying the inequality

ln p_{tm} ≤ (1 − \frac{1}{v}) t ln(tm) (1 − \frac{3.965}{ln^{2}(tm ln(tm))}) .

On the other hand, for n ≥ 2, (see [3, (4.2)])

ln p_{n} ≤ ln n + ln ln n + 1.

Thus, it is sufficient to choose m so large that the following inequality holds

ln(tm) + ln ln(tm) + 1 ≤ (1 − \frac{1}{v}) t ln(tm) (1 − \frac{3.965}{ln^{2}(tm ln(tm))}) ,

or, since 1 − \frac{1}{v} = \frac{1}{k+1}, that

\frac{ln(tm) + ln ln(tm) + 1}{ln(tm)(1 − \frac{3.965}{ln^{2}(tm ln(tm))})} ≤ \frac{t}{k + 1}.  (28)

For example, let k = 1, t = 3. We can choose m_{0} = 350. Then the left-hand side of (28) equals 1.4976 ⋯ < 1.5. This means that at least for m ≥ 350, the estimate (21) is valid. Using a computer for m ≤ 350, we obtain (21) for m ≥ 2. Other bounds are proved in the same way.

5 Bounds and formulas for N_{k}(m)

Proposition 9.

N_{k}(1) = 2, k = 2, 3, 5, 9, 14.  (29)

For m ≥ 2, k ≥ 1,

N_{k}(m) ≤ ⌈\frac{R_{\frac{k+1}{k}} (m)}{k + 1}⌉;  (30)

besides, if R_{\frac{k+1}{k}} (m) ≡ 1 (mod k + 1), then

N_{k}(m) = ⌈\frac{R_{\frac{k+1}{k}} (m)}{k + 1}⌉ = \frac{R_{\frac{k+1}{k}} (m) + k}{k + 1}  (31)

and, if R_{\frac{k+1}{k}} (m) ≡ 2 (mod k + 1), then

N_{k}(m) = ⌈\frac{R_{\frac{k+1}{k}} (m)}{k + 1}⌉ = \frac{R_{\frac{k+1}{k}} (m) + k − 1}{k + 1}.  (32)

Proof. If m ≥ 2, formally, the condition x = (k+1)n ≥ (k+1)N_{k}(m) is not stronger than the condition x ≥ R_{\frac{k+1}{k}} (m), since the first one is valid only for x multiple of k +1. Therefore, for m ≥ 2, (30) holds. It allows calculation of terms in the sequence {N_{k}(m)} for k > 1, m ≥ 2. Since N_{k}(1) ≤ N_{k}(2), then, having N_{k}(2), we can also prove (29) using direct calculation. Now let R_{\frac{k+1}{k}} (m) ≡ 1 (mod k + 1). Note, that for y = (R_{\frac{k+1}{k}} (m) − 1)/(k + 1) the interval

(ky, (k + 1)y) = (\frac{k}{k + 1} (R_{\frac{k+1}{k}} (m) − 1) , R_{\frac{k+1}{k}} (m) − 1)  (33)

cannot contain more than m−1 primes. Indeed, it is an interval of type (\frac{k}{k+1}x, x) for integer x, and the following such interval is

(\frac{k}{k + 1} (R_{\frac{k+1}{k}} (m)) , R_{\frac{k+1}{k}} (m)) .

By definition, R_{\frac{k+1}{k}} (m) is the smallest number such that if x ≥ R_{\frac{k+1}{k}} (m), then \{(\frac{k}{k+1}x, x)\} contains ≥ m primes. Therefore, the supposition that the interval (33) contains ≥ m primes contradicts the minimality of R_{\frac{k+1}{k}} (m). Since the following interval of type (ky, (k + 1)y) with integer y ≥ \frac{k}{k+1}(R_{\frac{k+1}{k}} (m) − 1) is

(\frac{k}{k + 1}(R_{\frac{k+1}{k}} (m) + k), R_{\frac{k+1}{k}} (m) + k) ,

then (31) follows.

Finally, let R_{\frac{k+1}{k}} (m) ≡ 2 (mod k + 1). Again, for y = (R_{\frac{k+1}{k}} (m) − 2)/(k + 1) the interval

(ky, (k + 1)y) = (\frac{k}{k + 1}(R_{\frac{k+1}{k}} (m) − 2), R_{\frac{k+1}{k}} (m) − 2)  (34)

cannot contain more than m − 1 primes. Indeed, comparing interval (34) with interval (33), we see that they contain the same integers except for R_{\frac{k+1}{k}} (m)−2, which is multiple of k +1. Therefore, they contain the same number of primes, and this number does not exceed m − 1. Again, since the following interval of type (ky, (k + 1)y) with integer y ≥ \frac{k}{k+1}(R_{\frac{k+1}{k}} (m) − 2) is

(\frac{k}{k + 1}(R_{\frac{k+1}{k}} (m) + k − 1), R_{\frac{k+1}{k}} (m) + k − 1) ,

then (32) follows.

As a corollary from (29), (31) and (32), we obtain the following formula in case k = 2.

Proposition 10.

N_{2}(m) = \begin{cases}2, & if m = 1; \\ ⌈\frac{R_{\frac{3}{2}} (m)}{3}⌉ , & if m ≥ 2. \end{cases}  (35)

Note that, if k ≥ 3 and R_{\frac{k+1}{k}} (m) ≡ j (mod k + 1), 3 ≤ j ≤ k, then, generally speaking,

(30) is not an equality. Evidently, N_{k}(m) ≥ N_{k}(m−1), and it is interesting that the equality is attainable (see sequences (37)–(40) below).

Example 11. Let k = 3, m = 2. Then v = \frac{4}{3} and, by (14), R_{\frac{4}{3}} (2) = 29 ≡ 1 (mod 4). Therefore, by (31), N_{3}(2) = \frac{29+3}{4} = 8. Indeed, interval (3 · 7, 4 · 7) already contains only prime 23.

Example 12. Let k = 3, m = 3. Then, by (14), R_{\frac{4}{3}} (3) = 59 ≡ 3 (mod 4). Here N_{3}(3) = 11

which is essentially less than ⌈R_{\frac{4}{3}} (3)/4⌉ = 15. Indeed, each interval

(3 · 15, 4 · 15), (3 · 14, 4 · 14), (3 · 13, 4 · 13), (3 · 12, 4 · 12), (3 · 11, 4 · 11)

contains more than 2 primes and only interval (3 · 10, 4 · 10) contains only 2 primes.

In any case, Proposition 9 allows us to calculate terms of sequence {N_{k}(m)} for every considered value of k. So, we obtain the following few terms of {N_{k}(m)} :

for k = 2,

2, 5, 13, 14, 23, 25, 33, 43, 46, 58, 60, 61, 71, 77, 80, 88, 103, 104, …;  (36)

for k = 3,

2, 8, 11, 17, 26, 38, 40, 41, 48, 57, 68, 68, 70, 87, 96, 100, 108, 109, …;  (37)

for k = 5,

2, 7, 17, 24, 25, 38, 41, 58, 59, 64, 65, 73, 95, 97, 103, 106, 107, 108, …;  (38)

for k = 9,

2, 14, 23, 23, 34, 36, 57, 58, 60, 60, 77, 86, 100, 100, 102, 123, 149, …;  (39)

for k = 14,

2, 11, 24, 37, 38, 39, 50, 96, 96, 96, 96, 97, 97, 125, 125, 132, 178, 178, …  (40)

Remark 13. If, as in [1, 6], instead of intervals (kn, (k +1)n), we consider intervals [kn, (k + 1)n], then sequences (5) and (36)–(38) would begin with 1.

6 Method of small intervals

If we know a theorem of the type: for x ≥ x_{0}(Δ), the interval (x, (1+ \frac{1}{Δ})x] contains a prime, then we can calculate a bounded number of the first terms of sequences (5) and (36)–(40). Indeed, put x_{1} = kn, such that n ≥ \frac{x_{0}}{k}. Then (k + 1)n = \frac{k+1}{k}x_{1} and, if 1 + \frac{1}{Δ} < \frac{k+1}{k}, i.e., Δ > k, then

(x_{1}, (1 + \frac{1}{Δ})x_{1}] ⊂ (kn, (k + 1)n).

Thus, if n ≥ \frac{x_{0}}{k} , then the interval (kn, (k + 1)n) contains a prime, and using method of finite descent, we can find N_{k}(1). Further, put x_{2} = (1+ \frac{1}{Δ})x_{1}. Then interval (x_{2}, (1+ \frac{1}{Δ})x_{2}] also contains a prime. Thus the union

(x_{1}, (1 + \frac{1}{Δ})x_{1}] ∪ (x_{2}, (1 + \frac{1}{Δ})x_{2}] = (x_{1}, (1 + \frac{1}{Δ})^{2}x_{1}]

contains at least two primes. This means that if (1 + \frac{1}{Δ})^{2}x_{1} < (k + 1)n or (1 + \frac{1}{Δ})^{2} < 1 + \frac{1}{k}, then

(x_{1}, (1 + \frac{1}{Δ})^{2}x_{1}] ⊂ (kn, (k + 1)n)

and the interval (kn, (k + 1)n) contains at least two primes; again, using method of finite descent, we can find N_{k}(2) etc. If (1 + \frac{1}{Δ})^{m} < 1 + \frac{1}{k}, then

(x_{1}, (1 + \frac{1}{Δ})^{m}x_{1}] ⊂ (kn, (k + 1)n)

and the interval (kn, (k + 1)n) contains at least m primes and we can find N_{k}(m). In this way, we can find N_{k}(m) for m < \frac{ln(1+ \frac{1}{k})}{ln(1+ \frac{1}{Δ} )}. In 2002, Ramaré and Saouter [9] proved that the interval (x(1−28314000^{−1}), x) always contains a prime if x > 10726905041, or, equivalently, the interval (x, (1 + 28313999^{−1})x) contains a prime if x > 10726905419. This means that, e.g., we can find N_{14}(m) for m ≤ 1954471. Unfortunately, this method cannot give the exact bounds and formulas for N_{k}(m) as (30)–(32).

We can also consider a more general application of this method. Consider a fixed infinite set P of primes which we call P -primes. Furthermore, consider the following generalization of v-Ramanujan numbers.

Definition 14. For v > 1, a (v, P)-Ramanujan number, R_{v}^{(P)}(m), is the smallest integer such that if x ≥ R_{v}^{(P)}(m), then π_{P} (x) − π_{P} (x/v) ≥ m, where π_{P} (x) is the number of P -primes not exceeding x.

Note that every (v, P)-Ramanujan number is P -prime. If we know a theorem of the type: for x ≥ x_{0}(Δ), the interval (x, (1 + \frac{1}{Δ})x] contains a P -prime, then using the above described algorithm, we can calculate a bounded number of the first (v, P) -Ramanujan numbers. For example, let P be the set of primes p ≡ 1 (mod 3). From the result of Cullinan and Hajir [2] it follows, in particular, that for x ≥ 106706, the interval (x, 1.048x) contains a P -prime. Using the same algorithm, we can calculate the first 14 (2, P)-Ramanujan numbers. They are

7, 31, 43, 67, 97, 103, 151, 163, 181, 223, 229, 271, 331, 337.  (41)

Analogously, if P is the set of primes p ≡ 2 (mod 3), then the sequence of (2, P)-Ramanujan numbers begins

11, 23, 47, 59, 83, 107, 131, 167, 227, 233, 239, 251, 263, 281, …;  (42)

if P is the set of primes p ≡ 1 (mod 4), then the sequence of (2, P)-Ramanujan numbers begins

13, 37, 41, 89, 97, 109, 149, 229, 233, 241, 257, 277, 281, 317, …;  (43)

and, if P is the set of primes p ≡ 3 (mod 4), then the sequence of (2, P)-Ramanujan numbers begins

7, 23, 47, 67, 71, 103, 127, 167, 179, 191, 223, 227, 263, 307, …;  (44)

Let N_{k}^{(P)}(m) denote the smallest number such that for n ≥ N_{k}^{(P)}(m), the interval (kn, (k + 1)n) contains at least m P -primes. It is easy to see that formulas (30)–(32) hold for N_{k}^{(P)}(m) and R(P)_{\frac{k+1}{k}} (m). In particular, in cases k = 1, 2 we have the formulas

N_{1}^{(P)}(m) = \frac{R_{2}^{(P)}(m) + 1}{2}, N_{2}^{(P)}(m) = ⌈\frac{R(P)_{\frac{3}{2}}(m)}{3}⌉ .  (45)

Therefore, the following sequences for N_{1}^{(P)}(m), correspond to sequences (41)–(44) respectively:

4, 16, 22, 34, 49, 52, 76, 82, 91, 112, 115, 136, 166, 169, …;  (46)
6, 12, 24, 30, 42, 54, 66, 84, 114, 117, 120, 126, 132, 141, …;  (47)
7, 19, 21, 45, 49, 55, 75, 115, 117, 121, 129, 139, 141, 159, …;  (48)
4, 12, 24, 34, 36, 52, 64, 84, 90, 96, 112, 114, 132, 154, …  (49)

7 The proof of Theorem 1

For k ≥ 1, let a(k) denote the least integer n > 1 for which the interval (kn, (k + 1)n) contains no prime; if no such n exists, we put a(k) = 0. Taking into account (29), note that a(k) = 0 for k = 1, 2, 3, 5, 9, 14. Consider sequence \{a(k)\}. Its first few terms are (\underline{A218831} in [13])

0, 0, 0, 2, 0, 4, 2, 3, 0, 2, 3, 2, 2, 0, 6, 2, 2, 3, 2, 6, 3, 2, 4, 2, 2, 7, 2, 2, 4, 3, …  (50)

Calculations of a(k) for k ∈ [1, 15], except for k = 1, 2, 3, 5, 9, 14, give positive values of a(k). Computer calculations of a(k) in the range {16, …, 10^{8}} show that all values of a(k) in this range are positive and belong to the interval [2, 16]. This completes the proof.

In conclusion, we present a distribution of numbers of values a(k) = 2, 3, …, 16 within intervals {[1, 10^{7}(i)]}, i = 1, …, 10. All these numerical results are obtained using the following Mathematica program:

s t a r t =2; cutOff =100;
a218831=Table [
NestWhile[#+1&, s t a r t ,
Union [PrimeQ[ Range[# k+1,# ( k+1) −1]]]!={ False}&,
1 , cutOff ] ,
{k , 1 , 1 0 0 0 0 0 0 0 0 }] / . { cutOff+s t a r t −>0};

We have for a(k) = 2 the numbers

8729394, 17566347, 26437886, 35330619, 44238546,
53158353, 62087802, 71025543, 79969616, 88921064.

In general, here we have a simple explicit formula: the number of a(k) = 2, k ≤ K is K + 1 − π(2K + 1). Further, let

A_{t}(K) = |{k ≤ K : a(k) = t}|.

In cases t ≥ 3 we have no explicit formulas. But, taking into account the distribution of primes into residue classes, a rough argument suggests that A_{t}(K) ≍ c_{t}K(ln K)^{2−t}. For example, for a(k) = 3 within the considered intervals we have the numbers

1061880, 2050703, 3014798, 3963752, 4901317,
5830488, 6752801, 7668802, 8580597, 9486975,

and one can hope that c_{3} ≈ 1.7 · · ·. In other cases we have

t = 4 : 173835, 321315, 461745, 597249, 729660, 859605, 987238, 1113288, 1237558, 1360344;

t = 5 : 25108, 45086, 63177, 80407, 97199, 113213, 128850, 144474, 159648, 174577;
t = 6 : 7312, 12542, 17150, 21536, 25714, 29734, 33616, 37243, 40952, 44503;
t = 7 : 1753, 2918, 3841, 4749, 5590, 6373, 7201, 7950, 8691, 9378;
t = 8 : 449, 703, 918, 1109, 1309, 1507, 1670, 1810, 1977, 2141;

t = 9 : 149, 216, 278, 342, 400, 440, 508, 558, 606, 647;
t = 10 : 73, 109, 138, 164, 186, 203, 222, 232, 249, 262;
t = 11 : 18, 25, 29, 31, 35, 36, 42, 46, 48, 49;
t = 12 : 13, 15, 17, 19, 21, 25, 26, 29, 30, 31;
t = 13 : 2, 3, 3, 3, 3, 3, 3, 4, 7, 7;
t = 14 : 4, 5, 6, 6, 6, 6, 7, 7, 7, 8;
t = 15 : 0, 2, 3, 3, 3, 3, 3, 3, 3, 3;
t = 16 : 4, 5, 5, 5, 5, 5, 5, 5, 5, 5.

For those t when the difference

\frac{A_{t}(10^{8})}{10^{8}}(8 ln 10)^{t−2} − \frac{A_{t}(10^{7})}{10^{7}}(7 ln 10)^{t−2}

remains less than 0.5, we can get an impression about the change of c_{t} depending on t. So, c_{2} = 1 and approximately c_{3} = 1.7, c_{4} = 4.6, c_{5} = 11, c_{6} = 49.

8 Acknowledgment

The authors are grateful to N. J. A. Sloane for several important remarks. They thank also an anonymous referee for useful and constructive comments that promoted an essential improvement of the paper.

References

[1] M. El Bachraoui, Primes in the interval [2n, 3n], Int. J. Contemp. Math. Sciences 1 (2006), no. 13, 617–621.

[2] J. Cullinan, and F. Hajir, Primes of prescribed congruence class in short intervals, INTEGERS 12 (2012), Article A56.

[3] P. Dusart, Estimates of some functions over primes without R.H., preprint. Available

    at http://arxiv.org/abs/1002.0442.

[4] P. Erdős, and J. Surányi, Topics in the Theory of Numbers, Undergraduate Texts in Mathematics, Springer-Verlag, 2003.

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

[6] A. Loo, On the primes in the interval [3n, 4n], Int. J. Contemp. Math. Sciences 6 (2011), no. 38, 1871–1882.

[7] J. Nagura, On the interval containing at least one prime number, Proc. Japan Academy, Ser. A 28 (1952), 177–181.

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

[9] O. Ramaré, and Y. Saouter, Short effective intervals containing primes, J. Number Theory 98 (2003), 10–33.

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

[11] B. Rosser, The n-th prime is greater than n ln n, Proc. London Math. Soc. 45 (1939), 21–44.

[12] V. Shevelev, Ramanujan and Labos primes, their generalizations, and classifications of primes, J. Integer Seq. 15 (2012), Article 12.5.4.

[13] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electroni-

    cally at http://oeis.org.

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

2010 Mathematics Subject Classification: Primary 11A41. Keywords: prime number, generalized Ramanujan prime.

(Concerned with sequences \underline{A084140}, \underline{A104272}, \underline{A164952}, \underline{A185004}, \underline{A185005}, \underline{A185006}, \underline{A185007}, \underline{A218769}, \underline{A218831}, \underline{A218850}, \underline{A220268}, \underline{A220269}, \underline{A220273}, \underline{A220274}, \underline{A220281}, \underline{A220293}, \underline{A220462}, \underline{A220463}, \underline{A220474}, and \underline{A220475}.)

Received January 1 2013; revised versions received May 7 2013; June 10 2013; July 25 2013. Published in Journal of Integer Sequences, July 31 2013.

Return to Journal of Integer Sequences home page.