1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ $$\biggl\lfloor \frac{n}{x}\biggr\rfloor = q \iff q \leqslant \frac{n}{x} < q+1$$ $\endgroup$ – Daniel Fischer Jul 6 '15 at 11:13
  • $\begingroup$ Are $n$ and $q$ positive? Since inequalities are involved in the definition of the floor function, signs matter. $\endgroup$ – Rory Daulton Jul 6 '15 at 11:14
  • $\begingroup$ Yes $n, q\geq 1$ $\endgroup$ – uttamkhanal Jul 6 '15 at 11:15
2
$\begingroup$

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.

$\endgroup$

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.