2
$\begingroup$

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

$\endgroup$
12
  • 2
    $\begingroup$ @Polv The leading digits of $3^{3^{3^{3^{3}}}}$ is easy with a few logarithms and enough accuracy, and WA can do it without issues. Multiple up-arrows is a whole different ball-game. $3\uparrow\uparrow\uparrow 3$ is a power-tower of roughly 7 billion 3's stacked on top of one another. $\endgroup$
    – Arthur
    Aug 16, 2021 at 8:25
  • 1
    $\begingroup$ @Arthur Apparent, maybe I am wrong, but Wolfram won't even try to calculate the leading digits of $3^{3^{3^{3^{3}}}}$ wolframalpha.com/input/?i=3%5E3%5E3%5E3%5E3 $\endgroup$
    – Polv
    Aug 16, 2021 at 8:30
  • 2
    $\begingroup$ @Polv You're right, I went one too high, WA does get an answer with four 3's. But still, my main point was that up-arrow is a lot more powerful than exponentiation. When you say "$3^{3^{3^3}}$ or $3\uparrow\uparrow\uparrow\uparrow3$", that tells me you haven't realized this. $3^{3^{3^3}}$ is equal to $3\uparrow\uparrow4$. That's nowhere near what you get with four arrows. $\endgroup$
    – Arthur
    Aug 16, 2021 at 8:37
  • 1
    $\begingroup$ We would need the fractional part of $(3\uparrow 3\uparrow 3\uparrow 3)\cdot \log_{10}(3)$ and $3\uparrow 3\uparrow 3\uparrow 3$ has $$3\ 638\ 334\ 640\ 025$$ digits. This might be feasible with extreme computational power, but if we add another $3$ to the power tower, the game is over. $\endgroup$
    – Peter
    Aug 16, 2021 at 8:38
  • 1
    $\begingroup$ To make Arthur's comment more exact (I do not know whether he means $10^{12}$ with "billion") : $3\uparrow \uparrow \uparrow 3$ is a power tower with $$3^{27}=7\ 625\ 597\ 484\ 987$$ threes. $\endgroup$
    – Peter
    Aug 16, 2021 at 8:47

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ The last digit is always easy, but last n digits are not. I am trying to figure out right now, with en.wikipedia.org/wiki/… As I directly use pow(int(base.last), exp.val, 10_000_000_000) (where pow is modpow in Python), for $3\uparrow\uparrow4$ I can get the answer of $...00739387$. However, if exponent's value cannot be totally determined (as in $3\uparrow\uparrow5$), I am ruined... $\endgroup$
    – Polv
    Aug 16, 2021 at 11:46
  • $\begingroup$ I mean $3\uparrow\uparrow\uparrow4$ and $3\uparrow\uparrow\uparrow5$ $\endgroup$
    – Polv
    Aug 16, 2021 at 11:52
  • $\begingroup$ I'm confused, is there some reason the same approach wouldn't apply? I.e. if ${^k}3 \bmod{10^8}=739387$, it should also hold for $3\uparrow^{a} x$. $\endgroup$
    – Trevor
    Aug 16, 2021 at 12:04
  • $\begingroup$ Okay, yeah, I get ${^4}3 \bmod {10^8}=739387$ too, but it looks like for all towers of height $k\geq 9$, taking it $\bmod 10^8$ always gives $64195387$. Since any up-arrow construct is ultimately a repeated power tower, this should be true of those also. $\endgroup$
    – Trevor
    Aug 16, 2021 at 12:15
  • 1
    $\begingroup$ (and if you specifically wanted the last eight digits of ${^5}3$, it's $60355387$) $\endgroup$
    – Trevor
    Aug 16, 2021 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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