3
$\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$ Commented 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$ Commented Aug 16, 2021 at 8:30
  • 3
    $\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$ Commented 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$ Commented 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$ Commented Aug 16, 2021 at 8:47

2 Answers 2

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$ Commented Aug 16, 2021 at 11:46
  • $\begingroup$ I mean $3\uparrow\uparrow\uparrow4$ and $3\uparrow\uparrow\uparrow5$ $\endgroup$ Commented 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$ Commented 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$ Commented Aug 16, 2021 at 12:15
  • 1
    $\begingroup$ (and if you specifically wanted the last eight digits of ${^5}3$, it's $60355387$) $\endgroup$ Commented Aug 16, 2021 at 12:31
1
$\begingroup$

About the first digits, you can read here First digits in tetration (we can say that $3^{3^{3^{3^{3}}}} = 3^{125801429062749131786039069820\ldots}$, but I am not aware of any successful attempt to go beyond height $4$).

The exact number of stable digits of $3^{3^{\ldots^{3}}}$ (at any height) is deeply discussed in this preprint of mine: see Figure 1. Basically, for each $k \in \mathbb{Z}^+$, the number of frozen digits that appear at the end of $3^{3^{...^{3}}}$ ($k$-times) is $k-1$ since the congruence speed of $3$ is $0$ at height $1$ and $1$ at any height above $1$.

Consequently, as long as $m<k$, it is sufficient to consider $3^{3^{...^{3}}}$ ($m$-times) since $^k{3} \equiv \! ^{m+1}{3} \pmod{10^m}$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.