¿Cuántos enteros únicos se pueden obtener al hacer $\left\lceil\frac{F}{1:1:N}\right\rceil$?

Question

Suponga que $F$ y $N$ son enteros positivos, y $N. ¿Cuántos enteros únicos obtendría si aplicara la función techo a la división de $F$ dividido por $1,2,\ldots,N$, respectivamente? Es decir, quiero una fórmula para contar (aproximadamente) $\mathrm{\texttt{length}}(\mathrm{\texttt{unique}}\left(\mathrm{\texttt{ceil}}(F./(1:1:N))\right))$, que está expresado en lenguaje Matlab.

Answer 1

Dejemos $g_f(n)=\left\lceil \frac{f}{n}\right\rceil$. Podemos primero mirar la diferencia hacia adelante de $g_f$, que es $\Delta[g_f](n)=g_f(n+1)-g_f(n)$. Cuando $\Delta[g_f](n)\geq -1$ para todo $n\geq n_0$, entonces $g_f(n)$ tomará todos los valores de $g_f(n_0)$ a $g_f(f-1)=2$ cuando $n\geq n_0.$ Además, si $$f\left(\frac{1}{n_0+1}-\frac{1}{n_0}\right)= -1,$$ entonces para todo $n\geq n_0$, $$f\left(\frac{1}{n_0+1}-\frac{1}{n_0}\right)\geq -1,$$ así que $$\Delta[g_f](n)\geq -1.$$ También notamos que si $$f\left(\frac{1}{n_0+1}-\frac{1}{n_0}\right)< -1,$$ entonces para todo $n, $$\Delta[g_f](n)< -1,$$ así que cada valor de $g_f(n)$ es único para todo $n. Cuando resolvemos para $n_0$, obtenemos $n_0^2 +n_0-f=0$, así que $$n_0=\frac{-1+\sqrt{1+4f}}{2}.$$ Sin embargo, $$0\leq\left\lceil\sqrt{f}\right\rceil-\left\lceil\frac{-1+\sqrt{1+4f}}{2}\right\rceil\leq 1.$$ Así que si usáramos $n_1=\sqrt{f}$ en lugar de $n_0$, las desigualdades para $\Delta[g_f](n)$ seguirían siendo válidas. Por lo tanto, el número de valores únicos de $g_f(n)$ donde $1\leq n es $$\lceil n_1\rceil-1+g_f(\lceil n_1 \rceil)-1=2\left\lceil \sqrt{f}\right\rceil -2.$$ Ahora el número de valores únicos de $g_f(n)$, donde $1\leq n \leq N < f$ es $$\begin{cases}N & N<\left\lceil \sqrt{f}\right\rceil\\ 2\left\lceil \sqrt{f}\right\rceil -\left\lceil\frac{f}{N}\right\rceil & N\geq \left\lceil \sqrt{f}\right\rceil. \end{cases}$$ El primer caso proviene del hecho de que cada valor de $g_f(n)$ es único para todo $n, y el segundo caso proviene del hecho de que $g_f(n)$ tomará todos los valores de $g_f(n_1)$ a $g_f(f-1)=2$ cuando $n\geq n_1,$ pero perdemos todos los valores de $g_f(N)-1$ y $2$ debido a la restricción $n\leq N$.