5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Consider the points of discontinuity. $\endgroup$ – robjohn Dec 22 '15 at 10:14
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ A very nice answer, but the intutionist in me might accept a direct proof :) $\endgroup$ – Lehs Dec 22 '15 at 9:33
  • 1
    $\begingroup$ 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 ;) $\endgroup$ – Eric S. Dec 22 '15 at 9:38
  • $\begingroup$ 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$? $\endgroup$ – David Z Dec 22 '15 at 11:04
  • $\begingroup$ @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. $\endgroup$ – Eric S. Dec 22 '15 at 11:10
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice try, but [1.6]<>[2.4] $\endgroup$ – Lehs Dec 22 '15 at 9:11
  • $\begingroup$ 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]$. $\endgroup$ – JimmyK4542 Dec 22 '15 at 9:13
  • $\begingroup$ |2.4-1.6|=|0.8|<1, but [1.6]=1 and [2.4]=2 $\endgroup$ – Lehs Dec 22 '15 at 9:14
  • $\begingroup$ 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]$. $\endgroup$ – JimmyK4542 Dec 22 '15 at 9:38
  • $\begingroup$ You should use ⌊⌋ in plain text. $\endgroup$ – Andreas Rejbrand Dec 22 '15 at 15:55

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.