floor function problems

Question

There are two parts of my problem.

1. Given $n$ and $x$, $\lfloor \frac nx \rfloor = q$, what is the maximum possible value for $x$ such that we obtain the same floor value? i.e. $\lfloor \frac nx \rfloor = \lfloor \frac{n}{x'}\rfloor = q$, where $x' \geq x $. I think $x' = \lfloor \frac nq \rfloor$ is the answer.
2. How many possible values(distinct) for q are there for all $x$ where $1\leq x\leq n$?

My thinking was that, what is the maximum value of $q$ that we can obtain and also the minimum value of $q$. Then, the answer would be $max - min + 1$. But this is surely wrong because we can have same floor values for different values of x. For example, for any $x \geq \lfloor \frac n2\rfloor + 1$, $q = \lfloor \frac nx\rfloor = 1$. Thus the maximum number of distinct floor values is at most $1 + \lfloor \frac n2 \rfloor$. How do I reduce the upper bound since I have read that there are at most $2\sqrt n$ distinct vaues?

Answer 1

By definition of $\lfloor\cdot\rfloor$, we have

$$\biggl\lfloor \frac{n}{x}\biggr\rfloor = q \iff q \leqslant \frac{n}{x} < q+1$$

for $q\in \mathbb{Z}$. Since we are here dealing with positive integers, the sense of the inequalities is retained when multiplying with $x$ and dividing by $q$ resp. $q+1$, so we have

$$\biggl\lfloor \frac{n}{x}\biggr\rfloor = q \iff \frac{n}{q+1} < x \leqslant \frac{n}{q}.$$

Using that also $x$ shall be an integer, we obtain

$$\biggl\lfloor \frac{n}{x}\biggr\rfloor = q \iff \biggl\lfloor \frac{n}{q+1}\biggr\rfloor < x \leqslant \biggl\lfloor\frac{n}{q}\biggr\rfloor.$$

Hence, for each $q$ there are $\bigl\lfloor \frac{n}{q}\bigr\rfloor - \bigl\lfloor \frac{n}{q+1}\bigr\rfloor$ integer values $1 \leqslant x \leqslant n$ so that $\bigl\lfloor \frac{n}{x}\bigr\rfloor = q$, and the maximal such $x$ is indeed $\bigl\lfloor \frac{n}{q}\bigr\rfloor$.

How do I reduce the upper bound since I have read that there are at most $2\sqrt{n}$ distinct values?

Note that for $x > \sqrt{n}$, we have $\frac{n}{x} < \sqrt{n}$ and hence $\bigl\lfloor \frac{n}{x}\bigr\rfloor \leqslant \lfloor \sqrt{n}\rfloor$. Thus we have at most $\lfloor \sqrt{n}\rfloor$ distinct values of $\bigl\lfloor \frac{n}{x}\bigr\rfloor$ for $1 \leqslant x \leqslant \lfloor \sqrt{n}\rfloor$, and the $\lfloor \sqrt{n}\rfloor$ values $1 \leqslant q \leqslant \lfloor \sqrt{n}\rfloor$ for $\lfloor \sqrt{n}\rfloor + 1 \leqslant x \leqslant n$, which gives at most $2\lfloor \sqrt{n}\rfloor$ distinct values total. In fact, the values of $\bigl\lfloor \frac{n}{x}\bigr\rfloor$ for $1 \leqslant x \leqslant \lfloor \sqrt{n}\rfloor$ are all distinct, and all values $1 \leqslant q \leqslant \lfloor \sqrt{n}\rfloor$ are attained, so there are exactly $2\lfloor \sqrt{n}\rfloor$ distinct values, unless the value $\lfloor \sqrt{n}\rfloor$ appears in both sets - when $\bigl\lfloor \frac{n}{\lfloor \sqrt{n}\rfloor}\bigr\rfloor = \lfloor \sqrt{n}\rfloor$, or equivalently $n < \lfloor \sqrt{n}\rfloor\cdot (\lfloor \sqrt{n}\rfloor + 1)$ - in which case there are exactly $2\lfloor \sqrt{n}\rfloor - 1$ distinct values.