Cuántos valores distintos del floor(N/i) existe para i = 1 a N.

Question

Digamos que tenemos una función de $F(i)=\text{floor}(N/i)$.

Entonces, ¿cómo muchos valores distintos de $F(i)$ existen para todos los $0 \leq i \leq N$

por ejemplo, Tenemos $N=25$ entonces.

$F(1)=25$

$F(2)=12$

$F(3)=8$

$F(4)=6$

$F(5)=5$

...

...

...

$F(24)=1$

$F(25)=1$

Así que el total de valores distintos de $F(i)$ $(N=25)$ :- $25, 12, 8, 6, 5, 4, 3, 2, 1$

total de valores distintos son $9$: $(2 \times 5-1)$

Puede alguien por favor, ayudar en que el número total de valores distintos se $O(\sqrt{N})$?

Answer 1

Si $k \leqslant \sqrt{N}$,$\lfloor N/\lfloor N/k\rfloor\rfloor = k$, ya que, dejando $m = \lfloor N/k\rfloor$, tenemos $$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$ son todos diferentes, desde

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

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

Así que usted tiene cualquiera de las $2\lfloor \sqrt{N}\rfloor$ o $2\lfloor\sqrt{N}\rfloor - 1$ valores distintos, dependiendo de si

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

o no.