A valid floor function trick?

Question

Given $x\in\mathbb R_+$ and $m,n\in\mathbb Z_+$, is it true that $$\bigg\lfloor\frac{\lfloor \frac{x}{m}\rfloor}{n}\bigg\rfloor=\bigg\lfloor \frac{x}{mn}\bigg\rfloor?$$

---

Thanks for at least three different and convincing proofs! I'll use this result trying to code the prime counting formula from Wikipedia $(2)$:

Given $m$, select $y$ so that $\sqrt[3]{m}\le y\le\sqrt{m}$ and let $n=\pi(y)$. Then

$(1)\;$ $\pi(m)=\phi(m,n)+n-1-P_2(m,n)$, where

$(2)\;$ $\displaystyle \phi(m,n)=\phi(m,n-1)-\phi\Big(\frac{m}{p_n},n-1\Big)$, $\;\phi(m,0)=\lfloor{m}\rfloor$ and

$(3)\;$ $\displaystyle P_2(m,n)=\sum_{y<p\le\sqrt{m}} \Big(\pi\Big(\frac{m}{p}\Big)-\pi(p)+1\Big)$, $\;p$ is a prime.

Answer 1

Yes it is. Assume it is not, then there is an integer $N\in\mathbb{N}$ that lies between $\left\lfloor\frac{\left\lfloor\frac{x}{m}\right\rfloor}{n}\right\rfloor$ and $\left\lfloor\frac{x}{mn}\right\rfloor$. Possible cases:

• $$\frac{x}{mn}<N\leq\frac{\left\lfloor\frac{x}{m}\right\rfloor}{n} \implies \frac{x}{m}<nN\leq\left\lfloor\frac{x}{m}\right\rfloor,$$ which is a contradiction, since $\left\lfloor\frac{x}{m}\right\rfloor\leq\frac{x}{m}$.

• $$\frac{\left\lfloor\frac{x}{m}\right\rfloor}{n}<N\leq\frac{x}{mn} \implies \left\lfloor\frac{x}{m}\right\rfloor<nN\leq\frac{x}{m},$$ which is also a contradiction, since there cannot lie an integer between $\left\lfloor\frac{x}{m}\right\rfloor$ and $\frac{x}{m}$.

Answer 2

We know that if |x-y|<1 (x>y) then [x] = [y]

[x/m] - x/m <1 : [x/m]/n - x/mn = ([x/m] - x/m ) /n <1

So | [x/m] / n - x/ mn | <1 so your trick is correct

Answer 3

Let $\left\lfloor\dfrac{x}{mn}\right\rfloor = k \in \mathbb{Z}$. Then $k \le \dfrac{x}{mn} < k+1$. So, $kn \le \dfrac{x}{m} < (k+1)n$.

Since $\dfrac{x}{m} \ge kn$ and $kn$ is an integer, we have $\left\lfloor\dfrac{x}{m}\right\rfloor \ge kn$. Also, $\left\lfloor\dfrac{x}{m}\right\rfloor \le \dfrac{x}{m} < (k+1)n$.

Hence, $kn \le \left\lfloor\dfrac{x}{m}\right\rfloor < (k+1)n$, and thus, $k \le \dfrac{\left\lfloor\tfrac{x}{m}\right\rfloor}{n} < k+1$.

Therefore, $\left\lfloor \dfrac{\left\lfloor\tfrac{x}{m}\right\rfloor}{n} \right\rfloor = k = \left\lfloor\dfrac{x}{mn}\right\rfloor$, as desired.

Answer 4

Yes, using the fact that $b \cdot \lfloor \frac{a}{b} \rfloor = a - (a \space\text{mod}\space b$), we have

$n \cdot \lfloor \frac{x}{m \cdot n} \rfloor =$

$\frac{x}{m} - (\frac{x}{m} \space\text{mod}\space n) =$

$\lfloor \frac{x}{m} \rfloor + \{ \frac{x}{m} \} - ((\lfloor \frac{x}{m} \rfloor + \{ \frac{x}{m} \}) \space\text{mod}\space n) = $

$\lfloor \frac{x}{m} \rfloor - (\lfloor \frac{x}{m} \rfloor \space\text{mod}\space n) =$

$n \cdot \lfloor \frac{\lfloor \frac{x}{m} \rfloor}{n} \rfloor$

Answer 5

I post an answer built upon robjohns comment.

$$\bigg\lfloor\frac{\lfloor \frac{x}{m}\rfloor}{n}\bigg\rfloor=\bigg\lfloor \frac{x}{mn}\bigg\rfloor$$

Start with $x=0$. Then left side and right side are equal. When $x$ increase, the left side will increase with $1$ exactly when $\lfloor\frac{x}{m}\rfloor$ increase with $1$ and become a divider of $n$, that is, exactly when the right side increase with $1$.