0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Computing $a_n$ is what i actually want to avoid because that is itself a tower of powers $\endgroup$
    – AgnostMystic
    Commented Jul 23 at 11:45
  • $\begingroup$ @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? $\endgroup$
    – SilvioM
    Commented Jul 23 at 12:11
  • 2
    $\begingroup$ @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. $\endgroup$
    – rus9384
    Commented Jul 23 at 15:13
  • $\begingroup$ @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$ $\endgroup$
    – AgnostMystic
    Commented Jul 24 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.