How many distinct values of floor(N/i) exists for i=1 to N.

Question

Say we have a function $F(i)=\text{floor}(N/i)$.

Then how many distinct values of $F(i)$ will exist for all $0 \leq i \leq N$

e.g. We have $N=25$ then.

$F(1)=25$

$F(2)=12$

$F(3)=8$

$F(4)=6$

$F(5)=5$

...

...

...

$F(24)=1$

$F(25)=1$

So total distinct values of $F(i)$ are $(N=25)$ :- $25, 12, 8, 6, 5, 4, 3, 2, 1$

total distinct values are $9$: $(2 \times 5-1)$

Can anyone please help in that total number of distinct values are $O(\sqrt{N})$?

Answer 1

If $k \leqslant \sqrt{N}$, then $\lfloor N/\lfloor N/k\rfloor\rfloor = k$, since, letting $m = \lfloor N/k\rfloor$, we have $$mk\leqslant N < (m+1)k = mk + k \leqslant mk + m = m(k+1),$$ so that gives you $\lfloor \sqrt{N}\rfloor$ values. And the values of $\lfloor N/k\rfloor$ for $k \leqslant \lfloor \sqrt{N}\rfloor$ are all different, since

$$\frac{N}{k-1} - \frac{N}{k} = \frac{N}{k(k-1)} > 1$$

for $1 < k \leqslant \lfloor \sqrt{N}\rfloor$.

So you have either $2\lfloor \sqrt{N}\rfloor$ or $2\lfloor\sqrt{N}\rfloor - 1$ distinct values, depending on whether

$$N \geqslant \lfloor \sqrt{N}\rfloor(\lfloor\sqrt{N}\rfloor+1)$$

or not.

Answer 2

Get the ceil() value of the positive root of the equation t^2 + t - (N + 1) = 0. Let's say the required root be r, then compare (r^2 - 1) with N if (r^2 - 1 >= N) the answer will be 2 * ( r - 1) else the answer will be 2 * (r - 1) + 1. Here is cpp psuedo code :

    int n; // get n
    int r = ceil((sqrt(5 + 4 * n) - 1.00) / 2.00);
    if(r * r - 1 >= n)
        return 2 * (r - 1);
    else
        return 2 * (r - 1) + 1;  

Answer 3

Let $k = \left\lfloor{\frac{N}{i}}\right\rfloor$. Take two cases -

1. $k \le \sqrt{N}$: Clearly there are $\mathcal{O}(\sqrt{N})$ possible values for $k$ in this case
2. $k > \sqrt{N}$: In this case $i \le \sqrt{N}$. Since there are $\mathcal{O}(\sqrt{N})$ possible values for $i$, there are $\mathcal{O}(\sqrt{N})$ values for $k$ as well.

$\implies$ the maximum distinct values of $k$ is $\mathcal{O}(\sqrt{N})$