MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

p[i] is the i-th prime. $\pi(x)$ is prime counting function.

Firstly, I think that this Prime gap inequality holds true,

$ p[i+1] - p[i] <= i $

Prove:for any i>0, we can always find distinct prime factors for {p[i], p[i]+1,...,p[i+1]}. For example, i=11, p[11]=31, p[12]=37, {31,32,33,34,35,36,37} have distinct prime factors {31,2,11,17,5,3,37}. Pigeonhole principle shows this simple inequality!

My question is the title,

Conjecture(Prime counting inequality) :

if $ i\lt j $, then $\pi(p[i]+i)-i<=\pi(p[j]+j)-j+1$

Edit: sorry, this conjecture is false! But another question is arising: if $ i\lt j $, what is the max value of $g(i,j) = (\pi(p[i]+i)-i) - (\pi(p[j]+j)-j) /; i\lt j$

I find g(i,j) may be 12. g(150065,150090)=12.

and more, what is the max value of h(i,j)=j-i /; $(\pi(p[i]+i)-i) > (\pi(p[j]+j)-j) $

share|cite|improve this question
Concerning your other conjecture, there will be places where primes collect and places where they are sparse. Based on your single data point, I am guessing g(i,j) can be potentially as large as log(j) times possibly an iterated log of j. I am having trouble reading your definition of h(i,j), so will not comment further on it. Gerhard "Ask Me About System Design" Paseman, 2011.08.04 – Gerhard Paseman Aug 5 '11 at 5:56
up vote 4 down vote accepted

I believe your inequality $p(i+1) \leq p(i) + i$ is true, but that there is no short and elementary proof. It follows from inspection and some known results on the length of gaps between primes, cf. Dusart or Harman.

Your titled inequality I believe fails for some $i$ with $j=i+2$. I don't have a specific value for $i$, but I suspect that there is a sequence such that your arguments to $\pi$ could fall into a large gap, especially when $p(i+2)= p(i)+6$. That is where I would start looking for counterexamples.

Gerhard "But It Looks Quite Plausible" Paseman, 2011.07.30

share|cite|improve this answer
you are right! Mathematica code: Table[pi[p[n] + n] - n, {n, 1, 100}] {1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 3, 3, 2, 3, 3, 4, 4, 4, 4, 3, 4, 4, \ 6, 5, 5, 4, 4, 4, 4, 6, 6, 6, 6, 7, 6, 7, 8, 7, 7, 6, 6,... my conjecture is false. – user8140 Jul 30 '11 at 7:08
Happens to the best of us. Fermat primes is one example. Don't let that stop you, let it guide you. Gerhard "Ask Me About System Design" Paseman, 2011.07.30 – Gerhard Paseman Jul 30 '11 at 7:14
Playing primes is just like playing chess with Zeus. – user8140 Jul 30 '11 at 7:22
t = Table[pi[p[n] + n] - n, {n, 1, 10000}]; ListPlot[{t}] – user8140 Jul 30 '11 at 8:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.