Iterated function?

Question

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

In other words, $g(n)$ is the number of times $f(n)$ needs to be iterated to reduce $n$ to 2 or less.

What's a tight bound on $g(n)$? $\lg$ is the binary logarithm ($\log_2$)

Thanks

Answer 1

Note that $g$ is nondecreasing and $g(x)= 1+g( f(x))$ for $x>2$. Also not that $f(x)\le \frac{x}{k}$ if $x\ge 2^k$. As a consequence, for any $k>1$ and $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}$$ Since $\frac1{\ln k}\to 0$ as $k\to\infty$, we immediately obtain $$\tag2 g(x)=o(\ln x).$$

---

Assume $g(t)\le c\frac{\ln t}{\ln \ln t}$ for $T_0\le t\le T$ with $T\ge T_0^4$ and $T_0>2$. For $x$ with $T<x\le 2T$, we can find $k$ with $T_0\le 2^k\le T$ and $\sqrt[4] x\le 2^k\le\sqrt x$, i.e. $ \frac 14\ln x\le k\ln 2\le \frac 12\ln x$ and thus $k=\theta\ln x$ with $1>\frac1{2\ln2}\ge\theta\ge \frac1{4\ln 2}>0$. With this we obtain $$\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}$$ In order to conclude $g(x)\le c\frac{\ln x}{\ln\ln x}$ also for $T\le T\le 2T$ from this (and hence by induction for all $x\ge T_0$), it is sufficient to start with big enough $T_0$ (so that $\ln\theta\ll \ln\ln x$) and $c$ (so that both $\frac{c+1}2<c$ and the $1$ can be absorbed).

We conclude $$ g(x)=O\left(\frac{\ln x}{\ln\ln x}\right).$$

---

Remark: From plotting/numerical experimentation, it looks like $$ g(x)\sim\frac{\ln x}{\ln\ln x}.$$ For example, with $x=e^{1.000.000.000}$, we have $$\frac{g(x)\ln\ln x}{\ln x}=1.03442069\ldots$$