Wikipedia

Ramanujan prime: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
rv addition of unreferenced and overexplained example section
Tags: Manual revert Mobile edit Mobile web edit Advanced mobile edit
 
(48 intermediate revisions by 18 users not shown)
Line 1:
{{short description|Prime fulfilling an inequality related to the prime-counting function}}
{{Distinguish|Hardy–Ramanujan number}}
 
Line 6 ⟶ 7:
In 1919, Ramanujan published a new proof of [[Bertrand's postulate]] which, as he notes, was first proved by [[Pafnuty Chebyshev|Chebyshev]].<ref>{{Citation |first=S. |last=Ramanujan |title=A proof of Bertrand's postulate |journal=Journal of the Indian Mathematical Society |volume=11 |year=1919 |pages=181–182 |url=http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper24/page1.htm }}</ref> At the end of the two-page published paper, Ramanujan derived a generalized result, and that is:
 
: <math>\pi(x) - \pi\left( \frac x/ 2 \right) \ge 1,2,3,4,5,\ldots \text{ for all } x \ge 2, 11, 17, 29, 41, \ldots \text{ respectively}</math>&nbsp;&nbsp;&nbsp;&nbsp;{{OEIS2C|id=A104272}}
 
where <math>\pi(x)</math> is the [[prime-counting function]], equal to the number of primes less than or equal to&nbsp;''x''.
Line 12 ⟶ 13:
The converse of this result is the definition of Ramanujan primes:
 
:The ''n''th Ramanujan prime is the least integer ''R<sub>n</sub>'' for which <math>\pi(x) - \pi(x/2) \ge n,</math> for all ''x'' ≥ ''R<sub>n</sub>''.<ref>{{MathWorld||authorlinkauthor-link=Jonathan Sondow|author=Jonathan Sondow|title=Ramanujan Prime|urlname=RamanujanPrime}}</ref> In other words: Ramanujan primes are the least integers ''R<sub>n</sub>'' for which there are at least ''n'' primes between ''x'' and ''x''/2 for all ''x'' ≥ ''R<sub>n</sub>''.
 
The first five Ramanujan primes are thus 2, 11, 17, 29, and 41. Equivalently.
 
Note that the integer ''R<sub>n</sub>'' is necessarily a prime number: <math>\pi(x) - \pi(x/2)</math> and, hence, <math>\pi(x)</math> must increase by obtaining another prime at ''x'' = ''R<sub>n</sub>''. Since <math>\pi(x) - \pi(x/2)</math> can increase by at most&nbsp;1,
Line 36 ⟶ 37:
:''R''<sub>''n''</sub> ~ ''p''<sub>2''n''</sub> (''n'' → ∞).
 
All these results were proved by Sondow (2009),<ref>{{Citation |first=J. |last=Sondow |title=Ramanujan primes and Bertrand's postulate |journal=Amer. Math. Monthly |volume=116 |issue=7 |year=2009 |pages=630–635 |arxiv=0907.5232 |doi=10.4169/193009709x458609}}</ref> except for the upper bound ''R''<sub>''n''</sub> < ''p''<sub>3''n''</sub> which was conjectured by him and proved by Laishram (2010).<ref>{{Citation |first=S. |last=Laishram |title=On a conjecture on Ramanujan primes |journal=[[International Journal of Number Theory]] |volume=6 |issue=8 |year=2010 |pages=1869–1873 |url=http://www.isid.ac.in/~shanta/PAPERS/RamanujanPrimes-IJNT.pdf |doi=10.1142/s1793042110003848|citeseerx=10.1.1.639.4934 }}.</ref> The bound was improved by Sondow, Nicholson, and Noe (2011)<ref>{{Citation |first1=J. |last1=Sondow |first2=J. |last2=Nicholson |first3=T.D. |last3=Noe |title=Ramanujan primes: bounds, runs, twins, and gaps |journal=Journal of Integer Sequences |volume=14|year=2011 |pages=11.6.2|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Noe/noe12.pdf|arxiv=1105.2249|bibcode=2011arXiv1105.2249S }}</ref> to
 
:<math>R_n \le \frac{41}{47} \ p_{3n}</math>
 
which is the optimal form of ''R''<sub>''n''</sub> ≤ ''c·p''<sub>3''n''</sub> since it is an equality for ''n'' = 5.
 
In a different direction, Axler<ref>{{Cite journal|last=Axler|first=Christian|title=On generalized Ramanujan primes|journal=The Ramanujan Journal|volume=39|issue=2016|pages=1|arxiv=1401.7179|year=2014|doi=10.1007/s11139-015-9693-9}}</ref> showed that
 
:<math>R_n < p_{\lceil t\cdot n \rceil}</math>
 
is optimal for ''t'' > 48/19, where <math>\lceil\cdot \rceil</math> is the [[Floor and ceiling functions|ceiling function]].
 
A further improvement of the upper bounds was done in late 2015 by Anitha Srinivasan and John W. Nicholson.<ref>{{Cite journal|first1=Anitha |last1=Srinivasan |first2=John |last2=Nicholson |title=An Improved Upper Bound For Ramanujan Primes|journal=Integers |volume=15 |year=2015 |url=http://www.emis.de/journals/INTEGERS/papers/p52/p52.pdf}}</ref> They show that if
 
:<math>\alpha = 1+\frac{3}{\ln n + \ln \ln n -4}</math>
 
then <math>R_n < p_{\lfloor2n\alpha\rfloor}</math> for all <math> n>241</math>, where <math>\lfloor\cdot\rfloor</math> is the [[Floor and ceiling functions|floor function]]. For
large ''n'', the bound is smaller and thus better than <math>p_{\lfloor2nc\rfloor}</math> for any fixed constant <math>c >1</math>.
 
In 2016, Shichun Yang and Alain Togbe<ref>{{Cite journal|first1=Yang |last1=Shichun |first2=Togbe |last2=Togbe |title=On the estimates of the upper and lower bounds of Ramanujan primes|journal=The Ramanujan Journal |volume=40 |year=2016 |url=DOI 10.1007/s11139-015-9706-8}}</ref> establish the estimates of the upper and lower bounds of Ramanujan primes <math>R_n<math> when ''n'' is big: If <math>n > 10^{300}<math> and <math>R_n= p_s<math>, then
 
:<math>\beta<s<\alpha, </math>
 
where
 
:<math>\alpha=2n \Big(1+\frac{\ln2}{\ln n}-\frac{\ln2 \ln \ln n-\ln ^2 2-\ln2 -0.13}{\ln ^2 n}\Big), </math>
 
:<math>\alpha=2n\Big(1+\frac{\ln2}{\ln n}-\frac{\ln2 \ln \ln n-\ln ^2 2-\ln2 -0.11}{\ln ^2 n}\Big). </math>
 
== Generalized Ramanujan primes ==
 
Given a constant ''c'' between 0 and 1, the ''n''th ''c''-Ramanujan prime is defined as the
smallest integer ''R<sub>c,n</sub>'' with the property that for any integer ''x ≥ R<sub>c,n</sub>'' there are at least ''n'' primes between ''cx''
and ''x'', that is, <math>\pi(x) - \pi(cx) \ge n</math>. In particular, when ''c'' = 1/2, the ''n''th 1/2-Ramanujan prime is equal to the ''n''th Ramanujan prime: ''R''<sub>0.5,''n''</sub> = ''R<sub>n</sub>''.
 
For ''c'' = 1/4 and 3/4, the sequence of ''c''-Ramanujan primes begins
 
:''R''<sub>0.25,''n''</sub> = 2, 3, 5, 13, 17, ... {{OEIS2C|id=A193761}},
 
:''R''<sub>0.75,''n''</sub> = 11, 29, 59, 67, 101, ... {{OEIS2C|id=A193880}}.
 
It is known<ref>{{Citation |first1=N. |last1=Amersi |first2=O. |last2=Beckwith |first3=S.J. |last3=Miller |first4=R. |last4=Ronan |first5=J. |last5=Sondow |title=Generalized Ramanujan primes |year=2011 |arxiv=1108.0475}}</ref> that, for all ''n'' and ''c'', the ''n''th ''c''-Ramanujan prime ''R<sub>c,n</sub>'' exists and is indeed prime. Also, as ''n'' tends to infinity, ''R<sub>c,n</sub>'' is asymptotic to ''p''<sub>''n''/(1&nbsp;&minus;&nbsp;''c'')</sub>
 
:''R''<sub>''c'',''n''</sub> ~ ''p''<sub>''n''/(1&nbsp;&minus;&nbsp;''c'')</sub> (''n'' → ∞)
 
where ''p''<sub>''n''/(1&nbsp;&minus;&nbsp;''c'')</sub> is the <math>\lfloor</math>''n''/(1&nbsp;&minus;&nbsp;''c'')<math>\rfloor </math>th prime and <math>\lfloor .\rfloor</math> is the [[Floor and ceiling functions|floor]] function.
 
== Ramanujan prime corollary ==
 
:<math>2p_{i-n} > p_i \text{ for } i>k \text{ where } k=\pi(p_k)=\pi(R_n)\, ,</math>
 
i.e. ''p''<sub>''k''</sub> is the ''k''th prime and the ''n''th Ramanujan prime.
 
This is very useful in showing the number of primes in the range [''p''<sub>''k''</sub>, 2''p''<sub>''i''−''n''</sub>] is greater than or equal to&nbsp;1. By taking into account the size of the gaps between primes in [''p''<sub>''i''&minus;''n''</sub>,''p''<sub>''k''</sub>], one can see that the average prime gap is about ln(''p''<sub>''k''</sub>) using the following ''R''<sub>''n''</sub>/(2''n'') ~ ln(''R''<sub>''n''</sub>).
 
Proof of Corollary:
 
If ''p''<sub>''i''</sub> > ''R''<sub>''n''</sub>, then ''p''<sub>''i''</sub> is odd and ''p''<sub>''i''</sub> &minus; 1 ≥ ''R''<sub>''n''</sub>, and hence
''π''(''p''<sub>''i''</sub> &minus; 1) &minus; ''π''(''p''<sub>''i''</sub>/2) = ''π''(''p''<sub>''i''</sub> &minus; 1) &minus; ''π''((''p''<sub>''i''</sub> &minus; 1)/2) ≥&nbsp;''n''.
Thus ''p''<sub>''i''</sub> &minus; 1 ≥ ''p''<sub>''i''&minus;1</sub> > ''p''<sub>''i''&minus;2</sub> > ''p''<sub>''i''&minus;3</sub> > ... > ''p''<sub>''i''&minus;''n''</sub> > ''p''<sub>''i''</sub>/2, and so 2''p''<sub>''i''&minus;''n''</sub> > ''p''<sub>''i''</sub>.
 
An example of this corollary:
 
With ''n'' = 1000, ''R''<sub>''n''</sub> = ''p''<sub>''k''</sub> = 19403, and ''k'' = 2197, therefore ''i'' ≥ 2198 and ''i''&minus;''n'' ≥ 1198.
The smallest ''i''&nbsp;&minus;&nbsp;''n'' prime is ''p''<sub>''i''&minus;''n''</sub> = 9719, therefore 2''p''<sub>''i''&minus;''n''</sub> = 2&nbsp;&times;&nbsp;9719 = 19438. The 2198th prime, ''p''<sub>''i''</sub>, is between ''p''<sub>''k''</sub> = 19403 and 2''p''<sub>''i''&minus;''n''</sub> = 19438 and is 19417.
 
The left side of the Ramanujan Prime Corollary is the {{OEIS2C|id=A168421}}; the smallest prime on the right side is {{OEIS2C|id=A168425}}. The sequence {{OEIS2C|id=A165959}} is the range of the smallest prime greater than p<sub>k</sub>. The values of <math>\pi(R_n)\,</math> are in the {{OEIS2C|id=A179196}}.
 
The Ramanujan Prime Corollary is due to John Nicholson.
 
Srinivasan's Lemma <ref>{{Citation |first=Anitha |last=Srinivasan |title=An upper bound for Ramanujan primes |journal=Integers |volume=14 |year=2014 |url=http://www.emis.ams.org/journals/INTEGERS/papers/o19/o19.pdf }}</ref> states that ''p''<sub>''k''−''n''</sub>&nbsp;<&nbsp;''p''<sub>''k''</sub>/2 if ''R''<sub>''n''</sub> =&nbsp;''p''<sub>''k''</sub> and&nbsp;''n''&nbsp;>&nbsp;1. Proof: By the minimality of ''R''<sub>''n''</sub>, the interval (''p''<sub>''k''</sub>/2,''p''<sub>''k''</sub>] contains exactly ''n'' primes and hence&nbsp;''p''<sub>''k''−''n''</sub>&nbsp;<&nbsp;''p''<sub>''k''</sub>/2.
 
==References==
Retrieved from "https://en.wikipedia.org/wiki/Ramanujan_prime"