Let $\pi(x)$ denotes the number of primes less than or equal to $x$. Also suppose that for some fixed $N$ we have $\pi(x+y)\ge\pi(x)+\pi(y)$. The problem is,

Show that the equality in the above inequality cannot hold for all $x,y>3$ and $x+y\le N$ where $x$ and $y$ are both positive integers.

My attempt

Suppose that there exists some $x_0$ and $y_0$ such that we have $$\pi(x_0)+\pi(y_0)=\pi(x_0+y_0)$$ Now if $x_0+y_0$ is composite then $\pi(x_0+y_0)=\pi(x_0+y_0-1)$. Now note that none of $x_0$ and $y_0$ can be prime because then we will have a contradiction. So the essence of all this is that if $x_0+y_0$ is composite then we also have a solution of the equation $$\pi(x+y-1)=\pi(x’)+\pi(y’)$$ such that $x’+y’=x+y-1$.

But I cannot solve the case when $x_0+y_0$ is a prime. Can anyone help me?


After going through the answer below, I think that I should elaborate once more the problem. What it says in disguise (so far I have understood) is the following,

Prove that if $p$ be an odd prime then there doesn't exist any solution to the equation, $$\pi(p-1)=\pi(x)+\pi(p-1-x)$$ for any integer $x$ where $p-x$ is a composite number.

Hope that this clarifies the problem more. If there is any problem (e.g., vagueness) still remaining, please let me know.

  • 1
    $\begingroup$ What do you mean when you say "for some fixed $N$ we have" a claim that doesn't mention the letter $N$ at all? $\endgroup$ – Henning Makholm May 23 '15 at 14:23
  • $\begingroup$ Probably it means that for some particular $N$ and $x$ there is a solution to the equality. $\endgroup$ – user 170039 May 25 '15 at 5:01

The following solution works for all $N \geq 9$.

Let $y=5$ and $x=N-5$. Then we should have $$\pi(N) \geq \pi(N-5) + \pi(5) = \pi(N-5) + 3$$

Hence, at least three of $N-4$, $N-3$, $N-2$, $N-1$, and $N$ must prime. That is not possible unless $N-4=2$ or $N-4=3$, in which case we have $N \leq 7$. Contradiction.

Note: We have $N \geq 9$ so that $x=N-5 \geq 4$.

Further, since $x,y > 3$, we have $x+y=N \geq 8$. So we only have $x=y=4$ in the case $N=8$, and your statement isn't even true, because we have $$\pi(8) = 4= 2\cdot 2 = 2\cdot \pi(4)$$

  • $\begingroup$ So, it implies that if we assume $\pi(x_0)+\pi(y_0)=\pi(x_0+y_0)$ holds for some $x_0,y_0$ where $x_0+y_0$ is a prime, then we can apply induction to reduce the statement to obtain a contradiction in the manner you said, right? To elaborate suppose there exists solution of the equation $\pi(x')+\pi(y')=\pi(x+y)$ with $x'+y'=x+y$ then we assume that there exists solution of the equation $\pi(x')+\pi(y')=\pi(x+y-r)$ where $x'+y'=x+y-r$. Then to prove the existence of the solution of $\pi(x')+\pi(y')=\pi(x+y-r-1)$ we apply your argument and eventually reach a contradiction. Is the process right? $\endgroup$ – Falling Snow May 24 '15 at 5:58
  • $\begingroup$ Also just one more question, the assumption is that for some $x_0$ and $y_0$ we have $\pi(x_0+y_0)=\pi(x_0)+\pi(y_0)$ with $x_0$ and $y_0$ fixed. How do you use this statement explicitly? $\endgroup$ – Falling Snow May 24 '15 at 6:05
  • $\begingroup$ No, I didn't use your attempt. I just showed, by providing counterexample, that it isn't even possible that for all $x,y$ to have this inequality. Maybe I misunderstood the problem? It is vaguely formulated. $\endgroup$ – wythagoras May 24 '15 at 6:29
  • $\begingroup$ Please see the added part. $\endgroup$ – Falling Snow May 24 '15 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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