# How can I prove this inequality regarding the prime numbers?

The inequality in question is: $$\sum_{p|2n} (\lfloor {n \over p} \rfloor - 1)-\sum_{p_1p_2|2n\;p_1>p_2} \lfloor {n \over p_1p_2} \rfloor + \sum_{p_1p_2p_3|2n\;p_1>p_2>p_3} \lfloor {n \over p_1p_2p_3} \rfloor - \cdots + 1 > n - \pi(2n-2)$$ Where $$\pi$$ is the prime-counting function, and for $$n$$ arbitrarily large. Sorry to post this without context, but even if I showed you the context, it probably wouldn't be of much use to solving it.

So, if this is held to be true for all $$n$$ that are arbitrarily large, how to prove so?

EDIT: It seems that for when $$n$$ is a prime number, this inequality tends to be false, but, I'm only interested in the cases where $$n$$ is not prime. So, let me rephrase my question: How can we prove this inequality, for all composite values of $$n$$ that are arbitrarily large?

• looks like goldbach, sundaram or Bertrand's postulate to me. – user645636 Jan 22 '20 at 17:30
• The first two sums look different from each other (that '$-1$' term), so I'm not sure what's supposed to be in the ellipsis. (Also, in that second sum: what about non-squarefree $n$? Is the intention to ignore any primes $p$ with $p^2\mid n$, or could that just be $\frac12\sum_{p_1, p_2\mid 2n}\lfloor n/(p_1p_2)\rfloor$?) – Steven Stadnicki Jan 22 '20 at 20:45

## 2 Answers

It should be easily enough falsifiable in the case where $$n=pq$$ with $$p,q\to\infty$$ and $$p/q\to1$$ as well: The left hand side is $$\left(\frac1p+\frac1q+\frac12\right)n-3-\left(\frac1{2p}+\frac1{2q}+\frac1{pq}\right)n$$ $$=\left(\frac1{2p}+\frac1{2q}+\frac12\right)n+O(1)$$ $$\approx n\left(\frac12+\frac1{\sqrt{n}}\right)$$ whereas the right hand side is $$n-\frac{2n}{\ln(2n)}+o(n/\ln n)\approx n\left(1-\frac2{\ln(2n)}\right)$$. So all that should be needed here is to choose $$n$$ large enough that the multiplier of $$n$$ on the LHS of your equation (i.e. $$\left(\frac12+\frac1{\sqrt{n}}\right)$$) is $$\lt\frac23$$, say, and so that the multiplier of $$n$$ on the RHS of your equation (i.e., $$\left(1-\frac2{\ln(2n)}\right)$$) is $$\gt\frac45$$.

For instance, suppose we take $$n=197\cdot 199 = 39203$$. Then the left hand side is $$(197-1+199-1+19601-1)-(98+99+1)+1$$ $$=19797$$, but the RHS is $$39203-\pi(78404) = 39203-7695 = 31508$$.

• @Tots (Also, given the form of the terms and the asymptotics, are you sure you didn't mean for the LHS to be e.g. $\sum_{p\mid2n}(\lfloor\frac{2n}p\rfloor-1)-\sum\ldots$? That one would be asymptotically 'close' (i.e., both sides should be $n+o(n)$ ) and so a little more interesting...) – Steven Stadnicki Jan 23 '20 at 1:49

Let $$f(n)=\sum_{j\ge 0, p_1\ldots p_j |2n, p_i >p_{i+1}} (-1)^j \lfloor \frac{n}{p_1\ldots p_j}\rfloor$$ $$= \sum_{d | 2n}\mu(d) \lfloor n/d \rfloor=\sum_{m \le n} \sum_{d | \gcd(m,2n)} \mu(d)=\sum_{m\le n, \gcd(m,2n)=1} 1$$ If $$n$$ is odd and $$\gcd(m,n)=1,m\le n$$ then one of $$m,n-m$$ is odd and coprime with $$2n$$, thus $$f(n)=\phi(n)/2$$. If $$n$$ is even then $$f(n)=\phi(n)$$.

And your sum is

$$-\sum_{p | 2n} 1 +(n-f(n))+1= n+1-f(n)-\sum_{p | 2n} 1$$ Thus your claim is that $$\pi(2n-2) \ge f(n)+\sum_{p | 2n} 1$$ which is obviously false for $$n$$ prime large enough.