Friday, August 30, 2019

elementary number theory - Why does $lfloorfrac{n}{x}rfloor$ have at most $2sqrt{n}$ values when $x=1,2,dots n$?



The question is very short and clear:



Why does $\lfloor\frac{n}{x}\rfloor$ (floor of $\frac nx$) have at most $2\sqrt{n}$ values when $x = 1, 2,\dots, n $?



I saw this statement at tutorial of 449A at codeforces, I really want to know how we get that, and since the amount of values should be integer, why $2\sqrt{n}$?




And I don't know the specific category of this problem so I just tag it as elementary number theory.


Answer



Over the range $1 \le x \le \sqrt{n}$, $x$ can take on only $\sqrt{n}$ distinct integer values. Thus, $\left\lfloor\dfrac{n}{x}\right\rfloor$ can only take on $\sqrt{n}$ distinct values, one for each distinct value of $x$.



Over the range $\sqrt{n} \le x \le n$, we have that $1 \le \dfrac{n}{x} \le \sqrt{n}$. Thus, $\left\lfloor\dfrac{n}{x}\right\rfloor$ can only take on $\sqrt{n}$ distinct values, one for each integer between $1$ and $\sqrt{n}$.



This adds up to $2\sqrt{n}$ values over the entire range $1 \le x \le n$.



Note that this is an upper bound and not an exact number. For instance, if $n = 6$, then we have at most $2\sqrt{6} \approx 4.89$ values. Indeed, $\lfloor\frac{6}{1}\rfloor = 6$, $\lfloor\frac{6}{2}\rfloor = 3$, $\lfloor\frac{6}{3}\rfloor = 2$, $\lfloor\frac{6}{4}\rfloor = \lfloor\frac{6}{5}\rfloor = \lfloor\frac{6}{6}\rfloor = 1$, so we have $4$ distinct values.



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...