How to prove the impossibility of an equality with floor functions

99 Views Asked by At

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

1

There are 1 best solutions below

8
On

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