A014085 -id:A014085 - cp's OEIS frontend

A110835 Smallest m > 0 such that there are no primes between nm and n(m+1) inclusive.

8, 4, 8, 6, 18, 15, 17, 25, 13, 20, 29, 44, 87, 81, 35, 83, 79, 74, 70, 67, 118, 330, 58, 223, 172, 229, 179, 471, 292, 360, 506, 367, 586, 577, 645, 545, 424, 743, 503, 637, 766, 467, 937, 579, 698, 683, 542, 1443, 641, 628, 616, 604, 2026, 1661, 571, 1834, 551

Offset: 1

Franklin T. Adams-Watters, Sep 16 2005

nonn

Suggested by Legendre's conjecture (still open) that there is always a prime between n^2 and (n+1)^2. If a(n) >= n+2, it implies that there is always a prime between n^2 and n*(n+1) and another between n*(n+1) and (n+1)^2. Note that the "inclusive" condition for the range affects only n=1. The value of a(1) would be 1 or 3 if this condition were taken to be exclusive or semi-inclusive, respectively. This is Oppermann's conjecture.

Sierpinski's conjecture (1958) is precisely that a(n) >= n for all n. - Charles R Greathouse IV, Oct 09 2010

			a(2)=4 because the primes 3, 5 and 7 are in range 2m to 2m+2 for m from 1 to 3, but 8, 9 and 10 are all composite.

Charles R Greathouse IV, Table of n, a(n) for n = 1..599
A. Schinzel and W. Sierpinski, "Sur certaines hypothèses concernant les nombres premiers", Acta Arithmetica 4 (1958), pp. 185-208.
Wikipedia, Oppermann's conjecture

See A014085 for primes between squares.

A228775 is an alternate version.

a[n_]:=Module[{m=1},Until[NextPrime[n*m-1]>n*(m+1),m++];m];Array[a,57] (* James C. McMahon, Aug 10 2025 *)

a(n)=local(m);m=1;while(nextprime(n*m)<=n*(m+1),m=m+1);m

a(n)=for(m=if(n>101,12118,4),oo, if(nextprime(n*m)>n*(m+1), return(m))) \\ Charles R Greathouse IV, Mar 04 2025

from sympy import nextprime
def a(n):
    m = 1
    while nextprime(n*m-1) <= n*(m+1): m += 1
    return m
print([a(n) for n in range(1, 58)]) # Michael S. Branicky, Aug 04 2021

A143898 Number of primes between n^K and (n+1)^K, where K = log(1151)/log(95).

Original entry on oeis.org

1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 3, 1, 1, 1, 3, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 3, 2, 1, 2, 3, 2, 1, 3, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 3, 3, 1, 4, 2, 3, 2, 1, 3, 2, 3, 2, 2, 2, 4, 1, 4, 2, 2, 2, 2, 3, 2, 3, 2, 4, 3, 2, 3, 3, 3, 3, 1, 3, 3, 2, 3, 3, 2, 3, 5, 3, 1, 1

Offset: 1

T. D. Noe, Sep 04 2008, Sep 26 2009, Oct 21 2009

This value of K is conjectured to be the least possible such that there is at least one prime in the range n^K to (n+1)^K for n > 0. This value of K was found using exact interval arithmetic. For each n <= 110 and for each prime p in the range n to n^1.7, we computed an interval k(n,p) such that p is between n^k(n,p) and (n+1)^k(n,p). The intersection of all these intervals produces a list of intervals. The least value in those intervals is K, which is log(1151)/log(95). We computed 10^5 terms of this sequence to give us confidence that a(n) > 0 for all n.
More details about the algorithm: The n^1.7 limit was chosen because we were fairly certain that K would be less than 1.7. Let k(n) be the union of the intervals k(n,p) for p < n^1.7. Then k(n) is the set of exponents e such that the range n^e to (n+1)^e always contains a prime. Let k be the intersection of all the k(n) intervals for n up to N. Then k is the set of exponents e such that there is always a prime in the range n^e to (n+1)^e for n <= N. The number K is the least number in the set k. It appears that as N becomes larger, the set k converges. See A143935. - T. D. Noe, Sep 08 2008
The constant log(1151)/log(95) is A194362. - John W. Nicholson, Nov 25 2013
1151 counts as a qualifying prime towards both a(94)=1 and a(95)=3, in accordance with use of closed ranges. If prime p were counted only when n^K < p <= (n+1)^K, then term 95 would be 2. If prime p were counted only when n^K <= p < (n+1)^K, then term 94 would be 0. The conjecture in the author's comment implies K is the greatest real value such that for all e <= K there exists n > 0 with no prime p satisfying n^e <= p < (n+1)^e. - Peter Munn, Mar 02 2017
The author's description of the calculation of K implies that K is not an isolated qualifying value; equivalently that K is also the least real value for which there is a positive epsilon such that for all exponent e, K <= e <= K+epsilon and integer n > 0 there is a prime p satisfying n^e <= p <= (n+1)^e. This is a necessary precondition for my Mar 02 2017 deduction from the author's conjecture. - Peter Munn, Aug 21 2019

T. D. Noe, Table of n, a(n) for n = 1..10000

A014085 (number of primes between n^2 and (n+1)^2), both A134034 and A143935 use a larger K.

k= 1.547777108714197624815033; Table[Length[Select[Range[Ceiling[n^k],Floor[(n+1)^k]], PrimeQ]], {n,150}] (* T. D. Noe, Sep 08 2008 *)

Removed some comments which changed the definition of this sequence. - N. J. A. Sloane, Oct 21 2009

A145445 a(n) = the smallest square > n-th prime.

Original entry on oeis.org

4, 4, 9, 9, 16, 16, 25, 25, 25, 36, 36, 49, 49, 49, 49, 64, 64, 64, 81, 81, 81, 81, 100, 100, 100, 121, 121, 121, 121, 121, 144, 144, 144, 144, 169, 169, 169, 169, 169, 196, 196, 196, 196, 196, 225, 225, 225, 225, 256, 256, 256, 256, 256, 256, 289, 289, 289, 289

Offset: 1

Zak Seidov, Oct 10 2008

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A104103.

Cf. A000040, A000290, A014085 (run lengths), A245508.

a145445 n = a145445_list !! (n-1)
a145445_list = f a000040_list $ drop 2 a000290_list where
   f ps'@ (p:ps) xs'@(x:xs) = if p < x then x : f ps xs' else f ps' xs
-- Reinhard Zumkeller, Jul 25 2014

Table[Ceiling[Prime[n]^(1/2)]^2,{n,100}]

from sympy import prime, integer_nthroot
def a(n): return (integer_nthroot(prime(n), 2)[0]+1)**2
print([a(n) for n in range(1, 59)]) # Michael S. Branicky, Apr 04 2021

a(n) = A104103(n)^2.

A065382 Number of primes between n(n+1)/2 (exclusive) and (n+1)(n+2)/2 (inclusive).

Original entry on oeis.org

2, 1, 1, 2, 2, 1, 2, 3, 2, 2, 3, 3, 3, 3, 2, 4, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 6, 4, 5, 3, 6, 6, 7, 5, 5, 6, 4, 8, 5, 6, 6, 8, 6, 8, 5, 7, 5, 11, 4, 6, 9, 7, 8, 9, 8, 7, 7, 9, 7, 8, 7, 12, 5, 9, 9, 11, 9, 7, 7, 12, 10, 10, 9, 9, 9, 6, 11, 10, 11, 9, 12, 11, 12, 9, 10, 11, 12, 10, 13, 9, 11, 10

Offset: 1

Reinhard Zumkeller, Nov 05 2001

nonn

Inspired by the weaker Legendre conjecture that there should be at least one prime between n^2 and (n+1)^2.

			a(10) = 2 because between 10*(10+1)/2=55 and (10+1)*(10+2)/2=66 there are 2 primes: 59, 61.

T. D. Noe, Table of n, a(n) for n = 1..10000

A000217, A014085, A065383, A065384.

Essentially the same as A066888 and A090970.

Table[ PrimePi[n(n + 1)/2] - PrimePi[n(n - 1)/2], {n, 2, 96}]

from sympy import primerange
def A065382(n): return sum(1 for p in primerange((n*(n+1)>>1)+1,((n+2)*(n+1)>>1)+1)) # Chai Wah Wu, May 22 2025

Definition improved by Robert G. Wilson v, Apr 22 2003

A068435 Consecutive prime powers without a prime between them.

Original entry on oeis.org

8, 9, 25, 27, 121, 125, 2187, 2197, 32761, 32768

Offset: 1

Jon Perry, Mar 09 2002

From David A. Corneth, Aug 24 2019: (Start)
Only 5 pairs are known up to 4*10^18. Legendre's conjecture states that there is a prime number between n^2 and (n + 1)^2 for every positive integer n. The conjecture has been verified up to n = 2*10^9. So to that bound we only have to check for two prime powers where at least one has an exponent of at least 3. That has been done to prime powers <= 10^22.
If there is another pair besides the first five listed with both numbers <= 10^22 then Legendre's conjecture is false.
Proof: If there is another such pair with both numbers <= 10^22 then it must be of the form [p^2, q^2] where p is a prime and q is the least prime larger than p. Then q - p >= 2 (as p != 2). So there is no prime between p^2 and q^2 and hence there is no prime between p^2 and (p+1)^2. This is a counterexample to Legendre's conjecture. (End)

			8 = 2^3, 9 = 3^2, there is no prime between 8 and 9.
25 = 5^2, 27 = 3^3, there is no prime between 25 and 27.

David A. Corneth, PARI program to search for pairs where not both numbers are squares of primes
Wikipedia, Legendre's conjecture

Cf. A014085, A025475, A060846, A067871, A068315, A246547, A366835.

Cf. A116086 and A116455 (for perfect powers, but not necessarily prime powers).

With[{upto=33000},Select[Partition[Select[Range[upto],PrimePowerQ],2,1],NoneTrue[#,PrimeQ]&]] (* Paolo Xausa, Oct 29 2023 *)

ispp(x) = !isprime(x) && isprimepower(x);
lista(nn=50000) = {my(prec = 0); for (i=1, nn, if (ispp(i), if (! prec, prec = i, if (primepi(i) == primepi(prec), print1(prec, ", ", i, ", ")); prec = i;);););} \\ Michel Marcus, Aug 24 2019

A108314 Sum of primes p with n^2 < p < (n+1)^2.

Original entry on oeis.org

5, 12, 24, 59, 60, 168, 173, 290, 269, 533, 534, 787, 917, 830, 1420, 1901, 1541, 2076, 2288, 2953, 3219, 3533, 3348, 5413, 5208, 4907, 6026, 7343, 6960, 7444, 9948, 9483, 11166, 10749, 12624, 11903, 12713, 17724, 17155, 19590, 18975, 16249, 22702, 21859, 26943

Offset: 1

Giovanni Teofilatto, Jun 30 2005

			a(2)=12 because between 4 and 9 there are two primes (5 and 7) with sum equal to 12.

Michael S. Branicky, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)

Cf. A014085, A158528, A293697.

a:=proc(n) local s,j: s:=0: for j from n^2 to (n+1)^2 do if isprime(j)=true then s:=s+j else s:=s: fi od end: seq(a(n),n=1..50); # Emeric Deutsch, Jul 01 2005

f[n_] := Plus @@ Prime[ Range[PrimePi[n^2] + 1, PrimePi[(n + 1)^2]]]; Table[ f[n], {n, 44}] (* Robert G. Wilson v, Jul 01 2005 *)

A108314(n)={r=0;forprime(i=n^2+1,(n+1)^2-1,r=r+i);r} \\ Michael B. Porter, Oct 14 2009

from sympy import sieve
def a(n): return sum(p for p in sieve.primerange(n**2, (n+1)**2))
print([a(n) for n in range(1, 46)]) # Michael S. Branicky, Jul 29 2021

Edited, corrected and extended by Emeric Deutsch, Robert G. Wilson v and Rick L. Shepherd, Jul 01 2005

A161621 Numerator of (b(n+1) - b(n))/(b(n+2) - b(n)), where b(n) = A038107(n) is the number of primes up to n^2.

Original entry on oeis.org

1, 1, 2, 3, 1, 4, 3, 4, 3, 5, 4, 1, 5, 2, 6, 7, 5, 1, 6, 1, 1, 7, 2, 9, 8, 7, 8, 9, 1, 4, 10, 9, 10, 9, 10, 1, 3, 12, 11, 12, 11, 3, 12, 11, 13, 10, 13, 3, 10, 11, 15, 4, 12, 13, 11, 12, 17, 13, 1, 16, 13, 17, 15, 7, 16, 1, 15, 17, 13, 7, 1, 15, 1, 17, 9, 11, 7, 18, 23, 13, 20, 19, 20, 17, 16

Offset: 1

Daniel Tisdale, Jun 14 2009

If the limit of R(n) exists as n->oo it is 1/2, but existence of the limit is conjectural. R(n) generalizes to R_k(n) by substituting PrimePi_k for PrimePi(n), where PrimePi_k(n) is the number of numbers with k prime factors (including repetitions) <= n. Convergence of {R(n)} to 1/2 implies Legendre's conjecture. For discussion of the order of the number of prime factors of a number n see reference [1], below. The PNT and reference [1] suggest but offer no proof that R_k(n)-> 1/2 as n -> oo. The corresponding sequence for near-primes would be {R_2(n)} = {1/3, 2/3, 1/2, ...}.

			R(3) = (PrimePi(4^2)-PrimePi(3^2)) / (PrimePi(5^2)-PrimePi(3^2)) = (PrimePi(16)-PrimePi(9)) / (PrimePi(25)-PrimePi(9)) = (6-4)/(9-4) = 2/5. Hence a(3) = 2. - _Klaus Brockhaus_, Jun 15 2009

S. Ramanujan, The Normal Number of Prime Factors of a Number n, reprinted at Chapter 35, Collected Papers (Hardy et al., ed), AMS Chelsea Publishing, 2000.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A014085

Cf. A161622 (denominators). - Klaus Brockhaus, Jun 15 2009

[ Numerator((#PrimesUpTo((n+1)^2)-a) / (#PrimesUpTo((n+2)^2)-a)) where a is #PrimesUpTo(n^2): n in [1..85] ]; // Klaus Brockhaus, Jun 15 2009

Numerator[(#[[2]]-#[[1]])/(#[[3]]-#[[1]])&/@Partition[PrimePi[ Range[ 90]^2],3,1]] (* Harvey P. Dale, Jan 06 2017 *)

a(1) inserted and extended beyond a(13) by Klaus Brockhaus, Jun 15 2009

Simplified title by John W. Nicholson, Dec 13 2013

A077767 Number of primes of form 4k+3 between n^2 and (n+1)^2.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 1, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 4, 5, 3, 4, 4, 4, 3, 5, 4, 4, 5, 5, 4, 4, 5, 5, 4, 8, 8, 5, 4, 6, 5, 6, 7, 5, 5, 7, 5, 7, 7, 7, 6, 8, 4, 5, 11, 5, 9, 8, 6, 11, 7, 7, 7, 7, 8, 10, 5, 12, 10, 5, 9, 10, 7, 13, 8, 8, 11, 5, 10, 9, 13, 9, 6, 9, 12, 7, 7, 11, 10, 9, 12, 11, 10, 10

Offset: 1

T. D. Noe, Nov 20 2002

nonn

Related to Legendre's conjecture that there is always a prime between two consecutive squares.

			a(8)=3 because primes 67, 71 and 79 are between squares 64 and 81

Seiichi Manyama, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)

Cf. A002145, A014085, A077766.

maxN=100; a=Table[0, {maxN}]; maxP=PrimePi[(maxN+1)^2]; For[i=1, i<=maxP, i++, p=Prime[i]; If[Mod[p, 4]==3, j=Floor[Sqrt[p]]; a[[j]]++ ]]; a
p3[{a_,b_}]:=Module[{p=Prime[Range[PrimePi[a]+1,PrimePi[b]]]},Count[p,?(Mod[#,4]==3&)]]; p3/@Partition[Range[100]^2,2,1] (* _Harvey P. Dale, Feb 20 2020 *)

A166363 Number of primes in the half-open interval (n(log(n))^2..(n+1)(log(n+1))^2].

Original entry on oeis.org

0, 2, 2, 1, 3, 1, 2, 3, 2, 2, 3, 2, 2, 4, 1, 2, 3, 3, 3, 3, 2, 2, 5, 2, 3, 4, 1, 3, 3, 3, 4, 3, 3, 3, 4, 3, 3, 4, 1, 3, 3, 5, 3, 4, 4, 3, 3, 3, 4, 3, 3, 4, 4, 4, 2, 3, 4, 3, 3, 4, 5, 3, 5, 4, 2, 3, 3, 6, 2, 4, 5, 3, 2, 2, 3, 6, 3, 6, 3, 4, 4, 6, 3, 4, 3, 4, 4, 4, 2, 3, 6, 3, 3, 2, 6, 5, 2, 6, 3, 5, 3, 2, 5, 4, 4

Offset: 1

Daniel Forgues, Oct 12 2009

nonn

The open-closed half-open intervals form a partition of the real line for x > 0, thus each prime appears in a unique interval.
The n-th interval length is ~ (log(n+1/2))^2 + 2*log(n+1/2) ~ (log(n))^2 as n goes to infinity.
The n-th interval prime density is ~ 1/[log(n+1/2)+2*log(log(n+1/2))] ~ 1/log(n) as n goes to infinity.
The expected number of primes in the n-th interval is ~ [(log(n+1/2))^2 + 2*log(n+1/2)] / [log(n+1/2)+2*log(log(n+1/2))] ~ log(n) as n goes to infinity.
For n = 1 there is no prime.
If it can be proved that each interval always contains at least one prime, this would constitute even shorter intervals than A166332(n), let alone A143898(n), as n gets large.
The Shanks Conjecture and the Cramer-Granville Conjecture tell us that the intervals of length (log(n))^2 are of very critical length (the constant M > 1 of the Cramer-Granville Conjecture definitely matters!). There seems to be some risk that one such interval does not contain a prime.
The Wolf Conjecture (which agrees better with numerical evidence) seems more in favor of each interval's containing at least one prime.
From Charles R Greathouse IV, May 13 2010: (Start)
Not all intervals > 1 contain primes!
a(n) = 0 for n = 1, 4977, 17512, 147127, 76082969 (and no others up to 10^8).
Higher values include 731197850, 2961721173, 2103052050563, 188781483769833, 1183136231564246 but this list is not exhaustive.
The intervals have length (log n)^2 + 2*log n + o(1). In the Cramer model, the probability that a given integer in the interval would be prime is approximately 1/(log n + 2*log log n). Tedious calculation gives the probability that a(n) = 0 in the Cramer model as 3C(log n)^2/n * (1 + o(1)) with C = exp(-5/2)/3. Thus under that model we would expect to find roughly C*(log N)^3 numbers n up to N with a(n) = 0. In fact, the numbers are not that common since the probabilities are not independent.
(End)
The similar sequence A345755 relies on intervals that are slightly more than twice as wide as those in the present sequence. A345755 does not include zero entries for n <= 2772, suggesting that the lengths of prime gaps may be bracketed by the two sequences. We conjecture that prime gaps may be larger than log(p)^2, but are not larger than log_2(p)^2. - Hal M. Switkay, Aug 29 2023

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Prime Gaps.
Eric Weisstein's World of Mathematics, Cramer-Granville Conjecture.
Eric Weisstein's World of Mathematics, Shanks Conjecture (and Wolf Conjecture.)

Cf. A166332, A000720, A111943, A143898, A134034, A143935, A144140 (primes between successive n^K, for different K), A014085 (primes between successive squares).

Cf. A182315, A345755.

a(n)=sum(k=ceil(n*log(n)^2),floor((n+1)*log(n+1)^2), isprime(k)) \\ Charles R Greathouse IV, Aug 21 2015

a(n) = pi((n+1)*(log(n+1))^2) - pi(n*(log(n))^2) since the intervals are half-open properly.

Edited by Daniel Forgues, Oct 18 2009 and Nov 01 2009

Edited by Charles R Greathouse IV, May 13 2010

A221056 Numbers k such that there is no square between prime(k) and prime(k+1).

Original entry on oeis.org

1, 3, 5, 7, 8, 10, 12, 13, 14, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 29, 31, 32, 33, 35, 36, 37, 38, 40, 41, 42, 43, 45, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60, 62, 63, 64, 65, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 84, 86

Offset: 1

Reinhard Zumkeller, Apr 15 2013

nonn

A061265(a(n)) = 0;

a(n) = A049084(A224363(n)); A000040(a(n)) = A224363(n).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Legendre's Conjecture
Wikipedia, Legendre's conjecture

Cf. A038107, A014085.

import Data.List (elemIndices)
a221056 n = a221056_list !! (n-1)
a221056_list = map (+ 1) $ elemIndices 0 a061265_list

Select[Range[86], Ceiling[Sqrt[Prime[#]]]^2 > Prime[# + 1] &] (* Zak Seidov, Apr 16 2013 *)

{for (n = 1, 86, ceil (sqrt (prime (n)))^2 > prime (n + 1) && print1 (n ","))} \\ Zak Seidov, Apr 16 2013

cp's OEIS Frontend

A110835 Smallest m > 0 such that there are no primes between n*m and n*(m+1) inclusive.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

A143898 Number of primes between n^K and (n+1)^K, where K = log(1151)/log(95).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A145445 a(n) = the smallest square > n-th prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

A065382 Number of primes between n(n+1)/2 (exclusive) and (n+1)(n+2)/2 (inclusive).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A068435 Consecutive prime powers without a prime between them.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A108314 Sum of primes p with n^2 < p < (n+1)^2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Extensions

A161621 Numerator of (b(n+1) - b(n))/(b(n+2) - b(n)), where b(n) = A038107(n) is the number of primes up to n^2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A110835 Smallest m > 0 such that there are no primes between nm and n(m+1) inclusive.

A166363 Number of primes in the half-open interval (n(log(n))^2..(n+1)(log(n+1))^2].