# A valid floor function trick?

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.

• Consider the points of discontinuity. – robjohn Dec 22 '15 at 10:14

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

• A very nice answer, but the intutionist in me might accept a direct proof :) – Lehs Dec 22 '15 at 9:33
• Haha, I get what you're saying, but I like to think proof by contradiction is pretty direct, especially when it only takes a few lines ;) – Eric S. Dec 22 '15 at 9:38
• Does this handle the (hypothetical) case where $\left\lfloor\frac{\left\lfloor\frac{x}{m}\right\rfloor}{n}\right\rfloor$ and $\left\lfloor\frac{x}{mn}\right\rfloor$ are consecutive integers, so there is no $N$ between them? For instance, if $\frac{x}{mn} = N = \left\lfloor\frac{\left\lfloor\frac{x}{m}\right\rfloor}{n}\right\rfloor - 1$? – David Z Dec 22 '15 at 11:04
• @DavidZ, $\left\lfloor\frac{x}{mn}\right\rfloor=N\Rightarrow N\leq\frac{x}{mn}<N+1$ and $\left\lfloor\frac{\left\lfloor\frac{x}{m}\right\rfloor}{n}\right\rfloor=N+1\ \Rightarrow N+1\leq\frac{\left\lfloor\frac{x}{m}\right\rfloor}{n}<N+2$, such that $\frac{x}{mn}<N+1\leq\frac{\left\lfloor\frac{x}{m}\right\rfloor}{n}$, which is the first case. – Eric S. Dec 22 '15 at 11:10

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.

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$

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

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

• Nice try, but [1.6]<>[2.4] – Lehs Dec 22 '15 at 9:11
• The statement "[x] = [y] if and only if |x-y| < 1" is not correct. If $x = 1.6$ and $y = 2.4$, then $|x-y| < 1$ but $[x] \neq [y]$. – JimmyK4542 Dec 22 '15 at 9:13
• |2.4-1.6|=|0.8|<1, but [1.6]=1 and [2.4]=2 – Lehs Dec 22 '15 at 9:14
• The statement "If |x-y| < 1 (x > y) then [x] = [y]" is also incorrect. If $x = 2.4$ and $y = 1.6$, then $|x-y| < 1$ and $x > y$ but $[x] \neq [y]$. – JimmyK4542 Dec 22 '15 at 9:38
• You should use ⌊⌋ in plain text. – Andreas Rejbrand Dec 22 '15 at 15:55