# Computing the number of digits in power tower

Consider the sequence $$a_1=1,a_2=2^1,a_3=3^{2^1},\cdots,a_{n+1}=n^{a_n}.$$ Is it possible to algorithmically find out the number of digits of $$a_n$$ without actually computing it?

For a single power like $$x=m^p:m,p \in \mathbb N$$ we can simply take the logarithm of $$x$$ to base 10 and add 1 to its integer part. However in case of power tower it is immediately clear how the method can be employed. I would be highly obliged if somebody could point out some way of doing it ,if possible.

Given that the number of digits of $$n \in \mathbb{N}^{+}$$ is $$\lfloor\log_{10}n\rfloor +1$$, the number of digits of $$a_{n+1}$$ is $$\lfloor\log_{10}a_{n+1}\rfloor +1 = \lfloor\log_{10}n^{a_n}\rfloor +1 = \lfloor a_n\log_{10}n\rfloor +1 \ .$$
It doesn't depend on the number of digits on $$a_n$$ but rather on the value of $$a_n$$. So, I would say that you don't directly need to compute $$a_{n+1}$$ in order to know its number of digits but you still need to compute $$a_n$$.
• Computing $a_n$ is what i actually want to avoid because that is itself a tower of powers Commented Jul 23 at 11:45
• @AgnostMystic so you actually want an open formula for $a_n$, not for its number of digits. I don't think it exists, or at least I can't figure out it. You asked for an algorithm and for not explicitly compute $a_{n+1}$ when computing its number of digits and this is what I wrote. If it still doesn't satisfy you I think you can ignore it instead of downvoting. My answer contribute to your question and shows some effort. Your question was not clear on what you exactly want. Do you want the algorithm to have a specific time complexity? Or what? Commented Jul 23 at 12:11
• @AgnostMystic Note that to compute digits of $a_n$ you need at least $\Omega(\log_{10}{a_n})$ time, and computing $a_{n-1}$ takes $O(\log_{10}{a_n})$ time. So, computing $a_{n-1}$ does not make the algorithm asymptotically suboptimal. As for whether computing the number of digits is possible in time $O(\log_{10}{\log_{10}{a_n}})$, that's a good question. Commented Jul 23 at 15:13
• @SilvioM,what you have done i already referred to it in the question.Nowhere did I talk aboit some open formula for $a_n.$Rather ,I explicitly asked about number of digits in $a_n$ Commented Jul 24 at 5:26