Do the last digits of exponential towers really converge to a fixed sequence?
While fooling around with exponential towers I noticed something odd:
$$ 3^{3} \equiv 2\underline{7} \mod 100000 $$ $$ 3^{3^{3}} \equiv 849\underline{87} \mod 100000 $$ $$ 3^{3^{3^{3}}} \equiv 39\underline{387} \mod 100000 $$ $$ 3^{3^{3^{3^{3}}}} \equiv 5\underline{5387} \mod 100000 $$ $$ 3^{3^{3^{3^{3^{3}}}}} \equiv \underline{95387} \mod 100000 $$ $$ \dots$$
It seems that the last digits always converge to a fixed sequence! Is this really true and if yes - can someone think of a proof for this statement?
Any kind of help will be appreciated
Yes, they do. To prove this, all we need to know is that exponents are periodic functions mod $n$ with a period of less than $n$. That is to say, for any $b$, there is always some $k<n$ such that, for all large enough $x$ we have: $$b^{x}\equiv b^{x+k}\pmod n.$$ To prove this, we can split into two cases - firstly, if $b$ is coprime to $n$, this follows quickly, because then $k$ can be taken as the multiplicative order of $b$ mod $n$, which must divide $\varphi(n)$ (the order of the multiplicative group mod $n$), which is less than $n$.
If $b$ is not coprime to $n$, then we write, from unique factorization: $$b=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_{c_1}^{\alpha_{c_1}}$$ $$n=p_1^{\beta_1}p_2^{\beta_2}\ldots p_{c_1}^{\beta_{c_1}}q_1^{\kappa_1}q_2^{\kappa_2}\ldots q_{c_2}^{\kappa_{c_2}}$$ where the $p$'s and $q$'s are distinct. Then, if we let $$m_1=p_1^{\beta_1}p_2^{\beta_2}\ldots p_{c_1}^{\beta_{c_1}}$$ $$m_2=q_1^{\kappa_1}q_2^{\kappa_2}\ldots q_{c_2}^{\kappa_{c_2}}$$ we can say that $m_1$ and $m_2$ are coprime and so are $b$ and $m_2$. Notice that $m_2$ can alternatively be defined as the largest divisor of $n$ coprime to $b$. One can go on to show that $b^x\equiv 0 \pmod{m_1}$ for sufficiently large $x$, as for each $p_i$ we have $b^{\beta_i}\equiv 0\pmod{p_i}$. Therefore, for sufficiently large $x$, the function $b^x$ is periodic with period $1$, mod $m_1$. Then, $b$ is coprime to $m_2$ and hence, from before, periodic there with some period less than $m_2$. Using the Chinese Remainder Theorem establishes that the period mod $n=m_1m_2$ is the LCM of the periods mod $m_1$ and $m_2$ and hence is some number less than $m_2$, which is less than $n$.
With this lemma in hand, the rest of the proof is simple; we can set it up as a proof by induction. Obviously, $b^{b^{\ldots}}\pmod 1$ is well-defined (i.e. takes a single value for all large enough towers), since everything integer is equivalent mod $1$. Next, suppose that, for all $n'<n$ we have that $b^{b^{\ldots}}\pmod{n'}$ is well-defined. Then, we can prove it is well-defined for $n$ too, since the value of $b^x$ is determined (for large enough $x$) by knowing $x$ mod some $m<n$. In this case, we have $x=b^{b^{\ldots}}$ and it is clear that, for large enough towers, this satisfies the hypothesis of being a large enough number for $b^x$ to be periodic and further, given the inductive hypothesis, must be well-defined mod $m$. From this, we can conclude that $b^{b^{\ldots}}$ is well-defined mod $n$ for all $b$ and $n$.
(Adding this answer to showcase a noteworthy generalization ...)
Yours is a very special case of the following:
If $k$ and $a_1,a_2,a_3,\ldots$ are any positive integers, then the sequence $$a_1,a_1^{a_2},a_1^{a_2^{a_3}},a_1^{a_2^{a_3^{a_4}}},\dots$$ is eventually constant $\pmod k.$
The above is a consequence of the following remarkable fact, which is proved as Corollary 2.11 in the paper Iterated exponents in number theory by D. B. Shapiro & S. D. Shapiro; Integers (2007), Vol. 7(1) #A23:
If $a_j\in\mathbb{Z_+}$, then the towers $a_1\uparrow a_2\uparrow\dots a_{h(k)}\uparrow c$ reduce to the same value in $\mathbb{Z}/k\mathbb{Z}$, for every $c\gt 1.$ Consequently, $a_1\uparrow a_2\uparrow\dots a_{s}\uparrow x\pmod k$ is independent of the value of $x\in\mathbb{Z_+}$, provided $s\gt h(k)$.
Here $\ h(k) := \min\{s: \lambda^s(k) = 1\},$ where $\lambda()$ is the Carmichael function; e.g., $h(10^d)=d+2$ for $d\ge 1,$ as proved [here].
Thus, the corollary guarantees that at least $d$ rightmost decimal digits of $3\uparrow\uparrow n$ are "stable" if $n\gt d+2.$ (Your list suggests that $n\gt d+2$ is actually enough to stabilize $d+2$ digits.)