# Knuth's up arrow notation

Given n, how can the number m with

$10 \uparrow \uparrow m < 2 \uparrow \uparrow n < 10 \uparrow \uparrow (m+1)$

be calculated ?

With induction, I got

$10 \uparrow \uparrow m < 2 \uparrow \uparrow (2m+1)$

for all m.

• Use the fact that $a \uparrow \uparrow m = a^(a\uparrow\uparrow m-1)$ Commented Dec 19, 2013 at 13:21

Let us first extend Knuth's $\uparrow \uparrow$ tetration to real numbers, see stackexchange tetration link, where we want to calculate m exactly. Here, slog is defined as the inverse of tetration, and now we have m as a function of n, and we can look at m as a function of integer values of n. $10 \uparrow \uparrow m = 2 \uparrow \uparrow n \\ m = \text{slog}_{10}(2 \uparrow \uparrow n) \\m(0) = \text{slog}_{10}(2 \uparrow \uparrow 0) = \text{slog}_{10}(1) = 0 \\m(1) = \text{slog}_{10}(2 \uparrow \uparrow 1) = \text{slog}_{10}(2) \approx 0.39311252 \\m(2) = \text{slog}_{10}(2 \uparrow \uparrow 2) = \text{slog}_{10}(4) \approx 0.70798979 \\m(3) = \text{slog}_{10}(2 \uparrow \uparrow 3) = \text{slog}_{10}(16) \approx 1.1099033 \\m(4) = \text{slog}_{10}(2 \uparrow \uparrow 4) = \text{slog}_{10}(65536) \approx 1.7773966 \\m(5) = \text{slog}_{10}(2 \uparrow \uparrow 5) = \text{slog}_{10}(2^{65536}) = 1 + \text{slog}_{10}(\log_{10}(2^{65536})) = \\ \quad\quad\> = 1 + \text{slog}_{10}(65536 \times \log_{10}(2)) \approx 2.7352838 \\m(6) = 1 + \text{slog}_{10}(2^{65536} \times \log_{10}(2)) \\ \quad\quad\> = 2 + \text{slog}_{10}(65536 \times \log_{10}(2) + \log_{10}(\log_{10}(2)))\approx 3.7352828 \\m(7) = 2 + \text{slog}_{10}(2^{65536} \times \log_{10}(2) + \log_{10}(\log_{10}(2))) \\ \quad\quad\> = 3 + \text{slog}_{10}(65536 \times \log_{10}(2) + \log_{10}(\log_{10}(2)) + O\frac{1}{2\uparrow\uparrow 5}) \\ \quad\quad\> = m(6)+1+O\frac{1}{2\uparrow\uparrow 5} \approx 4.7352828 \\m(8) = m(7)+1+O\frac{1}{2\uparrow\uparrow 6} = m(6)+2+O\frac{1}{2\uparrow\uparrow 5} \approx 5.7352828 \\m(9) = m(8)+1+O\frac{1}{2\uparrow\uparrow 7} = m(6)+3+O\frac{1}{2\uparrow\uparrow 5} \approx 6.7352828$

Edit, note that $\log_{10}(\log_{10}(2^{2^x}))$ can be expressed exactly in terms of $\log_{10}(2^x)$, as $\log_{10}(\log_{10}(2^{2^x}))=\log_{10}(2^x) + \log_{10}(\log_{10}(2))$, which with a little algebra can be used to prove the $O\frac{1}{2\uparrow\uparrow(n-2)}$ error term, in terms of the slog's derivative. If n>=7, the approximation $m(n)\approx m(n-1)+1$ is justified since the $\log_{10}(\log_{10}(2)) \approx -0.5214$ addition term can be ignored as completely insignificant when added to a 19,729 decimal digit number, $2^{65536}$.

$$m(n) = m(n-1) + 1 + O\frac{1}{2\uparrow\uparrow(n-2)}$$

And, as I tried to show without showing all of the messy algebra, the error term formula can also be generalized, as $m(6+k) = m(6) + k + O\frac{1}{2\uparrow\uparrow 5}$, for any integer k>=1, no matter how large, since the error term gets so small so quickly as k increases. Therefore the answer to the op's question for any n>=4 is as follows. $$10 \uparrow \uparrow (n-3) < 2 \uparrow \uparrow n < 10 \uparrow \uparrow (n-2)$$

This result also implies that tetration for different bases ultimately grows at the same rate, although surprisingly, the approximation is much much more exact for integer values of n, since the (n-2.2647172) constant actually turns out to be a small 1-cyclic sinusoid, so that for integer n>=6 $m(n+0.5) \approx (n+0.5-2.2651954)$ which is 0.0004782 smaller than the formula for integer values of n for m(n).

• The left inequality does hold for all n>=4. It is valid, but I would like to make the argument a little clearer.... perhaps by being more explicit for the step: log_10(log_10((x^2)^2) in terms of log_10(x^2), and an error term. Commented Dec 23, 2013 at 21:57
• Ok, you are right. Commented Dec 24, 2013 at 2:09
• I tried to balance algebra complexity, and showing why the answer is what it is. Maybe someday I'll figure out how to present this more clearly..... Commented Dec 24, 2013 at 2:59
• I thought about improving the answer to the other similar quesiton, slog(iterated factorial), but then I decided it wasn't worth rewriting the answer, to improve clarity. This is partly because it would be much easier if the question compared base(e) tetration to iterated factorials. Otherwise, it takes too much effort for not a lot of additional clarity. I actually haven't worked with the iterated factorial problem, before I answered the question. Commented Dec 24, 2013 at 3:37