How do I calculate the first n digits and last m digits of $3^{3^{3^{3^{3}}}}$?

Question

It is possible with $3^{3^{3^{3}}}$, from this algorithm (https://stackoverflow.com/questions/68797298/calculating-3333-very-large-exponent-how-did-wolfram-do-it).

However, being a large number, $3^{3^{3^{3^{3}}}}$ won't run using the same trick.

Most likely it's using the transform log(a^b) = b * log(a) to calculate log(3^3^3^3) = (3^3^3) log(3) = 7625597484987 * log(3), which works out to about 3638334640024.09968557 if you take logs base 10. You'll notice that the integer part of that gives you the number of digits, and if you take 10^0.09968557, you end up with 1.2580143 or so.

Also, Modular exponentiation also depends on the whole number, $3^{3^{3^{3}}}$ being too large, won't help calculate $3^{3^{3^{3^{3}}}}$.

EDIT: I can't apprehend Knuth's up-arrow notation. So what is $g_{1}$ or $3\uparrow\uparrow\uparrow\uparrow3$?

Answer 1

I'm not sure about the leading digit offhand, but I do know how to get the last digit. Tetration is usually written ${^k}x=x^{x^{x^{\dots}}}$ with $k$ $x$'s in the tower, and as I recall, $${^k}x \equiv c \pmod m$$ has the same value of $c$ given some $m$ and any $k>K$, where $K$ is a small constant, almost never out of single digits.

So this means that ${^3}3=3^{3^{3}}$ will have the same last digit as ${^4}3=3^{3^{3^{3}}}$ and so forth, up to infinitely many $3$s. This is equivalent to taking ${^k}3 \bmod{10}$ for large enough (i.e. non-tiny) $k$.

Note this also applies to any hyperoperations which themselves build off of exponentiation, such as Knuth up-arrows; they'll all have the same last digit as tetration.

When I was looking into this a couple years back I made, for Mathematica, this handy function:

tetmod[x_, k_, m_] := Which[
k==1, Mod[x, m],
k==2, PowerMod[x, x, m], 
True, PowerMod[x, EulerPhi@m + Mod[tetmod[x, k-1, EulerPhi@m], EulerPhi@m], m]
]

where tetmod[x,k,m] is ${^k}x \bmod m$. This can handle substantially larger power towers than you could otherwise.

FWIW, it was a while ago, so I may be forgetting about weird edge cases or something, but I remember this being a very robust result in general. For more details, try this thread as a jumping off point, or google tetration modulo.

For the record, I believe it's also straightforward to calculate exactly what $K$ you need for the mod to converge; it's something to do with the Carmichael function.

And to answer your actual question, we'll find that tetmod[3,5,10] yields $7$, so that's your final digit, as it is for any $3$-tower, i.e. $3^3$ and larger.