floor に関する等式の証明 - miscalc のブログ

最近気づいたので書きます（有名かも？）

有名な等式として $\displaystyle \left\lfloor \frac{N}{ab} \right\rfloor = \left\lfloor \frac{\left\lfloor \frac{N}{a} \right\rfloor}{b} \right\rfloor$ （ $N, a, b$ は正整数）があります。これを証明します。

整数 $n$ と実数 $r$ に対して

$\begin{align} n \leq r \iff n \leq \lfloor r \rfloor \tag{ * } \end{align}$

であることを利用します。 $n$ を整数として

$\begin{align} &\phantom{{}\iff{}} abn \leq N \tag{1} \\ &\iff bn \leq \frac{N}{a} \tag{2} \\ &\iff n \leq \frac{N}{ab} \tag{3} \end{align}$

ですが、 $(3)$ の後でだけ $( * )$ を適用すると $\displaystyle n \leq \left\lfloor \frac{N}{ab} \right\rfloor$ が得られ、 $(2), (3)$ の両方の後で $( * )$ を適用すると $\displaystyle n \leq \left\lfloor \frac{\left\lfloor \frac{N}{a} \right\rfloor}{b} \right\rfloor$ が得られます。このふたつが同値で、右辺が整数であることから、右辺は等しいです。 $\square$

雑にいうと、操作の途中で floor をとったりとらなかったりしてよい、という感じです。 $\displaystyle \left\lfloor \sqrt{\frac{N}{i}} \right\rfloor = \left\lfloor \sqrt{\left\lfloor \frac{N}{i} \right\rfloor} \right\rfloor$ なども同様に示せますね。