Help me with an interesting number theory proof: Find all different [n/k] - floor function

97 Views Asked by At

A positive integer $n$ is given. Let's consider all numbers of the form $\lfloor\frac{n}{k}\rfloor$ where $k$ is a positive integer. Prove that there are no more than $2\sqrt n + 1$ different numbers of such form.

Note: for $x \in \mathbb R$, $\lfloor x \rfloor$ is the greatest integer not greater than $x$.

I do know that for $k \gt n$ I will always get $0$, for $\frac{n}{2} \lt k \leq n$ I will always get $1$, for $\frac{n}{3} \lt k \leq \frac{n}{2}$ I will always get $2$ etc. but I have no idea how to generalize it somehow.

1

There are 1 best solutions below

0
On

For $k \le \sqrt n$ there are at most $\lfloor \sqrt n \rfloor$ different values because there are only that many different $k$'s. For $k \gt \sqrt n, \frac nk \lt \sqrt n$, so there are at most $\lfloor \sqrt n \rfloor+1$ different values because $0$ is included. The total of these is $2\lfloor \sqrt n \rfloor+1 $.