Iterada de la función?

Question

$$f(n) = \frac{n}{\lg n}$$ $$g(n) = \min (i \ge 0: f^i(n)\le 2)$$

En otras palabras, $g(n)$ es el número de veces $f(n)$ tiene que ser iterada para reducir el $n$ a 2 o menos.

¿Qué es un apretado obligado en $g(n)$? $\lg$ es el logaritmo binario ($\log_2$)

Gracias

Answer 1

Tenga en cuenta que $g$ es no decreciente y $g(x)= 1+g( f(x))$$x>2$. También no se que $f(x)\le \frac{x}{k}$ si $x\ge 2^k$. Como consecuencia, para cualquier $k>1$$x>2^k$, $$\tag1\begin{align}g(x)&\le g\left(2^k\right)+\min\left\{i\ge 0\biggm| \frac{x}{k^i}\le 2^k\right\}\\&=g(2^k)+\left\lceil\frac{\ln(2^{-k}x)}{\ln k}\right\rceil\\&\le g(2^k)+1-\frac{k\ln 2}{\ln k}+\frac{\ln x}{\ln k}.\end{align}$$ Desde $\frac1{\ln k}\to 0$$k\to\infty$, podemos obtener inmediatamente $$\tag2 g(x)=o(\ln x).$$

---

Suponga $g(t)\le c\frac{\ln t}{\ln \ln t}$$T_0\le t\le T$$T\ge T_0^4$$T_0>2$. Para$x$$T<x\le 2T$, podemos encontrar $k$ con $T_0\le 2^k\le T$ $\sqrt[4] x\le 2^k\le\sqrt x$ , es decir, $\frac 14\ln x\le k\ln 2\le \frac 12\ln x$ e lo $k=\theta\ln x$$1>\frac1{2\ln2}\ge\theta\ge \frac1{4\ln 2}>0$. Con esto obtenemos $$\begin{align} g(x)&\le g(2^k)+1-\frac{k\ln 2}{\ln k}+\frac{\ln x}{\ln k}\\ &\le c\frac{k\ln 2}{\ln k+\ln\ln 2}+1-\frac{k\ln 2}{\ln k}+\frac{\ln x}{\ln k}\\ &\le (c-1)\frac{k\ln 2}{\ln k}+1+\frac{\ln x}{\ln k}\\ &=1+\left((c-1)\theta\ln 2+1\right)\frac{\ln x}{\ln \theta+\ln \ln x}\\ &=1+\frac{c+1}2\cdot\frac{\ln x}{\ln \theta+\ln \ln x}.\end{align}$$ En orden a la conclusión de $g(x)\le c\frac{\ln x}{\ln\ln x}$ $T\le T\le 2T$ a partir de esto (y por lo tanto, por inducción para todos los $x\ge T_0$), es suficiente para empezar lo suficientemente grande como $T_0$ (de modo que $\ln\theta\ll \ln\ln x$) y $c$ (de modo que ambas $\frac{c+1}2<c$ e las $1$ puede ser absorbida).

Llegamos a la conclusión de $$g(x)=O\left(\frac{\ln x}{\ln\ln x}\right).$$

---

Comentario: De conspirar/numérico de la experimentación, se ve como $$g(x)\sim\frac{\ln x}{\ln\ln x}.$$ Por ejemplo, con $x=e^{1.000.000.000}$, tenemos $$\frac{g(x)\ln\ln x}{\ln x}=1.03442069\ldots$$