Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

How do we show that For $x,y \ge 0$ real numbers, there exists a constant C suchthat: $$\pi(x+y)-\pi(y) \le \frac{1}{3}x+C$$ Where $\pi(.)$ denotes thes prime counting function, is true?

the hint is to sieve n with $y< n \le x+y $:

$$\pi (x+y) \le 1+ \sum _{n \le x+y} 1+1-1 - \sum_{2|n}1 - \sum_{3|n}1 + \sum_{6|n}1 + \sum_{n\le x+y} 1 = $$ $$1+ \sum _{n \le x+y} 1+1-1 - \sum_{2|n}1 - \sum_{3|n}1 + \sum_{6|n}1 + [x+y]$$

because: $1\le n = dm \le x+y \Leftrightarrow \frac{1}{d}\le m \le \frac{x+y}{y} $

so: $$\sum_{n\le x+y , d|n}1 = [\frac{x+y}{d}]$$

then that gives: $$\pi (x+y) < 1+ [x+y] - [\frac{x+y}{2}] - [\frac{x+y}{3}] + [\frac{x+y}{6}]$$

so that will give: $\pi (x+y) < \frac{x+y}{3} + 3$ but also we get : $\pi(y) < \frac{y}{3} + 3$ so for any constant $C\ge 0$ it will surely hold that:

$$\pi(x+y) - \pi(y) < \frac{x}{3} \le \frac{x}{3} + C$$

Is this correct?

share|cite|improve this question
There is $ \leq 1/3 \pi(x)$ in the title, but $\leq 1/3 x$ in the post. – dtldarek Mar 14 '12 at 23:15
Thanks for the correction dtldarek. – VVV Mar 14 '12 at 23:18
Hint: Which numbers modulo $6$ can be prime? – TMM Mar 14 '12 at 23:22
What if you forget about the $C$ for a moment and bring $\Delta y$ to the LHS. With $\Delta y \to 0$ you get: $$ \lim_{\Delta y\to 0} \frac{\pi(y+\Delta y)-\pi(y)}{\Delta y}=\pi(y)'\le 1/3. $$ Now use $\pi(y)\approx \frac{y}{\log y}$ and therefore $\pi(y)'\approx \frac{\log y-1}{(\log y)^2}=\frac{1}{\log y}-\frac{1}{(\log y)^2}$ which has a global maximum of $1/4$ at $y=e^2$. See here. – draks ... Mar 15 '12 at 14:31
Thank you. The prime number theorem wasnt proven yet, so the only thing that comes in question is the sieve of eratosthenes (as TMM suggests, sieving n numbers in the interval of $y<n\le x+y$ but it looks like I did it wrong (I believe). – VVV Mar 15 '12 at 15:53

Hint: Which numbers modulo $6$ can be prime? (Certainly not those divisible by $2$ or $3\ldots$)

So on an interval of width $x$ from $y$ to $y + x$, how many primes ($\pi(y+x) - \pi(y)$) do we expect at most on this interval?

share|cite|improve this answer
I put my comment to your answer in the edit of my question, thanks. – VVV Mar 15 '12 at 10:33

You are asking us to show that your inequality holds for any $x, y \ge 0$ and for any constant $C$, which is obviously false. Perhaps this is what you mean:

Show that there exists a constant $C$ such that for any real numbers $x, y \ge 0$, $\pi(x+y)-\pi(y) \le \frac{1}{3}x+C$.

share|cite|improve this answer
Yea, exactly TonyK. – VVV Mar 15 '12 at 22:52
@VVV: Still not right, I'm afraid: now your statement is vacuously true. I suppose that's an improvement! – TonyK Mar 16 '12 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.