0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ looks like goldbach, sundaram or Bertrand's postulate to me. $\endgroup$ – user645636 Jan 22 '20 at 17:30
  • 1
    $\begingroup$ 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$?) $\endgroup$ – Steven Stadnicki Jan 22 '20 at 20:45
0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ @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...) $\endgroup$ – Steven Stadnicki Jan 23 '20 at 1:49
0
$\begingroup$

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.

$\endgroup$

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.