Magnitude of $f_3(n)$ compared to power towers of tens

Question

In the fast growing hierarchy , the sequence $f_2(n)$ is defined as $$f_2(n)=n\cdot 2^n$$

The number $f_3(n)$ is defined by $$f_3(n)=f_2^{\ n}(n)$$

For example, to calculate $f_3(5)$, we have to apply the operator $n\cdot 2^n$ five times with start value $5$.

Denote $$T(n):=10\uparrow 10 \uparrow \cdots \uparrow 10 \uparrow 10$$ with $n$ tens, so a power tower of tens with height $n$.

With the help of the computer, I found out that $f_{30}<T(31)$ , but $f_{31}>T(32)$, so $31$ is the smallest number $n$ with $f_3(n)>T(n+1)$

• Can this value also be found without electronic help by bounding the function $f_3(n)$ ?
• Can I also find the smallest number $n$ with $f_3(n)>T(n+k)$ for $k=2,3,4,\cdots$ without brute force ?

Answer 1

We will use $\log$ to mean logarithm base $10$.

Observe that $f_2^k(n) > (2^n \uparrow\uparrow k)n$, as a simple induction shows. Therefore $f_3(n) > 2^n \uparrow\uparrow n$. Since $2^n > 10$ for $n \ge 4$, we thus have

$$\log^{n-2} f_3(n) > 2^{n 2^n}$$

In the other direction, we will show that

$$\log^{n-2} f_3(n) < 2^{n 2^n + 2n}$$

Define $g_i(n)$ by $g_1(n) = n 2^n + 2n$ and $g_{i+1}(n) = 2^{g_i(n)}$. We claim that $g_i(n) > n f_2^i(n)$ for $i \ge 3$ and $n \ge 3$. Indeed, for $i=3$ we have

$n f_2^3(n) = n^2 2^{n+n2^n} 2^{n2^{n + n2^n}} < 2^{2^{n+n2^n}}2^{n2^{n + n2^n}} = 2^{(n+1)2^{n+n2^n}} < 2^{2^n 2^{n+n2^n}} = 2^{2^{2n+n2^n}} = g_3(n)$.

Then, assuming the statement for $i$,

$g_{i+1}(n) = 2^{g_i(n)} > 2^{n f_2^i(n)} > 2^{n + f_2^i(n) + f_2^i(n)} > n f_2^i(n) 2^{f_2^i(n)} = n f_2^{i+1}(n)$.

Thus $\log_2^{k-2}f_2^k(n) < 2^{n2^n + 2n}$, and therefore $\log^{n-2} f_3(n) < \log_2^{n-2} f_3(n) < 2^{n2^n + 2n}$.

It follows that

$$(n 2^n)\log 2 < \log^{n-1}f_3(n) < (n 2^n + 2n)\log 2$$

and $$ n \log 2 + \log n + \log \log 2 < \log^n f_3(n) < n \log 2 + \log n + \log \log 2 + \frac{\log e}{2^{n-1}}$$

and we can see that $\frac{\log e}{2^{n-1}}$ goes to $0$ very quickly.

So, it is reasonably straightfoward to find $h(k) = $ the smallest value of $n$ such that $f_3(n) > T(n+k)$. As you have found, $h(1) = 31$ and $h(2) = 33 219 280 916$; for $k = 3$, if we let $x = 10^{10^{10} - \log \log 2}$, we will have overshot by very very close to $\log x + \log \log 2$; thus letting $y = \lceil x - \frac{\log x + \log \log 2}{\log 2} \rceil$ will very likely give us the exact answer, as the logarithm will be extremely close to constant in that interval. The same method will very likely give the exact answer for all $k$, as the error terms decrease tetrationally.

Answer 2

Interestingly, 10 is not the best base to choose, in fact, 2 is much more optimal, if you allow the top exponent to be altered. As shown in this post of mine, we have the following bounds:

$$n\operatorname{Tet}(2^n,n,1)\le f_3(n)\le\operatorname{Tet}(2\sqrt[n]n,n,n)$$

where

$$\operatorname{Tet}(a,b,c)=\underbrace{a\widehat{}a\widehat{}\dots\widehat{}a\widehat{}}_bc=\begin{cases}c,&b=0\\a\widehat{}\operatorname{Tet}(a,b-1,c),&b>0\end{cases}$$

Thus, it follows that

$$\operatorname{Tet}(2,n,n)\le f_3(n)<^\star\operatorname{Tet}(2+\varepsilon,n,n)$$

where $<^\star$ represents eventual dominance and $\varepsilon>0$.

As for base conversion, you can ignore most of the 2's, only considering the top 2's and converting them to base 10.

---

From this method, we may find bounds for $h(k)=\min\{n|f_3(n)>T(n+k)\}$ by considering the smallest $n$ such that $n\operatorname{Tet}(2^n,j,1)>T(j+k)$ for varying values of $j$.

For $j=1$, we get that which you already noticed,

$$h(k)\approx\log_2(T(k+1))\\h(k)\approx\log_2(T(k+1))-\log_2(h(k))$$

which readily provides a recursive approach for approximating $h(k)$. For example, at $k=2$, we get an initial approximation of

$$h(2)\approx\log_2(T(3))\approx33219280949\\h(2)\approx\log_2(T(3))-\log_2(33219280949)\approx33219280914$$

which is fairly accurate. This is the fixed-point approximation to $n2^n=n\operatorname{Tet}(2^n,1,1)=T(3)$.