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

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 ?
• I once worked out some crude estimates for power towers here: math.stackexchange.com/questions/612967 not sure if they are good enough. – nbarto Dec 18 '17 at 18:51
• @barto Note that the $f_3(n)$-function does NOT produce power towers. – Peter Dec 18 '17 at 18:52
• For large $n$, the "top"-entry $x$ of the power tower $$f_3(n)=10\uparrow 10\uparrow\cdots \uparrow 10\uparrow 10\uparrow x$$ seems to be $n\lg(2)+\lg(n)+\lg(\lg(2))$ (upto repeated taking the logarithm to base $10$), where $\lg$ denotes the logarithm to base $10$. If so, for $k=2$ , we would get $$33\ 219\ 280\ 916\approx \frac{10^{10}}{\lg(2)}$$ – Peter Dec 18 '17 at 19:08
• – Simply Beautiful Art Jan 16 '18 at 14:45

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.

• This also approves the "top-entry" for large $n$ (+1) – Peter Dec 20 '17 at 9:33
• Is the first index $3$ in $\log_3^n f_3(n)$ a typo ? – Peter Dec 20 '17 at 9:35
• Yes, that was a typo. – Deedlit Dec 21 '17 at 16:26

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)$.