Iterated logarithm to the $n - 1$ of the auto tetration n^^n

Question

I'm considering the sequence

1. $0 = \log(1)$
2. $\log\left(2^2\right)$
3. $\log\left(\log\left(3^{3^3}\right)\right)$
4. $\log\left(\log\left(\log\left(4^{4^{4^4}}\right)\right)\right)$

I tried solving this using Python and I get lots of $\log(x < 0)$ problems. I thought they were mostly fence post and recursion type errors, so I debugged my code but still the latest iteration has those problems for $n > 5$ or so.

I'm beginning to suspect that the iterated logs are too powerful, even when taken down a notch, and that I should do something to the argument to keep things finite. My first theory, on discovering a recursive solution, was that my sequence was increasing but I'm not at all sure anymore

Just to clarify: by iterated logarithm I mean $\log(\log(\log(... \text{Self tetration}, n^{n^{\dots}} )))$, is just $1$, $2^2$, $3^{3^3}$, ...

Iterated logs to the $n$ are provably overkill and iterated logs to the $n-2$ fail to tame the power tower.

Answer 1

I'm assuming these are natural logarithms, although as it turns out the base of the logarithm doesn't matter much. Write $\log^k$ for the iterated (natural) logarithm and $n \upuparrows k$ for tetration. Note that with base-$n$ logarithms we clearly have

$$\log^k_n (n \upuparrows n) = (n \upuparrows (n-k)).$$

For $n \ge 3$ we have $\log n > 1$ and hence $\log_n x < \log x$, which gives

$$\log^{n-1}(n \upuparrows n) > \log \log_n^{n-2} (n \upuparrows n) = \log n^n = n \log n.$$

In particular there should in principle be no problems with taking logs of negative numbers, but I don't know what any particular piece of Python code might be doing to compute logs here.

But we can say more than this: it turns out that the base of practically every logarithm in the sequence except the outermost one doesn't matter, so the above is a pretty accurate approximation, which means

$$\boxed{ \log^{n-1} (n \upuparrows n) \approx \log n^n = n \log n }$$

so this sequence is increasing except for possibly the first few terms which can be checked by hand. To give an idea of how this works here's the $n = 4$ case. We get

$$\log 4^{4^{4^4}} = 4^{4^4} \log 4$$ $$\log \log 4^{4^{4^4}} = 4^4 \log 4 + \log \log 4.$$

Here $4^4 \log 4 \approx 355$ and $\log \log 4 \approx 0.326$ is much smaller in comparison so can be safely ignored when we take the next logarithm, hence

$$\log \log \log 4^{4^{4^4}} \approx 4 \log 4 + \log \log 4 \approx 4 \log 4.$$

In general we can argue by induction that $\log^k (n \upuparrows n) \approx (n \upuparrows (n-k)) \log n$. The error terms are quite tiny in comparison to how big the power towers are until we get to the outermost or maybe the second-to-outermost log. I can be more precise about this if you want.

Answer 2

This answer is just an expansion of Qiaochu Yuan's answer to get a memorizable recursive form and to have a handful of actual values

I've explicated Qiaochu Yuan's approach with one more term, for instance for $m=4$ computing $$ \log^{\circ3} (\;^44) = 4 \log(4)+ \log^{\circ2}(4)+\log\left(1+\frac{\log^{\circ2}(4)}{\log(4)} \frac1{\;^24} \right) \tag 1 $$ So this is a bit more precise, and suffices, when we work with more than the usual ~20 digits precision.

To have the scheme for larger $m$ handable, I've done the following notation and computation:

---

For the following, let's denote for the logarithm $\lambda (x) := \log(x)$, and $ \lambda^{\circ h}(x):=\log^{\circ h}(x)$ for the $h$-fold iterated $\log()$.
Moreover, we allow to omit the parentheses for a simple argument like $\lambda m := \log(m)$, $\lambda\lambda m := \log(\log(m))$ and so on.

Then for $m=2$ we have
$$ \lambda^{\circ 1}(\;^22) = \;^12 \lambda2 = 2 \lambda 2 \tag 2 $$

For $m=3$ we have $$ \lambda^{\circ 2}(\;^33) = \;^13 \lambda3 \left( 1+ { \lambda\lambda3 \over \;^13 \lambda3 } \right) = 3\lambda3+ \lambda\lambda 3 \tag 3 $$

For $m=4$ we have $$ \lambda^{\circ 3}(\;^44) = \;^14 \lambda4 \left( 1+ { \lambda\lambda4 + \lambda \left( 1+{ \lambda\lambda4 \over \;^24 \lambda4} \right) \over \;^14 \lambda4 } \right) \\ = 4 \lambda4 + \lambda \lambda 4+ \lambda\left(1+ {\lambda\lambda4\over \;^24 \lambda 4}\right) \tag 4 $$ For $m=5$ we have $$ \lambda^{\circ 4}(\;^55) = \;^15 \lambda5 \left( 1+ { \lambda\lambda5 + \lambda \left( 1+{ \lambda\lambda5 + \color{red}{ \lambda\left( 1+ {\lambda\lambda5\over \;^35 \lambda5} \right)} \over \;^25 \lambda5} \right) \over \;^15 \lambda5 } \right) \\ = 5 \lambda5 + \lambda \lambda 5+ \lambda\left(1+ {\lambda\lambda5 + \varepsilon \over \;^25 \lambda 5}\right) \qquad \varepsilon \lt 10^{-2000} \tag 5$$ Here, the $\color{red} {\text{red}}$ part might be set to zero - although Pari/GP can evaluate it to the small number $1.5472633343566660957 \cdot 10^{-2185}$.

I think, it is obvious enough, to see how this recursive expression extends for the case $m=6$ and $m \gt 6$.

So in general we could -with very good approximation to thousands of digits- denote the general case for $m \ge 4$: $$ \lambda^{\circ m-1}(\;^mm) = \;^1m \lambda m \left( 1+ { \lambda\lambda m + \lambda \left( 1+{ \lambda\lambda m \color{red}{+ \varepsilon} \over \;^2 m \lambda m} \right) \over \;^1m \lambda m } \right) \qquad \phantom {aaaaaaaaaaaa}\\ = m \lambda m + \lambda \lambda m+ \lambda\left(1+ {\lambda\lambda m + \varepsilon \over \;^2m \lambda m}\right) \qquad m \ge 4,\varepsilon \lt 10^{-2000} \tag 6 $$ For actual evaluation of course set $\varepsilon=0$.

---

Pari/GP can evaluate the rhs of this formula up to large $m$ and here is a short list of results:

   m   f(m)
   1                      1
   2  1.3862943611198906188
   3  3.3898846936210280904
   4  5.8727316593473939578
   5  8.5231691718927068792
   6  11.333761872486528355
   7  14.287101269386856237
   8  17.367631722509864240
   9  20.562216205127370811
  10  23.859883375224634209
  11  27.251439383707043270
  12  30.729114890821370757
  13  34.286280381748089855
  14  37.917224395890985590
  15  41.616981909484545859
  16  45.381200996374726095
  17  49.206038373730453973
  18  53.088076771932640857
  19  57.024258903684450970
  20  61.011834171444768572

The Pari/GP-program used is this (I set internal computational precision to 200 dec digits by default):

{list=matrix(20,2);
 for(m=1,20, 
    for(dummy=1,1,
                     if(m==1,t1=m;       break());
         lm=log(m);  if(m==2,t1=m*lm;    break());
         llm=log(lm);if(m==3,t1=m*lm+llm;break());
         t3=log(1+0+0); /* t3=log(1+llm/lm/m^m^m+ log(1+ ...(recursion)...));*/
         t2=log(1+llm/lm/m^m+t3);
         t1=m*lm+llm+t2;
       );
   list[m,]=[m,t1];
   );  }
               \\ -----------------
print(list);