退出

Minimum value of $i$ to change $\lfloor n / i \rfloor$

数论 Math StackExchange 1 票 1 回答 38 浏览 提问者: insipidintegrator 2026-06-09 07:34
number-theory ceiling-and-floor-functions programming

问题内容

I was solving this CSES question called Sum of Divisors and one of the solutions in the USACO Guide hints at this statement:

The minimum value of $j > i$ such that $\lfloor n/j \rfloor$ < $\lfloor n/i \rfloor$ is $j = \lfloor n/q \rfloor + 1$, where $q = \lfloor n/i \rfloor$ for integers $j, i \le n$.

I am trying to prove this.

Let $q = \lfloor n/i \rfloor$, then since $q \le \dfrac ni$, we have $\dfrac nq \ge i$. But since $i$ is an integer we can also write $$\left\lfloor \dfrac nq \right\rfloor \ge i \implies 1 + \left\lfloor \dfrac nq \right\rfloor \ge i + 1$$ and so $$\dfrac{n}{1 + \left\lfloor \dfrac nq \right\rfloor} \le \frac{n}{i+1}\lt\frac ni\implies \left\lfloor\dfrac{n}{1 + \left\lfloor \dfrac nq \right\rfloor}\right\rfloor \le \left\lfloor\frac ni\right\rfloor$$ $$\implies \left\lfloor\frac nj\right\rfloor \le \left\lfloor\frac ni\right\rfloor$$

  1. I need to prove that $\left\lfloor\dfrac nj\right\rfloor \lt \left\lfloor\dfrac ni\right\rfloor$. How do I get the strict inequality?
  2. I also need to prove that $\left\lfloor\dfrac nq\right\rfloor + 1$ is the minimum such $j$ possible. For that we would want $\lfloor n / \lfloor n/q\rfloor\rfloor = q$, for which I give a partial attempt again:

$$q = \left\lfloor \dfrac ni \right\rfloor \implies qi \le n \lt (q + 1)i$$, then $$i \le \frac nq \lt \frac {q+1}{q}i\implies i \le \left\lfloor \dfrac nq \right\rfloor\lt i + \left\lfloor \dfrac iq \right\rfloor$$ Inverting this and trying to get $\lfloor n / \lfloor n/q\rfloor\rfloor$ just seems too clunky after this.

回答 (1)

Michael Hartley 1 票 已采纳 2026-06-09 08:23 原文

Forget about $i$. Let $q$ be any positive integer. We can prove that the minimum $j$ such that $\lfloor n/j \rfloor<q$ is $j = \lfloor n/q\rfloor + 1$.

Suppose $j$ is as described. This is so if and only if for any $k<j$, we have

$$\left\lfloor \frac{n}{j} \right\rfloor<q\ \ \ {\mathrm{and}}\ \ \ \left\lfloor \frac{n}{k} \right\rfloor\geq q.$$

Since $\lfloor \frac{n}{k} \rfloor$ is non-increasing, this is true if and only if $$\left\lfloor \frac{n}{j} \right\rfloor<q\ \ \ {\mathrm{and}}\ \ \ \left\lfloor \frac{n}{j-1} \right\rfloor\geq q,$$ which is true if and only if $$ \frac{n}{j}<q\ \ \ {\mathrm{and}}\ \ \ \frac{n}{j-1}\geq q,$$ that is, $$ \frac{n}{q}<j\ \ \ {\mathrm{and}}\ \ \ \frac{n}{q}\geq j-1,$$ which is equivalent to $$ \left\lfloor\frac{n}{q}\right\rfloor=j-1$$ as required.