Ramanujan prime

In mathematics, a Ramanujan prime is a prime number that satisfies a result proven by Srinivasa Ramanujan relating to the prime-counting function.

Origins and definition

In 1919, Ramanujan published a new proof of Bertrand's postulate which, as he notes, was first proved by Chebyshev.^[1] At the end of the two-page published paper, Ramanujan derived a generalized result, and that is:

$\pi(x) - \pi(x/2) \ge 1,2,3,4,5,\ldots \text{ for all } x \ge 2, 11, 17, 29, 41, \ldots \text{respectively}$ A104272

where $\pi(x)$ is the prime-counting function, equal to the number of primes less than or equal to x.

The converse of this result is the definition of Ramanujan primes:

The nth Ramanujan prime is the least integer R_n for which $\pi(x) - \pi(x/2) \ge n,$ for all x ≥ R_n.^[2]

The first five Ramanujan primes are thus 2, 11, 17, 29, and 41. Equivalently,

Ramanujan primes are the least integers R_n for which there are at least n primes between x and x/2 for all x ≥ R_n.

Note that the integer R_n is necessarily a prime number: $\pi(x) - \pi(x/2)$ and, hence, $\pi(x)$ must increase by obtaining another prime at x = R_n. Since $\pi(x) - \pi(x/2)$ can increase by at most 1,

$\pi(R_n) - \pi\left( \frac{R_n} 2 \right) = n.$

Bounds and an asymptotic formula

For all n ≥ 1, the bounds

2n ln 2n < R_n < 4n ln 4n

hold. If n > 1, then also

p_2n < R_n < p_3n

where p_n is the nth prime number.

As n tends to infinity, R_n is asymptotic to the 2nth prime, i.e.,

R_n ~ p_2n (n → ∞).

All these results were proved by Sondow (2009),^[3] except for the upper bound R_n < p_3n which was conjectured by him and proved by Laishram (2010).^[4] The bound was improved by Sondow, Nicholson, and Noe (2011)^[5] to

$R_n \le \frac{41}{47} \ p_{3n}$

which is the optimal form of R_n < c·p_3n since it is an equality for n = 5.

In a different direction, Axler^[6] showed that

$R_n < p_{\lceil t\cdot n \rceil}$

is optimal for t > 48/19, where $\lceil\cdot \rceil$ is the ceiling function.

A further improvement of the upper bounds was done in late 2015 by Anitha Srinivasan and John W. Nicholson.^[7] They show that if

$\alpha = 1+\frac{3}{\ln n + \ln \ln n -4}$

then $R_n < p_{\lfloor2n\alpha\rfloor}$ for all $n>241$, where $\lfloor\cdot\rfloor$ is the floor function. For large n, the bound is smaller and thus better than $p_{\lfloor2nc\rfloor}$ for any fixed constant $c >1$.

Generalized Ramanujan primes

Given a constant c between 0 and 1, the nth c-Ramanujan prime is defined as the smallest integer R_c,n with the property that for any integer x ≥ R_c,n there are at least n primes between cx and x, that is, $\pi(x) - \pi(cx) \ge n$. In particular, when c = 1/2, the nth 1/2-Ramanujan prime is equal to the nth Ramanujan prime: R_0.5,n = R_n.

For c = 1/4 and 3/4, the sequence of c-Ramanujan primes begins

R_0.25,n = 2, 3, 5, 13, 17, ...  A193761,

R_0.75,n = 11, 29, 59, 67, 101, ...  A193880.

It is known^[8] that, for all n and c, the nth c-Ramanujan prime R_c,n exists and is indeed prime. Also, as n tends to infinity, R_c,n is asymptotic to p_{n/(1 − c)}

R_c,n ~ p_{n/(1 − c)} (n → ∞)

where p_{n/(1 − c)} is the $\lfloor$n/(1 − c)$\rfloor$th prime and $\lfloor .\rfloor$ is the floor function.

Ramanujan prime corollary

$2p_{i-n} > p_i \text{ for } i>k \text{ where } k=\pi(p_k)=\pi(R_n)\, ,$

i.e. p_k is the kth prime and the nth Ramanujan prime.

This is very useful in showing the number of primes in the range [p_k, 2*p_i-n] is greater than or equal to 1. By taking into account the size of the gaps between primes in [p_i−n,p_k], one can see that the average prime gap is about ln(p_k) using the following R_n/(2n) ~ ln(R_n).

Proof of Corollary:

If p_i > R_n, then p_i is odd and p_i − 1 ≥ R_n, and hence π(p_i − 1) − π(p_i/2) = π(p_i − 1) − π((p_i − 1)/2) ≥ n. Thus p_i − 1 ≥ p_i−1 > p_i−2 > p_i−3 > ... > p_i−n > p_i/2, and so 2p_i−n > p_i.

An example of this corollary:

With n = 1000, R_n = p_k = 19403, and k = 2197, therefore i ≥ 2198 and i−n ≥ 1198. The smallest i − n prime is p_i−n = 9719, therefore 2p_i−n = 2 × 9719 = 19438. The 2198th prime, p_i, is between p_k = 19403 and 2p_i−n = 19438 and is 19417.

The left side of the Ramanujan Prime Corollary is the  A168421; the smallest prime on the right side is  A168425. The sequence  A165959 is the range of the smallest prime greater than p_k. The values of $\pi(R_n)\,$ are in the  A179196.

The Ramanujan Prime Corollary is due to John Nicholson.

Srinivasan's Lemma ^[9] states that p_k-n < p_k/2 if R_n = p_k and n > 1. Proof: By the minimality of R_n, the interval (p_k/2,p_k] contains exactly n primes and hence p_k-n < p_k/2.

References

1. Ramanujan, S. (1919), "A proof of Bertrand's postulate", Journal of the Indian Mathematical Society 11: 181–182
2. Jonathan Sondow, "Ramanujan Prime", MathWorld.
3. Sondow, J. (2009), "Ramanujan primes and Bertrand's postulate", Amer. Math. Monthly 116: 630–635, arXiv:0907.5232, doi:10.4169/193009709x458609
4. Laishram, S. (2010), "On a conjecture on Ramanujan primes" (PDF), International Journal of Number Theory 6: 1869–1873, doi:10.1142/s1793042110003848.
5. Sondow, J.; Nicholson, J.; Noe, T.D. (2011), "Ramanujan primes: bounds, runs, twins, and gaps" (PDF), Journal of Integer Sequences 14: 11.6.2, arXiv:1105.2249
6. Axler, Christian. "On generalized Ramanujan primes". Retrieved 16 April 2014.
7. Srinivasan, Anitha; Nicholson, John (2015). "An Improved Upper Bound For Ramanujan Primes" (PDF). Integers.
8. Amersi, N.; Beckwith, O.; Miller, S.J.; Ronan, R.; Sondow, J. (2011), Generalized Ramanujan primes, arXiv:1108.0475
9. Srinivasan, Anitha (2014), "An upper bound for Ramanujan primes" (PDF), Integers 14