# How to prove the impossibility of an equality with floor functions

Given that $$r, 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

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

• 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. Jul 5 '20 at 9:17
• 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 ... Jul 5 '20 at 9:24
• 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. Jul 5 '20 at 16:57
• Do you mean en.wikipedia.org/wiki/Bertrand%27s_postulate ? Jul 5 '20 at 17:10
• 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. Jul 6 '20 at 13:41

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$$
• That seems like a good approach. Thanks. But don't you get $2n-1$ on the right at the end there? Jul 5 '20 at 21:16