|
%I #339 Feb 24 2023 02:37:30
%S 2,11,17,29,41,47,59,67,71,97,101,107,127,149,151,167,179,181,227,229,
%T 233,239,241,263,269,281,307,311,347,349,367,373,401,409,419,431,433,
%U 439,461,487,491,503,569,571,587,593,599,601,607,641,643,647,653,659
%N Ramanujan primes R_n: a(n) is the smallest number such that if x >= a(n), then pi(x) - pi(x/2) >= n, where pi(x) is the number of primes <= x.
%C Referring to his proof of Bertrand's postulate, Ramanujan states a generalization: "From this we easily deduce that pi(x) - pi(x/2) >= 1, 2, 3, 4, 5, ..., if x >= 2, 11, 17, 29, 41, ..., respectively." Since the a(n) are prime (by their minimality), I call them "Ramanujan primes."
%C See the additional references and links mentioned in A143227.
%C 2n log 2n < a(n) < 4n log 4n for n >= 1, and prime(2n) < a(n) < prime(4n) if n > 1. Also, a(n) ~ prime(2n) as n -> infinity.
%C Shanta Laishram has proved that a(n) < prime(3n) for all n >= 1.
%C a(n) - 3n log 3n is sometimes positive, but negative with increasing frequency as n grows since a(n) ~ 2n log 2n. There should be a constant m such that for n >= m we have a(n) < 3n log 3n.
%C A good approximation to a(n) = R_n for n in [1..1000] is A162996(n) = Round(k*n * (log(k*n)+1)), with k = 2.216 determined empirically from the first 1000 Ramanujan primes, which approximates the {k*n}-th prime number which in turn approximates the n-th Ramanujan prime and where Abs(A162996(n) - R_n) < 2 * Sqrt(A162996(n)) for n in [1..1000]. Since R_n ~ prime(2n) ~ 2n * (log(2n)+1) ~ 2n * log(2n), while A162996(n) ~ prime(k*n) ~ k*n * (log(k*n)+1) ~ k*n * log(k*n), A162996(n) / R_n ~ k/2 = 2.216/2 = 1.108 which implies an asymptotic overestimate of about 10% (a better approximation would need k to depend on n and be asymptotic to 2.) - _Daniel Forgues_, Jul 29 2009
%C Let p_n be the n-th prime. If p_n>=3 is in the sequence, then all integers (p_n+1)/2, (p_n+3)/2, ..., (p_(n+1)-1)/2 are composite numbers. - _Vladimir Shevelev_, Aug 12 2009
%C Denote by q(n) the prime which is the nearest from the right to a(n)/2. Then there exists a prime between a(n) and 2q(n). Converse, generally speaking, is not true, i.e., there exist primes outside the sequence, but possess such property (e.g., 109). - _Vladimir Shevelev_, Aug 14 2009
%C The Mathematica program FasterRamanujanPrimeList uses Laishram's result that a(n) < prime(3n).
%C See sequence A164952 for a generalization we call a Ramanujan k-prime. - _Vladimir Shevelev_, Sep 01 2009
%C From _Jonathan Sondow_, May 22 2010: (Start)
%C About 46% of primes < 19000 are Ramanujan primes. About 78% of the lesser of twin primes < 19000 are Ramanujan primes.
%C About 15% of primes < 19000 are the lesser of twin primes. About 26% of Ramanujan primes < 19000 are the lesser of twin primes.
%C A reason for the jumps is in Section 7 of "Ramanujan primes and Bertrand's postulate" and in Section 4 of "Ramanujan Primes: Bounds, Runs, Twins, and Gaps". (See the arXiv link for a corrected version of Table 1.)
%C See Shapiro 2008 for an exposition of Ramanujan's proof of his generalization of Bertrand's postulate. (End)
%C The (10^n)-th R prime: 2, 97, 1439, 19403, 242057, 2916539, 34072993, 389433437, .... - _Robert G. Wilson v_, May 07 2011, updated Aug 02 2012
%C The number of R primes < 10^n: 1, 10, 72, 559, 4459, 36960, 316066, 2760321, .... - _Robert G. Wilson v_, Aug 02 2012
%C a(n) = R_n = R_{0.5,n} in "Generalized Ramanujan Primes."
%C All Ramanujan primes are in A164368. - _Vladimir Shevelev_, Aug 30 2011
%C If n tends to infinity, then limsup(a(n) - A080359(n-1)) = infinity; conjecture: also limsup(a(n) - A080359(n)) = infinity (cf. A182366). - _Vladimir Shevelev_, Apr 27 2012
%C Or the largest prime x such that the number of primes in (x/2,x] equals n. This equivalent definition underlines an important analogy between Ramanujan and Labos primes (cf. A080359). - _Vladimir Shevelev_, Apr 29 2012
%C Research questions on R_n - prime(2n) are at A233739, and on n-Ramanujan primes at A225907. - _Jonathan Sondow_, Dec 16 2013
%C The questions on R_n - prime(2n) in A233739 have been answered by Christian Axler in "On generalized Ramanujan primes". - _Jonathan Sondow_, Feb 13 2014
%C Srinivasan's Lemma (2014): prime(k-n) < prime(k)/2 if R_n = prime(k) and n > 1. Proof: By the minimality of R_n, the interval (prime(k)/2,prime(k)] contains exactly n primes and so prime(k-n) < prime(k)/2. - _Jonathan Sondow_, May 10 2014
%C For some n and k, we see that A168421(k) = a(n) so as to form a chain of primes similar to a Cunningham chain. For example (and the first example), A168421(2) = 7, links a(2) = 11 = A168421(3), links a(3) = 17 = A168421(4), links a(4) = 29 = A168421(6), links a(6) = 47. Note that the links do not have to be of a form like q = 2*p+1 or q = 2*p-1. - _John W. Nicholson_, Feb 22 2015
%C Extending Sondow's 2010 comments: About 48% of primes < 10^9 are Ramanujan primes. About 76% of the lesser of twin primes < 10^9 are Ramanujan primes. - _Dana Jacobsen_, Sep 06 2015
%C Sondow, Nicholson, and Noe's 2011 conjecture that pi(R_{m*n}) <= m*pi(R_n) for m >= 1 and n >= N_m (see A190413, A190414) was proved for n > 10^300 by Shichun Yang and Alain Togbé in 2015. - _Jonathan Sondow_, Dec 01 2015
%C Berliner, Dean, Hook, Marr, Mbirika, and McBee (2016) prove in Theorem 18 that the graph K_{m,n} is prime for n >= R_{m-1}-m; see A291465. - _Jonathan Sondow_, May 21 2017
%C Okhotin (2012) uses Ramanujan primes to prove Lemma 8 in "Unambiguous finite automata over a unary alphabet." - _Jonathan Sondow_, May 30 2017
%C Sepulcre and Vidal (2016) apply Ramanujan primes in Remark 9 of "On the non-isolation of the real projections of the zeros of exponential polynomials." - _Jonathan Sondow_, May 30 2017
%C Axler and Leßmann (2017) compute the first k-Ramanujan prime for k >= 1 + epsilon; see A277718, A277719, A290394. - _Jonathan Sondow_, Jul 30 2017
%D Srinivasa Ramanujan, Collected Papers of Srinivasa Ramanujan (Ed. G. H. Hardy, S. Aiyar, P. Venkatesvara and B. M. Wilson), Amer. Math. Soc., Providence, 2000, pp. 208-209.
%D Harold N. Shapiro, Ramanujan's idea, Section 9.3B in Introduction to the Theory of Numbers, Dover, 2008.
%H T. D. Noe, <a href="/A104272/b104272.txt">Table of n, a(n) for n = 1..10000</a>
%H N. Amersi, O. Beckwith, S. J. Miller, R. Ronan, J. Sondow, <a href="http://arxiv.org/abs/1108.0475">Generalized Ramanujan primes</a>, arXiv:1108.0475 [math.NT], 2011.
%H N. Amersi, O. Beckwith, S. J. Miller, R. Ronan, J. Sondow, <a href="https://doi.org/10.1007/978-1-4939-1601-6_1">Generalized Ramanujan primes</a>, Combinatorial and Additive Number Theory, Springer Proc. in Math. & Stat., CANT 2011 and 2012, Vol. 101 (2014), 1-13
%H Christian Axler, <a href="http://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=26247">Über die Primzahl-Zählfunktion, die n-te Primzahl und verallgemeinerte Ramanujan-Primzahlen</a>, Ph.D. thesis 2013, in German, English summary.
%H Christian Axler, <a href="http://arxiv.org/abs/1401.7179">On generalized Ramanujan primes</a>, arXiv:1401.7179 [math.NT], 2014.
%H Christian Axler, <a href="http://dx.doi.org/10.1007/s11139-015-9693-9">On generalized Ramanujan primes</a>, Ramanujan J. 39 (1) (2016) 1-30.
%H Christian Axler and Thomas Leßmann, <a href="http://arxiv.org/abs/1504.05485">An explicit upper bound for the first k-Ramanujan prime</a>, arXiv:1504.05485 [math.NT], 2015.
%H Christian Axler and Thomas Leßmann, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.124.7.642">On the first k-Ramanujan prime</a>, Amer. Math. Monthly, 124 (2017), 642-646.
%H Adam H. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, C. McBee, <a href="http://arxiv.org/abs/1604.07698">Coprime and prime labelings of graphs</a>, arXiv preprint arXiv:1604.07698 [math.CO], 2016; <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Mbirika/mbi3.html">Journal of Integer Sequences, Vol. 19 (2016), #16.5.8.</a>
%H Paul Erdős, <a href="https://www.renyi.hu/~p_erdos/1934-01.pdf">A theorem of Sylvester and Schur</a>, J. London Math. Soc., 9 (1934), 282-288.
%H Peter Hegarty, <a href="http://arxiv.org/abs/1201.3847">Why should one expect to find long runs of (non)-Ramanujan primes?</a>, arXiv:1201.3847 [math.NT], 2012.
%H Ernest G. Hibbs, <a href="https://www.proquest.com/openview/4012f0286b785cd732c78eb0fc6fce80">Component Interactions of the Prime Numbers</a>, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
%H Shanta Laishram, <a href="http://www.isid.ac.in/~shanta/PAPERS/RamanujanPrimes-IJNT.pdf">On a conjecture on Ramanujan primes</a>, Int. J. Number Theory, 6 (2010), 1869-1873.
%H Catherine Lee, <a href="https://arxiv.org/abs/1907.12670">Minimum coprime graph labelings</a>, arXiv:1907.12670 [math.CO], 2019.
%H Jaban Meher and M. Ram Murty, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.120.07.650">Ramanujan's proof of Bertrand's postulate</a>, Amer. Math. Monthly, Vol. 120, No. 7 (2013), pp. 650-653.
%H Alexander Okhotin, <a href="https://doi.org/10.1016/j.ic.2012.01.003">Unambiguous finite automata over a unary alphabet</a>, Inf. Comput., 212 (2012), 15-36.
%H Murat Baris Paksoy, <a href="http://arxiv.org/abs/1210.6991">Derived Ramanujan primes: R'_n</a>, arXiv:1210.6991 [math.NT], 2012.
%H PlanetMath, <a href="http://planetmath.org/ramanujanprime">Ramanujan prime</a>
%H Srinivasa Ramanujan, <a href="http://ramanujan.sirinudi.org/Volumes/published/ram24.html">A proof of Bertrand's postulate</a>, J. Indian Math. Soc., 11 (1919), 181-182.
%H Juan Matias Sepulcre and Tomás Vidal, <a href="https://rua.ua.es/dspace/bitstream/10045/62689/5/2016_Sepulcre_Vidal_JMathAnalAppl_preprint.pdf">On the non-isolation of the real projections of the zeros of exponential polynomials</a>, J. Math. Anal. Appl., 437 (2016) No. 1, 513-525.
%H Vladimir Shevelev, <a href="http://arXiv.org/abs/0908.2319">On critical small intervals containing primes</a>, arXiv:0908.2319 [math.NT], 2009.
%H Vladimir Shevelev, <a href="http://arxiv.org/abs/0909.0715">Ramanujan and Labos primes, their generalizations and classifications of primes</a>, arXiv:0909.0715 [math.NT], 2009-2011.
%H Vladimir Shevelev, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Shevelev/shevelev19.html">Ramanujan and Labos primes, their generalizations, and classifications of primes</a>, J. Integer Seq. 15 (2012) Article 12.5.4
%H Vladimir Shevelev, Charles R. Greathouse IV, Peter J. C. Moses, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Moses/moses1.html">On intervals (kn, (k+1)n) containing a prime for all n>1</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.7.3. <a href="http://arxiv.org/abs/1212.2785">arXiv:1212.2785</a>
%H Jonathan Sondow, <a href="http://arxiv.org/abs/0907.5232">Ramanujan primes and Bertrand's postulate</a>, arXiv:0907.5232 [math.NT], 2009-2010.
%H Jonathan Sondow, <a href="http://www.jstor.org/stable/40391170">Ramanujan primes and Bertrand's postulate</a>, Amer. Math. Monthly, 116 (2009), 630-635. <a href="https://zbmath.org/?q=an:1229.11013">Zentralblatt review</a>
%H Jonathan Sondow, J. W. Nicholson, and T. D. Noe, <a href="http://arxiv.org/abs/1105.2249">Ramanujan Primes: Bounds, Runs, Twins, and Gaps</a>, arXiv:1105.2249 [math.NT] 2011; J. Integer Seq. 14 (2011) Article 11.6.2.
%H Jonathan Sondow, <a href="http://mathworld.wolfram.com/RamanujanPrime.html">Ramanujan Prime</a>, Eric Weisstein's MathWorld.
%H Jonathan Sondow and E. Weisstein, <a href="http://mathworld.wolfram.com/BertrandsPostulate.html">Bertrand's Postulate</a>, MathWorld.
%H Anitha Srinivasan, <a href="http://www.emis.de/journals/INTEGERS/papers/o19/o19.Abstract.html">An upper bound for Ramanujan primes</a>, Integers, 14 (2014), #A19.
%H Anitha Srinivasan and John W. Nicholson, <a href="http://www.emis.de/journals/INTEGERS/papers/p52/p52.Abstract.html">An improved upper bound for Ramanujan primes</a>, Integers, 15 (2015), #A52.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Bertrand%27s_postulate">Bertrand's postulate</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Ramanujan_prime">Ramanujan prime</a>.
%H Shichun Yang and Alain Togbé, <a href="http://dx.doi.org/10.1007/s11139-015-9706-8">On the estimates of the upper and lower bounds of Ramanujan primes</a>, Ramanujan J., online 14 August 2015, 1-11.
%F a(n) = 1 + max{k: pi(k) - pi(k/2) = n - 1}.
%F a(n) = A080360(n-1) + 1 for n > 1.
%F a(n) >= A080359(n). - _Vladimir Shevelev_, Aug 20 2009
%F A193761(n) <= a(n) <= A193880(n).
%F a(n) = 2*A084140(n) - 1, for n > 1. - _Jonathan Sondow_, Dec 21 2012
%F a(n) = prime(2n) + A233739(n) = (A233822(n) + a(n+1))/2. - _Jonathan Sondow_, Dec 16 2013
%F a(n) = max{prime p: pi(p) - pi(p/2) = n} (see Shevelev 2012). - _Jonathan Sondow_, Mar 23 2016
%F a(n) = A000040(A179196(n)). - _R. J. Mathar_, Sep 21 2017
%F Sum_{n>=1} (-1)^(n+1)/a(n) = A190303. - _Amiram Eldar_, Nov 20 2020
%e a(1) = 2 is Bertrand's postulate: pi(x) - pi(x/2) >= 1 for all x >= 2.
%e a(2) = 11 because a(2) < 8 log 8 < 17 and pi(n) - pi(n/2) > 1 for n = 16, 15, ..., 11 but pi(10) - pi(5) = 1.
%e Consider a(9)=71. Then the nearest prime > 71/2 is 37, and between a(9) and 2*37, that is, between 71 and 74, there exists a prime (73). - _Vladimir Shevelev_, Aug 14 2009 [corrected by _Jonathan Sondow_, Jun 17 2013]
%p A104272 := proc(n::integer)
%p local R;
%p if n = 1 then
%p return 2;
%p end if;
%p R := ithprime(3*n-1) ; # upper limit Laishram's thrm Thrm 3 arXiv:1105.2249
%p while true do
%p if A056171(R) = n then # Defn. 1. of Shevelev JIS 14 (2012) 12.1.1
%p return R ;
%p end if;
%p R := prevprime(R) ;
%p end do:
%p end proc:
%p seq(A104272(n),n=1..200) ; # slow downstream search <= p(3n-1) _R. J. Mathar_, Sep 21 2017
%t (RamanujanPrimeList[n_] := With[{T=Table[{k,PrimePi[k]-PrimePi[k/2]}, {k,Ceiling[N[4*n*Log[4*n]]]}]}, Table[1+First[Last[Select[T,Last[ # ]==i-1&]]],{i,1,n}]]; RamanujanPrimeList[54]) (* _Jonathan Sondow_, Aug 15 2009 *)
%t (FasterRamanujanPrimeList[n_] := With[{T=Table[{k,PrimePi[k]-PrimePi[k/2]}, {k,Prime[3*n]}]}, Table[1+First[Last[Select[T,Last[ # ]==i-1&]]],{i,1,n}]]; FasterRamanujanPrimeList[54])
%t nn=1000; R=Table[0,{nn}]; s=0; Do[If[PrimeQ[k], s++]; If[PrimeQ[k/2], s--]; If[s<nn, R[[s+1]]=k], {k,Prime[3*nn]}]; R=R+1 (* _T. D. Noe_, Nov 15 2010 *)
%o (Perl) use ntheory ":all"; my $r = ramanujan_primes(1000); say "[@$r]"; # _Dana Jacobsen_, Sep 06 2015
%o (PARI) ramanujan_prime_list(n) = {my(L=vector(n), s=0, k=1); for(k=1, prime(3*n)-1, if(isprime(k), s++); if(k%2==0 && isprime(k/2), s--); if(s<n, L[s+1] = k+1)); L} \\ _Satish Bysany_, Mar 02 2017
%Y Cf. A006992 (Bertrand primes), A056171 (pi(n) - pi(n/2)).
%Y Cf. A000720, A007053, A014085, A060715, A084139, A084140, A143223, A143224, A143225, A143226, A143227, A080360, A080359, A164368, A164288, A164554, A164333, A164294, A164371, A190303.
%Y Cf. A162996 (Round(kn * (log(kn)+1)), with k = 2.216 as an approximation of R_n = n-th Ramanujan Prime.
%Y Cf. A163160 (Round(kn * (log(kn)+1)) - R_n, where k = 2.216 and R_n = n-th Ramanujan prime).
%Y Cf. A178127 (Lesser of twin Ramanujan primes), A178128 (Lesser of twin primes if it is a Ramanujan prime).
%Y Cf. A181671 (number of Ramanujan primes less than 10^n).
%Y Cf. A174635 (non-Ramanujan primes), A174602, A174641 (runs of Ramanujan and non-Ramanujan primes).
%Y Cf. A189993, A189994 (lengths of longest runs).
%Y Cf. A190124 (constant of summation: 1/a(n)^2).
%Y Cf. A192820 (2- or derived Ramanujan primes R'_n), A192821, A192822, A192823, A192824, A225907.
%Y Cf. A193761 (0.25-Ramanujan primes), A193880 (0.75-Ramanujan primes).
%Y Cf. A190413, A190414, A212493, A212541, A233739, A233822, A277718, A277719, A164952, A290394, A291465.
%Y Cf. A185004 - A185007 ("modular" Ramanujan primes).
%Y Not to be confused with the Ramanujan numbers or Ramanujan tau function, A000594.
%K nonn,nice
%O 1,1
%A _Jonathan Sondow_, Feb 27 2005
|
