What is the time complexity of finding the most significant digit of $3\uparrow\uparrow n$? I know we can find the least significant digits in constant time using modular arithmetic, is the most significant digit known to be harder to compute?

The first digit of $$3\uparrow\uparrow 4$$ still can be determined. We have $$\log_{10}(3)\cdot 3^{(3^3)}=3638334640024.099685574579370$$

Since $10^{0.1}<2$ , we can conclude that the first digit is $1$.

But to calculate the first digit of $$3\uparrow\uparrow 5$$ , we need the logarithm of $3\uparrow\uparrow 5$ with precision better than $1.0$

With a supercomputer, it might be possible to calculate the logarithm precise enough. The magnitude of the logarithm is roughly $10^{(10^{12.56)}}$.

The first digit of $3\uparrow\uparrow n$ for any $n\ge 6$ cannot be caclaulated because the logarithm simply gets too large.

  • I just realized that you asked for the time complexity. I do not know which complexity we have, but since we soon arrive at hopeless magnitudes, it does not matter in practice anyway. – Peter Jan 31 '17 at 14:02
  • I agree that calculating the full value of ${log_10}(3\uparrow\uparrow n)$ is impractical for $n \ge 6$. But we only need the digits after the decimal point, and only one or two of them in most cases. How can we determine whether or not there is some shortcut that could give us those digits quickly, just as there is a shortcut using Euler's Totient Theorem that lets us calculate the last digits of $3\uparrow\uparrow n$ for large $n$? – user171318 Jan 31 '17 at 17:48
  • @user171318 I think no other method than the logarithm is known to determine the first digit (Unless the number can simply be written down). Euler's Totient theorem clearly doesn't help. I asked a similar question (first digit of Graham's number) and noone had an idea. – Peter Feb 1 '17 at 10:21
  • So, for upper bounds, nothing better than about $O(3\uparrow\uparrow n)$ is known? But what about lower bounds? Can we prove that the problem is NP-hard, or even that is is not in DLOGTIME? – user171318 Feb 8 '17 at 17:39

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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