¿Cómo hallamos el número de subintervalos cuya intersección con el subconjunto del intervalo entero no es vacía?

Question

Supongamos que hemos fijado $A=\left\{\frac{1}{k}:k\in\mathbb{N}\right\}$ y dividimos el intervalo $[0,1]$ en $n$ subintervalos de igual longitud. ¿Cómo hallamos la fórula exacta (o aproximación) del número subintervalos $f(n)$ cuya intersección con $A$ no está vacío?

Esto es lo que he encontrado

$$\begin{array}{|c|c|} \hline n & f(n) \\ \hline 1 & 1 \\ \hline 2 & 2 \\ \hline 3 & 3 \\ \hline 4 & 4 \\ \hline 5 & 4 \\ \hline 6 & 5 \\ \hline 7 & 5 \\ \hline 8 & 6 \\ \hline 9 & 6 \\ \hline 11 & 6 \\ \hline 12 & 8 \\ \hline 13 & 7 \\ \hline 14 & 8 \\ \hline 15 & 8 \\ \hline \end{array}$$

Parece difícil encontrar una fórmula exacta, ya que $f(n)$ puede, a veces, ir hacia atrás como $n$ aumenta. Una aproximación es más razonable.

En caso de que encuentre una aproximación, ¿puede detallar cómo la ha encontrado?

Edita: Utilizando gráficos he encontrado que la aproximación es

~~

$$f(n)\approx \frac{\ln(n)^2}{2\ln(2)^2}-\frac{3\ln(n)}{2\ln(2)}+4$$

~~

En $n>32$ pero no sé cómo derivarlo matemáticamente.

Edición: Me equivoqué, véase la respuesta de @Joriki. Sin embargo, no respondió completamente a mi segunda pregunta.

¿Cómo aplicaría su proceso para aproximar $f(n)$ para conjuntos más complejos como

$$A=\left\{\frac{1}{2^x}+\frac{1}{2^y}+\frac{1}{2^z}:x,y,z\in\mathbb{N} \right\}\cap[0,1]$$

Answer 1

$A$ puede dividirse en dos rangos: Si la diferencia entre valores adyacentes de $\frac1k$ es inferior a $\frac1n$ se acierta en todos los intervalos, mientras que si la diferencia es superior a $\frac1n$ cada intervalo es alcanzado como máximo por $1$ elemento. Como la diferencia entre valores adyacentes de $\frac1k$ es aproximadamente $\frac1{k^2}$ la transición entre estos dos rangos se sitúa aproximadamente en $k=\sqrt n$ . Así, cada uno de los primeros $\sqrt n$ valores de $k$ alcanza un nuevo intervalo, y cada uno de los restantes $\sqrt n$ intervalos son alcanzados por al menos un valor, por lo que en total aproximadamente $2\sqrt n$ se alcanzan los intervalos.

He aquí un gráfico de los resultados hasta 2000, comparados con $2\sqrt n$ y también a su aproximación, que parece estar muy lejos de la realidad (por ejemplo, para $n=2000$ produce alrededor de $48$ mientras que el valor real es de aproximadamente $89$ ):

Este es el código que he utilizado para generar los datos del gráfico.

La irregularidad se debe enteramente al hecho de que estás contando los límites de los intervalos hacia los dos intervalos adyacentes. Si cuentas los límites sólo hacia el menor de los dos intervalos, entonces los intervalos son $\left(\frac jn,\frac{j+1}n\right]$ la función se vuelve completamente regular y viene dada por $\left\lfloor\sqrt{4n}\right\rfloor$ que se puede derivar haciendo más rigurosa la consideración anterior y considerando $\frac1k-\frac1{k+1}=\frac1{k(k+1)}=\frac1n$ . He aquí un gráfico de esta función regular (con y sin la función suelo aplicada):

Obsérvese que hay más puntos en los límites cuantos más divisores $n$ (de hecho, la cuenta se incrementa para cada divisor de $n$ debajo de $\sqrt n$ que es la mitad de los divisores de $n$ menos $\frac12$ si $n$ es un cuadrado). Ya lo puedes ver en tus datos: $12$ es altamente divisible y se desvía hacia arriba, mientras que $11$ y $13$ son primos y no tienen recuentos adicionales de los límites.