0
$\begingroup$

Given that $r<n$, is it possible to prove that the following equality is impossible for $n>7$ ? (both inequalities are strict here). Some other minimal $n$ would be okay as well. I know it holds for $n=7$ and $r=3$

I am fairly sure that the left side has to be bigger than the right side for big enough $n$, but am not sure how to strictly show this.

$$ 2\cdot\sum_{i=1}^{\infty}\left \lfloor{\frac{n}{2^i}}\right \rfloor = \sum_{i=1}^{\infty}\left \lfloor{\frac{n}{2^i} + \frac{r}{2^i}}\right \rfloor $$

If it helps, there are a few more constraints that can be added to $n$ and $r$:

$n$ has to be prime

If $p$ is the next prime number after $n$ then $n+r<p$

New idea: as per my comments below, substituting $r=n-3$ i think this reduces to proving the following:

$$\sum_{i=1}^{\infty}\left \lfloor{\frac{n}{2^i}}\right \rfloor > n-1$$

Which seems like it should be easier to prove (unless i made an error somewhere)

New update: Testing shows that using $r=n-3$ is not strict enough, so my derived inequality is pointless (I'll leave it up anyway for now).

Testing using $n+r=p-1$ shows equality at $n=7$ as I mentioned and then the left side starts to run away from the right side rather fast. So it seems using this limitation on $r$ is essential. Though I have no idea how to do that.

Of possible interest/help: I ran a few simulations comparing $r$ to $n$ to see where the left side was finally equal to or smaller than the right side. The gap does grow, but very, very slowly, so that by prime numbers close to 10 000 you don't see equality until $r=n-14$.

$\endgroup$
10
  • $\begingroup$ May be, will be helpful, that for $\forall n, r$ there $\exists K$ for $i>K$ remainder of series will be $0$, so you really have finite sums. $\endgroup$
    – zkutch
    Jul 5 '20 at 9:17
  • $\begingroup$ Thanks, but I knew that one already. Those values will be different for $n$ and $r$ which caused me some issues going down that route. It's not the infinities I find difficult, it's dealing with the sum of floors and floor of sums in the wrong direction. It would be easier to show the right side bigger if that were true ... $\endgroup$
    – David Taub
    Jul 5 '20 at 9:24
  • $\begingroup$ I am pretty sure using Bertrand's postulate (again) that the maximum value for $r$ is $n-3$. So maybe it's possible to substitute $n-3$ for r and show that for bigger n this fails. It looks close, but I have trouble figuring out how to deal with a factor of 2 outside the floor on the left and inside the floor on the right. $\endgroup$
    – David Taub
    Jul 5 '20 at 16:57
  • $\begingroup$ Do you mean en.wikipedia.org/wiki/Bertrand%27s_postulate ? $\endgroup$
    – zkutch
    Jul 5 '20 at 17:10
  • 1
    $\begingroup$ I ran a simulation and @David is right, this does not hold for $r=n-3$ at all. But it definitely seems to hold for $n+r<p$ for at least the first 500 primes I just checked. And the inequality grows steadily, so there is reason to believe it will continue to hold. So then this fact limiting $r$ has to be used somehow. $\endgroup$
    – David Taub
    Jul 6 '20 at 13:41
0
$\begingroup$

I write it here, because it's easy to edit and see: suppose $k$ is least for which $\frac{n}{2^k}>1$. Then we have $\left\lfloor{\frac{n}{2^k}} \right\rfloor \geqslant 1$. So $$\frac{n}{2^{k-1}}>2 \Rightarrow \left\lfloor{\frac{n}{2^{k-1}}} \right\rfloor \geqslant 2 $$ $$\frac{n}{2^{k-2}}>4 \Rightarrow \left\lfloor{\frac{n}{2^{k-2}}} \right\rfloor \geqslant 4$$ at last we obtain $$\frac{n}{2}>2^{k-1} \Rightarrow \left\lfloor{\frac{n}{2}} \right\rfloor \geqslant 2^{k-1} $$ so as we have $\frac{n}{2^{k+1}}<1$, then $k>\log_2n-1$ $$\sum_{i=1}^{\infty}\left \lfloor{\frac{n}{2^i}}\right \rfloor \geqslant 1+2+4+ \cdots +2^{k-1} = 1+2(2^k-1) >1+2(2^{\log_2n-1}-1)=\\=1+2\left(\frac{n}{2}-1 \right)=n-1$$

$\endgroup$
8
  • $\begingroup$ That seems like a good approach. Thanks. But don't you get $2n-1$ on the right at the end there? $\endgroup$
    – David Taub
    Jul 5 '20 at 21:16
  • $\begingroup$ Added one little step more. In which point do you have doubt? $\endgroup$
    – zkutch
    Jul 5 '20 at 22:00
  • $\begingroup$ It was late and I read the exponent wrong. I will sit and look at this later and see if I think it works. $\endgroup$
    – David Taub
    Jul 6 '20 at 7:43
  • $\begingroup$ As @DavidK showed above, there must be an error in how I derived this last inequality from the first if your proof holds. So back to step one again. $\endgroup$
    – David Taub
    Jul 6 '20 at 10:22
  • $\begingroup$ @David Taub. Understand. Hope he have mistake and you not, but let me do not delete written above as it may be will be helpful in feature. Delete is easy, typed second time same terrible. Now I am on online exam and when find free time shall give one try more from scratch. $\endgroup$
    – zkutch
    Jul 6 '20 at 11:13

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.