login
Smallest prime > n^2.
(Formerly M1389)
32

%I M1389 #75 Oct 29 2023 21:24:12

%S 2,5,11,17,29,37,53,67,83,101,127,149,173,197,227,257,293,331,367,401,

%T 443,487,541,577,631,677,733,787,853,907,967,1031,1091,1163,1229,1297,

%U 1373,1447,1523,1601,1693,1777,1861,1949,2027,2129,2213,2309,2411,2503

%N Smallest prime > n^2.

%C Suggested by Legendre's conjecture (still open) that there is always a prime between n^2 and (n+1)^2.

%C Legendre's conjecture is equivalent to a(n) < (n+1)^2. - _Jean-Christophe Hervé_, Oct 26 2013

%C From _Jaroslav Krizek_, Apr 02 2016: (Start)

%C Conjectures:

%C 1) There is always a prime p between n^2 and n^2+n (verified up to 13*10^6).

%C 2) a(n) is the smallest prime p such that n^2 < p < n^2+n; a(n) < n^2+n.

%C 3) For all numbers k >= 1 there is the smallest number m > 2*(k+1) such that for all numbers n >= m there is always a prime p between n^2 and n^2 + n - 2k. Sequence of numbers m for k >= 1: 6, 8, 12, 13, 14, 24, 24, 24, 30, 30, 30, 31, 33, 35, 43, ...; lim_{k->oo} m/2k = 1. Example: k=2; for all numbers n >= 8 there is always a prime p between n^2 and n^2 + n - 4. (End)

%D Archimedeans Problems Drive, Eureka, 24 (1961), 20.

%D J. R. Goldman, The Queen of Mathematics, 1998, p. 82.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 19.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Jean-Christophe Hervé, <a href="/A007491/b007491.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LandausProblems.html">Landau's Problem</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LegendresConjecture.html">Legendre's Conjecture</a>.

%F a(n) = A007918(A000290(n)). - _Reinhard Zumkeller_, Jun 07 2015

%p [seq(nextprime(i^2), i=1..100)];

%t NextPrime[Range[60]^2] (* _Harvey P. Dale_, Mar 24 2011 *)

%o (PARI) vector(100,i,nextprime(i^2))

%o (Magma) [NextPrime(n^2): n in [1..50]]; // _Vincenzo Librandi_, Apr 30 2015

%o (Haskell)

%o a007491 = a007918 . a000290 -- _Reinhard Zumkeller_, Jun 07 2015

%o (Python)

%o from sympy import nextprime

%o def a(n): return nextprime(n**2)

%o print([a(n) for n in range(1, 51)]) # _Michael S. Branicky_, Jan 13 2023

%Y Cf. A053000, A053001, A014085, A144831.

%Y Cf. A007918, A000290.

%K nonn,easy,nice

%O 1,1

%A _N. J. A. Sloane_, _Robert G. Wilson v_, _R. K. Guy_

%E More terms from _Labos Elemer_, Nov 17 2000

%E Definition modified by _Jean-Christophe Hervé_, Oct 26 2013