Ramanujan Primes: Bounds, Runs, Twins, and Gaps

Jonathan Sondow 209 West 97th Street New York, NY 10025 USA

             jsondow@alumni.princeton.edu

John W. Nicholson P. O. Box 2423 Arlington, TX 76004 USA

                reddwarf2956@yahoo.com

Tony D. Noe 14025 NW Harvest Lane Portland, OR 97229 USA

                   noe@sspectra.com

Abstract

The nth Ramanujan prime is the smallest positive integer R_{n} such that if x ≥ R_{n}, then the interval (\frac{1}{2}x, x] contains at least n primes. We sharpen Laishram’s theorem that R_{n} < p_{3n} by proving that the maximum of R_{n}/p_{3n} is R_{5}/p_{15} = 41/47. We give statistics on the length of the longest run of Ramanujan primes among all primes p < 10^{n}, for n ≤ 9. We prove that if an upper twin prime is Ramanujan, then so is the lower; a table gives the number of twin primes below 10^{n} of three types. Finally, we relate runs of Ramanujan primes to prime gaps. Along the way we state several conjectures and open problems. An appendix explains Noe’s fast algorithm for computing R_{1}, R_{2}, …, R_{n}.

1 Introduction

For n ≥ 1, the nth Ramanujan prime is defined as the smallest positive integer R_{n} with the property that for any x ≥ R_{n}, there are at least n primes p with \frac{1}{2}x < p ≤ x. By its minimality, R_{n} is indeed a prime, and the interval (\frac{1}{2}R_{n}, R_{n}] contains exactly n primes [10].

In 1919 Ramanujan proved a result which implies that R_{n} exists, and he gave the first five Ramanujan primes. (We formulate his result as a theorem and quote him.)

Theorem 1 (Ramanujan). “Let π(x) denote the number of primes not exceeding x. Then … π(x) − π(\frac{1}{2}x) ≥ 1, 2, 3, 4, 5, …, if x ≥ 2, 11, 17, 29, 41, …, respectively.”

Proof. This follows from properties of the Γ-function. See Ramanujan [4] for details, and Shapiro [8, Section 9.3B] for an exposition of Ramanujan’s idea.

The case R_{1} = 2 is Bertrand’s Postulate: for all x ≥ 2, there exists a prime p with \frac{1}{2}x < p ≤ x. For n = 1, 2, 3, …, the nth Ramanujan prime [9, Sequence \underline{A104272}] is

R_{n} = 2, 11, 17, 29, 41, 47, 59, 67, 71, 97, 101, 107, 127, 149, 151, 167, 179, 181, 227, 229, 233, ….

In the present paper, we report progress on three predictions [10, Conjectures 1, 2, 3] about Ramanujan primes: on bounds, runs, and twins.

In the next section, we sharpen Laishram’s theorem that R_{n} < p_{3n}, where p_{n} denotes the nth prime. Namely, we prove the optimal bound that the maximum value of R_{n}/p_{3n} is R_{5}/p_{15} = 41/47. The proof uses another result of Laishram and a computation of the first 169350 Ramanujan primes by Noe’s fast algorithm. Our first new conjecture follows.

In Section 3, we present statistics on the length of the longest run of Ramanujan primes among all primes p < 10^{n}, for n ≤ 9. We pose an open problem on the unexpectedly long runs of non-Ramanujan primes, and make a new conjecture about both types of runs.

In Section 4, we prove that if the larger of two twin primes is Ramanujan, then its smaller twin is also Ramanujan, and we provide a table of data on the number of twins below 10^{n}, again for n ≤ 9. We offer several new conjectures and open problems on twin primes.

In Section 5, we associate runs of odd Ramanujan primes to certain prime gaps.

An appendix explains the algorithm for computing Ramanujan primes and includes a Mathematica program.

2 Bounds

Here are some estimates for the nth Ramanujan prime.

Theorem 2 (Sondow). The following inequalities hold:

2n log 2n < p_{2n} < R_{n} < 4n log 4n < p_{4n}  (n > 1).  (1)

Moreover, for every ϵ > 0, there exists N_{0}(ϵ) > 0 such that

R_{n} < (2 + ϵ)n log n  (n ≥ N_{0}(ϵ)).  (2)

In particular, R_{n} ∼ p_{2n} as n → ∞.

Proof. Inequalities of Rosser and Schoenfeld for π(x), together with Rosser’s theorem [6] that p_{n} > n log n, lead to (1). The bound (2) follows from the Prime Number Theorem. For details, see Sondow [10].

A prediction [10, Conjecture 1] that (1) can be improved to p_{2n} < R_{n} < p_{3n} has been proved by Laishram.

Theorem 3 (Laishram). For all n ≥ 1, we have R_{n} < p_{3n}.

Proof. Dusart’s inequalities [2] for Chebychev’s function

θ(x) := ∑_{prime p ≤ x}log p ≤ π(x) log x

lead to an explicit value of N_{0}(ϵ) in (2), for each ϵ > 0. For details, see Laishram [3].

Using one of those values and a fast algorithm for computing Ramanujan primes (see the Appendix), we sharpen Theorem 3 by giving an optimal upper bound on R_{n}/p_{3n}, namely, its maximum. (Notice that the rational numbers R_{n}/p_{3n} are all distinct, because the p_{3n} are distinct primes and 0 < R_{n}/p_{3n} < 1. Thus the maximum occurs at only one value of n.)

Theorem 4. The maximum value of R_{n}/p_{3n} is

max_{n≥1} \frac{R_{n}}{p_{3n}} = \frac{R_{5}}{p_{15}} = \frac{41}{47} = 0.8723 ….

Proof. Since 41/47 > 0.8666 … = 13/15, it suffices to show R_{n}/p_{3n} < 13/15 for n ≠ 5.

Set ϵ = 3/5 and substitute 2 + ϵ = 13/5 into (2). Using Rosser’s theorem with 3n in place of n, we can write the result as

R_{n} < \frac{13}{15} 3n log n < \frac{13}{15} p_{3n} (n ≥ N_{0}(3/5)).

According to Laishram [3, Theorem 1], if 0 < ϵ ≤ 1.08, then N_{0}(ϵ) = (2/ϵ)^{c/ϵ} in (2), where c = c(ϵ) = 6 at ϵ = 0.6. Hence N_{0}(3/5) = (10/3)^{10} = 169350.87 …, and so

\frac{R_{n}}{p_{3n}} < \frac{13}{15} (n > 169350).

To complete the proof, we compute the first 169350 Ramanujan primes and then check that R_{n}/p_{3n} < 13/15 when 5 ≠ n ≤ 169350.

Similarly, one can show that

max_{n≠5} \frac{R_{n}}{p_{3n}} = \frac{R_{10}}{p_{30}} = \frac{97}{113} = 0.8584 …,
max_{n≠5 or 10} \frac{R_{n}}{p_{3n}} = \frac{R_{2}}{p_{6}} = \frac{11}{13} = 0.8461 …,

and so on down towards

lim_{n→∞} \frac{R_{n}}{p_{3n}} = \frac{2}{3} = 0.666 ….

We conclude this section with a related prediction.

Conjecture 5. For m = 1, 2, 3, …, let N(m) be given by the following table.

\begin{matrix}m & 1 & 2 & 3 & 4 & 5 & 6 & 7, 8, …, 19 & 20, 21, … \\ N(m) & 1 & 1245 & 189 & 189 & 85 & 85 & 10 & 2 \end{matrix}

Then we have

π(R_{mn}) ≤ mπ(R_{n}) (n ≥ N(m)).

Equivalently, if we define the function ρ by ρ(n) := π(R_{n}), so that R_{n} = p_{ρ(n)}, then

ρ(mn) ≤ mρ(n) (n ≥ N(m)).

In the cases m = 2, 3, …, 20, the statement has been verified for all n with R_{mn} < 10^{9}. The first few values of ρ(n), for n = 1, 2, 3, …, are [9, Sequence \underline{A179196}]

ρ(n) = 1, 5, 7, 10, 13, 15, 17, 19, 20, 25, 26, 28, 31, 35, 36, 39, 41, 42, 49, 50, 51, 52, 53, ….

Note that Theorems 2 and 3 imply 2n < ρ(n) < 3n for all n > 1, and ρ(n) ∼ 2n as n → ∞. The latter yields ρ(mn) ∼ 2mn ∼ mρ(n) as n → ∞, for any fixed m ≥ 1.

3 Runs

Since p_{2n} < R_{n} ∼ p_{2n} as n → ∞, the probability of a randomly chosen prime being Ramanujan is slightly less than 1/2, roughly speaking. More precisely, column 2 in Table 1 gives the probability P_{n} (rounded to 3 decimal places) that a prime p < 10^{n} is a Ramanujan prime, for n = 1, 2, …, 9.

Let us consider a coin-tossing model. Suppose that a biased coin has probability P of heads. According to Schilling [7], the expected length EL_{N} = EL_{N}(P) of the longest run of heads in a sequence of N coin tosses is approximately equal to

EL_{N} ≈ \frac{log N}{log(1/P)} − (\frac{1}{2} − \frac{log(1 − P) + γ}{log(1/P)} ) ,

where γ = 0.5772 … is the Euler-Mascheroni constant. The variance VarL_{N} = VarL_{N}(P) is close [7] to

VarL_{N} ≈ \frac{π^{2}}{6 log(1/P)^{2}} + \frac{1}{12}

“and is quite remarkable for the property that it is essentially constant with respect to” N. For example, with a fair coin,

EL_{N} ≈ \frac{log N}{log 2} − (\frac{3}{2} − \frac{γ}{log 2}) = \frac{log N}{log 2} − 0.667 …  (P = \frac{1}{2})  (3)

and

VarL_{N} ≈ \frac{π^{2}}{6(log 2)^{2}} + \frac{1}{12} = 3.507 …  (P = \frac{1}{2}) .  (4)

Schilling points out that by (4) “the standard deviation of the longest run is approximately (VarL_{N})^{1/2} ≈ 1.873, an amazingly small value. This implies that the length of the longest run is quite predictable indeed; normally it is within about two of its expectation.”

This is nearly true of the longest run of Ramanujan primes in the sequence of prime numbers below 10^{n} (where P = P_{n} ⪅ 1/2), at least for n ≤ 9. But for non-Ramanujan primes (where P = 1 − P_{n} ⪆ 1/2), the actual length of the longest run exceeds the expected length by much more than two, at least for n = 6, 7, 8, 9. (See Table 1, in which the two columns marked “Actual” are [9, Sequences \underline{A189993} and \underline{A189994}].)

Probability P_{n} of a prime  Length of the longest run below 10^{n} of
p < 10^{n}  Ramanujan primes non-Ramanujan primes
n  being Ramanujan  Expected Actual Expected  Actual
1  .250  1  1  5  3
2  .400  5  2  8  4
3  .429  8  5  11  7
4  .455  11  13  14  13
5  .465  14  13  18  20
6  .471  18  20  21  36
7  .476  21  21  24  47
8  .479  24  26  28  47
9  .482  28  31  31  65

Table 1: Length of the longest run of (non-)Ramanujan primes below 10^{n}.

Problem 6. Explain the unexpectedly long runs of non-Ramanujan primes among primes p < 10^{n}, for n ≥ 6.

Formula (3) suggests the following predictions supported by Table 1. They strengthen an earlier prediction [10, Conjecture 2] that arbitrarily long runs of both types exist.

Conjecture 7. We have

lim sup_{N→ ∞} \frac{length of the longest run of Ramanujan primes among primes ≤ p_{N}}{log N/ log 2} ≥ 1

and the same holds true if “Ramanujan” is replaced with “non-Ramanujan”.

For n = 1, 2, …, the first run of n Ramanujan primes begins at

2, 67, 227, 227, 227, 2657, 2657, 2657, 2657, 2657, 2657, 2657, 2657, 562871, 793487, …,

and the first run of n non-Ramanujan primes at

3, 3, 3, 73, 191, 191, 509, 2539, 2539, 5279, 9901, 9901, 9901, 11593, 11593, 55343, 55343, …,

respectively [9, Sequences \underline{A174602} and \underline{A174641}].

4 Twins

If p_{n}+2 = p_{n+1}, then p_{n} and p_{n+1} are twin primes; the smallest are 3 and 5. If R_{n}+2 = R_{n+1}, then R_{n} and R_{n+1} are twin Ramanujan primes; the smallest are 149 and 151.

Given primes p and q > p, a necessary condition for them to be twin Ramanujan primes is evidently that

π(p) − π(\frac{1}{2}p) + 1 = π(q) − π(\frac{1}{2}q) .  (5)

To see that the condition is not sufficient, even when p and q are consecutive primes p_{k} and p_{k+1}, verify (5) for any one of the pairs

(p, q) = (p_{k}, p_{k+1}) = (11, 13), (47, 53), (67, 71), (109, 113), (137, 139),  (6)

where Ramanujan primes are in bold.

It is less evident that (5) is a necessary condition for p and q even to be (ordinary) twin primes, but that is not hard to prove [10, Proposition 1].

Proposition 8. If p and q = p + 2 are twin primes with p > 5, then (5) holds.

The converse is false, even when p and q are consecutive primes both of which are Ramanujan, as the example (p_{19}, p_{20}) = (67, 71) = (R_{8}, R_{9}) shows.

As mentioned, each pair in (6) consists of consecutive primes p < q satisfying (5). However, in no pair is q a Ramanujan prime but not p; in fact, such a pair cannot exist.

Proposition 9. (i). If the larger of two twin primes is Ramanujan, then the smaller is also Ramanujan: they are twin Ramanujan primes. (ii). More generally, given consecutive primes (p, q) = (p_{k}, p_{k+1}) satisfying (5), if q = R_{n+1}, then p = R_{n}.

Proof. Part (i) is (vacuously) true for twin primes p and q = p + 2 with p ≤ 5. For p > 5 it suffices, by Proposition 8, to prove part (ii).

Since q = R_{n+1}, we have π(x) − π(\frac{1}{2}x) ≥ n + 1 when x ≥ q, and (5) implies that π(p) − π(\frac{1}{2}p) = n. To prove that p = R_{n}, we have to show that π(p − 1) − π(\frac{1}{2}(p − 1)) < n, and that π(x) − π(\frac{1}{2}x) ≥ n for x = p + 1, p + 2, …, q − 1.

If ℓ is any prime, then π(ℓ − 1) + 1 = π(ℓ) and π(\frac{1}{2}(ℓ − 1)) = π(\frac{1}{2}ℓ), so that the quantity π(y) − π(\frac{1}{2}y) increases by 1 from y = ℓ − 1 to y = ℓ. Taking ℓ = p or ℓ = q, we infer that π(ℓ − 1) − π(\frac{1}{2}(ℓ − 1)) = n − 1 or n, respectively. As p and q are consecutive primes, it follows that π(x) = π(q − 1) and π(\frac{1}{2}x) ≤ π(\frac{1}{2}(q − 1)), for x = p + 1, p + 2, …, q − 1, implying π(x) − π(\frac{1}{2}x) ≥ n. This proves the required inequalities.

Part (i) was conjectured by Noe [9, Sequence \underline{A173081}].

Corollary 10. If we denote

π_{2,1}(x) := #{pairs of twin primes ≤ x : one or both are Ramanujan},
π_{2,2}(x) := #{pairs of twin primes ≤ x : both are Ramanujan},

then for all x ≥ 0 we have the equalities

π_{2,1}(x) = #{pairs of twin primes ≤ x : the smaller is Ramanujan},
π_{2,2}(x) = #{pairs of twin primes ≤ x : the larger is Ramanujan}.

Proof. By Proposition 9 part (i), given twin primes p and p+2, if p+2 = R_{n+1}, then p = R_{n}. The corollary follows.

Table 2 gives some figures (see [9, Sequences \underline{A007508}, \underline{A173081}, \underline{A181678}]) on

π_{2}(x) := #{pairs of twin primes ≤ x},

π_{2,1}(x), π_{2,2}(x), and their ratios. Proposition 8 and Corollary 10 will help to explain why many values of the ratios are greater than might be expected a priori.

π_{∗} = π_{∗}(10^{n})
n  π_{2}  π_{2,1}  π_{2,2}  π_{2,1}/π_{2} π_{2,2}/π_{2} π_{2,2}/π_{2,1}
1  2  0  0  0  0  –
2  8  6  0 .750  0  0
3  35  28  10 .800  .286  .357
4  205  167  73 .815  .356  .437
5  1224  694  508 .788  .415  .527
6  8169  6305  3468 .772  .425  .550
7  58980 45082 25629 .764  .434  .568
8 440312 335919 194614 .763  .442  .579
9 3424506 2605867 1537504 .761  .449  .590

Table 2: Counting three types of pairs of twin primes below 10^{n}.

The probability that two randomly chosen primes p and q are both Ramanujan is slightly less than 1/2 × 1/2 = 1/4, roughly speaking. The probability increases if p and q are twin primes, because then Proposition 8 guarantees that the necessary condition (5) holds.

For that reason, and based on the first 1000 Ramanujan primes, it was predicted [10, Conjecture 3] that more than 1/4 of the twin primes up to x are twin Ramanujan primes, if x ≥ 571. This is borne out for x = 10^{n}, with 3 ≤ n ≤ 9, by Table 2. It shows that the prediction can be improved to π_{2,2}(x)/π_{2}(x) > 2/5, for x ≥ 10^{5}.

Corollary 10 implies that whether a twin prime pair is counted in π_{2,1}(x) or π_{2,2}(x) depends on only one of the two primes being Ramanujan. This suggests that the ratios π_{2,1}(x)/π_{2}(x) and π_{2,2}(x)/π_{2}(x) should approach 1/2 as x tends to infinity.

We conclude this section with these and other conjectures based on our results and on Table 2, as well as with two more open problems.

Conjecture 11. For all x ≥ 10^{5}, we have

\frac{π_{2,1}(x)}{π_{2}(x)} < \frac{4}{5},  \frac{π_{2,2}(x)}{π_{2}(x)} > \frac{2}{5},  \frac{π_{2,2}(x)}{π_{2,1}(x)} > \frac{2/5}{4/5} = \frac{1}{2}.

Conjecture 12. If π_{2}(x) → ∞ as x → ∞, then π_{2,1}(x) ∼ π_{2,2}(x) ∼ \frac{1}{2}π_{2}(x).

Recall Brun’s famous theorem [1] that the series of reciprocals of the twin primes converges or is finite (unlike the series of reciprocals of all the primes, which Euler showed diverges). Its sum [9, Sequence \underline{A065421}] is Brun’s constant B_{2},

B_{2} := (\frac{1}{3} + \frac{1}{5}) + (\frac{1}{5} + \frac{1}{7}) + (\frac{1}{11} + \frac{1}{13}) + (\frac{1}{17} + \frac{1}{19}) + ⋯ =^{?} 1.9021605 ….

Here =^{?} means that the value of B_{2} is conditional “on heuristic considerations about the distribution of twin primes” (Ribenboim [5, p. 201]).

Problem 13. Compute the analogous constant B_{2,1} for twin primes at least one of which is Ramanujan,

B_{2,1} := (\frac{1}{11} + \frac{1}{13}) + (\frac{1}{17} + \frac{1}{19}) + (\frac{1}{29} + \frac{1}{31}) + (\frac{1}{41} + \frac{1}{43}) + · · · .

The numbers 11, 17, 29, 41, … [9, Sequence \underline{A178128}] are the lesser of twin primes if at least one is Ramanujan. By Corollary 10, that is the same as the lesser of twin primes if it is Ramanujan.

Problem 14. Compute the analogous constant B_{2,2} for twin Ramanujan primes,

B_{2,2} := (\frac{1}{149} + \frac{1}{151}) + (\frac{1}{179} + \frac{1}{181}) + (\frac{1}{227} + \frac{1}{229}) + (\frac{1}{239} + \frac{1}{241}) + · · · .

The numbers 149, 179, 227, 239, … [9, Sequence \underline{A178127}] are the lesser of twin Ramanujan primes.

5 Prime gaps

Let us say that there is a prime gap from a to b ≥ a if none of the numbers a, a+1, a+2, …, b is prime. Given a run of r odd Ramanujan primes starting at p, we can associate to it a prime gap of length at least r starting at \frac{1}{2}(p + 1).

Proposition 15. (i). If p = R_{n} is odd, then the integer \frac{1}{2}(p + 1) is not prime. (ii). More generally, given a run of r ≥ 1 odd Ramanujan primes from p = R_{n} = p_{k} to q = R_{n+r−1} = p_{k+r−1}, there is a prime gap from \frac{1}{2}(p + 1) to \frac{1}{2}(q + 1). (iii). Parts (i) and (ii) are sharp in the sense that, for certain runs of Ramanujan primes p to q, both \frac{1}{2}(p + 1) − 1 and \frac{1}{2}(q + 1) + 1 are prime numbers. (iv). But in the case r = 2, if p and q are twin Ramanujan primes, then the prime gap from \frac{1}{2}(p + 1) to \frac{1}{2}(q + 1) always lies in a longer prime gap of length 5 or more.

Proof. (i). Since p = R_{n} is odd, π(p) = π(p + 1), and the quantity π(x) − π(\frac{1}{2}x) does not decrease from x = p to x = p + 1. Hence π(\frac{1}{2}p) ≥ π(\frac{1}{2}(p + 1)), and so \frac{1}{2}(p + 1) is not prime. (ii). By (i), the case r = 1 holds. Taking r = 2, let p = R_{n} = p_{k} and q = R_{n+1} = p_{k+1} be odd. By (i), neither \frac{1}{2}(p + 1) nor \frac{1}{2}(q + 1) is prime. If an integer i lies strictly between them, then the oddness of p and q implies p + 1 < j := 2i − 1 < q − 1. Since p = p_{k} and q = p_{k+1}, we have π(p) = k = π(j + 1). As p = R_{n} and q = R_{n+1}, it follows that π(x) − π(\frac{1}{2}x) does not decrease from x = p to x = j + 1. Hence π(\frac{1}{2}p) ≥ π (\frac{1}{2}(j + 1)) = π(i), and so i is also not prime. This proves (ii) for runs of length 2.

The general case follows easily by induction on r. Namely, given a run of length r > 2 from R_{n} = p_{k} to R_{n+r−1} = p_{k+r−1}, break it into a run of length 2 from R_{n} = p_{k} to R_{n+1} = p_{k+1}, concatenated with a run of length r − 1 from R_{n+1} = p_{k+1} to R_{n+r−1} = p_{k+r−1}. (iii). For r = 1, the composite number \frac{1}{2}(R_{2} + 1) = \frac{1}{2}(11 + 1) = 6 lies between the primes 5 and 7. For an example with r > 1, take the run (R_{293}, R_{294}) = (4919, 4931) = (p_{657}, p_{658}) of length r = 2. It is associated to the prime gap from \frac{1}{2}(R_{293}+1) = 2460 to \frac{1}{2}(R_{294}+1) = 2466, which is bounded by the primes 2459 and 2467. (iv). Since p > 3 and q are twin primes, (p, q) = (6k − 1, 6k + 1) for some k. If k = 2i is even, then (\frac{1}{2}(p + 1), \frac{1}{2}(q + 1)) = (6i, 6i + 1) lies in the prime gap from 6i to 6i + 4.

Now assume that k = 2i + 1 is odd. Then (\frac{1}{2}(p + 1), \frac{1}{2}(q + 1)) = (6i + 3, 6i + 4) will lie in a prime gap from 6i + 2 to 6i + 6, unless 6i + 5 is prime. But if 6i + 5 = \frac{1}{2}(q + 3) were prime, then, since q + 2 = 6k + 3 is not prime, π(x) − π(\frac{1}{2}x) would decrease from x = q to x = q +3, contradicting the fact that q is a Ramanujan prime. This completes the proof.

For part (iii), the first “sharp” example of a run of length r = 1, 2, …, 11 begins at the Ramanujan prime

11, 4919, 1439, 7187, 37547, 210143, 3376943, 663563, 4429739, 17939627, 12034427,

respectively [9, Sequence \underline{A177804}]. An example of part (iv) is the prime gap associated to the twin Ramanujan primes R_{14} = 149 and R_{15} = 151, which lies in the larger prime gap

74, \frac{1}{2}(R_{14} + 1) = 75, \frac{1}{2}(R_{15} + 1) = 76, 77, 78.

6 Appendix on the algorithm

To compute a range of Ramanujan primes R_{i} for 1 ≤ i ≤ n, we perform simple calculations in each interval (k/2, k] for k = 1, 2, …, p_{3n} − 1. To facilitate the calculation, we use a counter s and a list L with n elements L_{i}. Initially, s and all L_{i} are set to zero. They are updated as each interval is processed.

After processing an interval, s will be equal to the number of primes in that interval, and each L_{i} will be equal either to the greatest index of the intervals so far processed that contain exactly i primes, or to zero if no interval having exactly i primes has yet been processed.

Having processed interval k−1, to find the number of primes in interval k we perform two operations: add 1 to s if k is prime, and subtract 1 from s if k/2 is prime. We then update the sth element of the list to L_{s} = k, because now k is the largest index of all intervals processed that contain exactly s primes.

After all intervals have been processed, the list R of Ramanujan primes is obtained by adding 1 to each element of the list L.

These ideas are captured in the following Mathematica program for finding the first 169350 Ramanujan primes.

                    nn = 169350;
                    L = Table[0, {nn}];
                    s = 0;
                    Do[
                       If[PrimeQ[k], s++];
                       If[PrimeQ[k/2], s--];
                       If[s < nn, L[[s+1]] = k],
                       {k, Prime[3*nn]-1}];
                    R = L + 1

Although it is adequate for computing a modest number of them, to compute many more requires a speedup of several orders of magnitude. That can be achieved by using a lower-level programming language and generating prime numbers via a sieve. With this speedup we computed all Ramanujan primes below 10^{9} in less than three minutes on a 2.8 GHz Pentium 4 computer.

7 Acknowledgment

The authors are grateful to Steven Finch for pointing out Schilling’s paper [7].

References

[1] V. Brun, La série \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \frac{1}{13} + \frac{1}{17} + \frac{1}{19} + \frac{1}{29} + \frac{1}{31} + \frac{1}{41} + \frac{1}{43} + \frac{1}{59} + \frac{1}{61} + ⋯ où les dénominateurs sont “nombres premiers jumeaux” est convergente ou finie, Bull. Soc. Math. France 43 (1919), 100–104, 124–128.

[2] P. Dusart, Inégalités explicites pour ψ(X), θ(X), π(X) et les nombres premiers, C. R. Math. Acad. Sci. Soc. R. Can. 21 (1999), 53–59.

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

http://www.isid.ac.in/^{∼}shanta/PAPERS/RamanujanPrimes.pdf.

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

http://www.imsc.res.in/^{∼}rao/ramanujan/CamUnivCpapers/Cpaper24/.

[5] P. Ribenboim, The Book of Prime Number Records, 2nd. ed., Springer-Verlag, New York, 1989.

[6] J. B. Rosser, The nth prime is greater than n ln n, Proc. London Math. Soc. 45 (1938), 21–44.

[7] M. F. Schilling, The longest run of heads, College Math. J. 21 (1990), 196–207; also available at

    http://users.eecs.northwestern.edu/^{∼}nickle/310/2010/headRuns.pdf.

[8] H. N. Shapiro, Introduction to the Theory of Numbers, Wiley, New York, 1983; reprinted by Dover, Mineola, NY, 2008.

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

    cally at http://oeis.org, 2011.

[10] J. Sondow, Ramanujan primes and Bertrand’s postulate, Amer. Math. Monthly 116 (2009), 630–635; also available at http://arxiv.org/abs/0907.5232.

2010 Mathematics Subject Classification: Primary 11A41. Keywords: prime gap, Ramanujan prime, twin prime.

(Concerned with sequences \underline{A007508}, \underline{A065421}, \underline{A104272}, \underline{A173081}, \underline{A174602}, \underline{A174641}, \underline{A177804}, \underline{A178127}, \underline{A178128}, \underline{A179196}, \underline{A181678}, \underline{A189993}, and \underline{A189994}.)

Received December 14 2010; revised version received May 11 2011. Published in Journal of Integer Sequences, May 17 2011.

Return to Journal of Integer Sequences home page.