Power tower of infinite height mod n

So this one's been bothering me for a while and I can't figure it out

Define $$^kb$$ as $$b^{b^{b^{...}}}$$ as the power tower of $$b$$ of height $$k$$

What I want to do is understand the behavior of $$\lim_{k \to \infty} {}^kb$$ mod $$n$$, ideally to find a closed form.

Obviously for integers $$b \geq 2$$, $$\lim_{k \to \infty} {}^kb = \infty$$, but there's no reason why $$^kb$$ can't converge mod $$n$$. In fact, if $$b$$ is relatively prime to $$n$$, $$\lambda(n)$$, $$\lambda(\lambda(n))$$, etc. then it definitely will converge because eventually some iteration of $$\lambda^i(n) = 1$$ and so $$b \equiv_{\lambda^i(n)} 0$$. Then, for all $$k \geq i$$, $${}^kb = {}^ib$$. ($$\lambda(n)$$ here referes to carmichael's totient function, and $$\lambda^i(n)$$ refers to the iteration of the function $$i$$ times: $$\lambda(\lambda(\dots\lambda(n)))$$)

I'm pretty sure that it converges for arbitrary $$b$$, $$n$$ but I haven't been able to prove that

Trying some small cases seems surprisingly unhelpful:

$$2^{2^{2^{...}}} \equiv_2 0$$

$$2^{2^{2^{...}}} \equiv_3 1$$

$$2^{2^{2^{...}}} \equiv_4 0$$

$$2^{2^{2^{...}}} \equiv_5 1$$

$$2^{2^{2^{...}}} \equiv_6 4$$

$$2^{2^{2^{...}}} \equiv_7 2$$

$$2^{2^{2^{...}}} \equiv_8 0$$

$$2^{2^{2^{...}}} \equiv_9 7$$

• This is covered well in this article. (I've referenced it in this answer, but you're asking for more.) Apr 13, 2021 at 5:19
• @metamorphy oh, cool! looks like my $\omega$ and $\phi$ is Shapiro's $\omicron$ and $\rho$, respectively. nice to know I was on a shared path! :) Apr 13, 2021 at 5:56

Very interesting question! Here's at least a proof that it converges for any $$b, n$$, though the question of characterizing these numbers is unanswered here.

First, some definitions. Consider $$b\in\mathbb{N}$$. Define $$\omega(b,n),\phi(b,n)$$ to be the least nonnegative integers such that $$b^{\omega(b,n)}b^{\phi(b,n)}\equiv_nb^{\phi(b,n)}$$, with $$\omega(b,n)>0$$.

To see what these numbers are intuitively, consider the sequence $$(b^0,b^1,b^2,\cdots)$$; eventually this will start repeating. $$\omega(b,n)$$ is the period of that repetition, and $$\phi(b,n)$$ is the length until we enter that period for the first time. For example, with $$n=6$$, $$b=2$$, we have $$(1,2,4,2,4,\cdots)$$. $$\phi(b,n)=1$$, and $$\omega(b,n)=2$$. See the end of the post for a graphical depiction.

Define the function $$\text{mod}:\mathbb{Z}\times\mathbb{Z}\times\mathbb{Z}\to \mathbb{Z}$$ to take in a number, a modulus, and an offset, Mathematica-style. $$\text{mod}(x,n,d)$$ is defined to be the least $$a\in \mathbb{Z}$$ such that $$a \equiv_n x$$ and $$a\geq d$$. Note for later that if $$x\equiv_n y$$, then $$\text{mod}(x,n,d)=\text{mod}(y,n,d)$$. Also define $$\text{mod}(x,n):=\text{mod}(x,n,0)$$, and note that $$\text{mod}(\text{mod}(x,n),n,d)=\text{mod}(x,n,d)$$.

Define $$\sigma(b,n)\in\mathbb{Z}$$ to be the value we're looking for, if it exists: the least nonnegative integer $$s$$ such that for some $$k_0$$, we have that for all $$k\geq 0$$, $$\ ^kb\equiv_ns$$.

Let me also introduce the notation $$\text{exp}_b(x):=b^x$$ for clarity.

Now, note that for $$x\geq\phi(b,n)$$, we have $$\text{exp}_b(x)\equiv_n \text{exp}_b(\text{mod}(x, \omega(b,n), \phi(b,n))$$. (To see this, simply expand $$x$$ as $$x=\text{mod}(x, \omega(b,n), \phi(b,n)) + k\omega(b,n)$$ for some $$k$$, and note that we may write $$\text{mod}(x, \omega(b,n), \phi(b,n))=\phi(b,n)+x_0$$ where $$x_0\geq 0$$. Use the definition of $$\omega$$ and $$\phi$$ to get rid of $$k\omega(b,n)$$, and recombine.)

Note that for all $$b,n$$ with $$b>1$$, there is some height $$k$$ such that $$^kb\geq \phi(b,n)$$. Hence we may make use of the note above.

In particular, if and only if it exists, we must have that for some sufficiently high $$k_0$$, $$^kb\equiv_n \sigma(b,n)$$ for all $$k\geq k_0$$. Therefore $$\sigma(b,n)\equiv_n \text{exp}_b(\ ^{k-1}b)\equiv_n\text{exp}_b(\text{mod}(\ ^{k-1}b,\omega(b,n),\phi(b,n)))$$

Induction step (we'll get to the base case later): suppose that $$\sigma(b,m)$$ exists for all $$m. Then using the fact that $$\text{mod}(\ ^{k-1}b,\omega(b,n),\phi(b,n))=\text{mod}(\text{mod}(\ ^{k-1}b,\omega(b,n)),\omega(b,n),\phi(b,n))$$

We may choose $$k$$ sufficiently high such that $$\text{mod}(\ ^{k-1}b,\omega(b,n))\equiv_n \sigma(b,\omega(b,n))$$. Therefore $$\text{mod}(\ ^{k-1}b,\omega(b,n),\phi(b,n)) = \text{mod}(\sigma(b,\omega(b,n)),\omega(b,n),\phi(b,n))$$.

Note that we always have $$\omega(b,n)\leq n-1$$, since $$b$$ can never be both a multiplicative generator of the group and a zero divisor, so the periodic orbit is always missing either $$1$$ or $$0$$.

Then, we can use the induction step, and conclude that $$\sigma(b,\omega(b,n))$$ exists, and that therefore $$\sigma(b,n)$$ does.

(It is easy to check that anything satisfying the equation for $$\sigma(b,n)$$ above must be the limit of $$\ ^kb$$ mod $$n$$, just by unpacking and repacking the definition of $$\sigma$$.)

The base case, that $$\sigma(b,1)$$ exists for any $$b>1$$, is immediate: anything mod $$1$$ is $$0$$, and so all sequences are constant and equal to 0!

Here's some Mathematica code to calculate these numbers. LogRemainder[b, n] is what I've called the function that returns $$\omega$$ and $$\phi$$ in a 2-element list, {ω[b,n], φ[b,n]}. It calls $$\sigma$$ stablepower. It includes a brute-force check for the non-overflow cases.

Still totally mysterious to me, though, is any closed form or deep insight on $$\sigma(b,n)$$; that would be really interesting to see.

(* Brute force: *)

brute[nmax_, bmax_] :=
Table[
Mod[FixedPoint[b^# &, 1, SameTest -> (Mod[#1, n] == Mod[#2, n] &)], n],
{n, 2, nmax}, {b, 2, bmax}]

(* By the above: *)

(* Note that the following definitions are memoized for faster computation,
hence the f[x_] := (f[x] = ...) idiom. *)

LogRemainder[a_, n_] := (LogRemainder[a, n] = LogRemainder0[a, n, Mod[1, n]])

LogRemainder0[a_, n_, acc0_, acc___] :=
If[MemberQ[{acc}, acc0], {First@FirstPosition[{acc}, acc0, {1}],
Length[{acc}] - First@FirstPosition[{acc}, acc0, {1}]},
LogRemainder0[a, n, Mod[a*acc0, n], acc0, acc]]

stablepower[b_, 1] := 0

stablepower[b_, n_] := (stablepower[b, n] =
Mod[b^(Mod[stablepower[b, #1], #1, #2] & @@ LogRemainder[b, n]), n])

(* Check up to 10: *)

Table[stablepower[b, n], {n, 2, 10}, {b, 2, 8}] == brute[10, 8]

(* Out: True *)

(* Print up to 20: *)

Table[stablepower[b, n], {n, 2, 20}, {b, 2, 20}] // Grid

(* Out (note your calculations appearing along the left column,
and the diagonal of 0s when b == n):

0   1   0   1   0   1   0   1   0   1   0   1   0   1   0   1   0   1   0
1   0   1   2   0   1   1   0   1   2   0   1   1   0   1   2   0   1   1
0   3   0   1   0   3   0   1   0   3   0   1   0   3   0   1   0   3   0
1   2   1   0   1   3   1   4   0   1   1   3   1   0   1   2   1   4   0
4   3   4   5   0   1   4   3   4   5   0   1   4   3   4   5   0   1   4
2   6   4   3   1   0   1   1   4   2   1   6   0   1   2   5   1   5   1
0   3   0   5   0   7   0   1   0   3   0   5   0   7   0   1   0   3   0
7   0   4   2   0   7   1   0   1   5   0   4   4   0   7   8   0   1   7
6   7   6   5   6   3   6   9   0   1   6   3   6   5   6   7   6   9   0
9   9   4   1   5   2   3   5   1   0   1   8   3   1   5   8   4   7   1
4   3   4   5   0   7   4   9   4   11  0   1   4   3   4   5   0   7   4
3   1   9   5   1   6   1   1   3   6   1   0   1   8   3   10  1   7   9
2   13  4   3   8   7   8   1   4   9   8   13  0   1   2   5   8   5   8
1   12  1   5   6   13  1   9   10  11  6   13  1   0   1   2   6   4   10
0   11  0   5   0   7   0   9   0   3   0   13  0   15  0   1   0   11  0
1   7   1   14  1   12  1   9   1   5   1   13  1   8   1   0   1   8   1
16  9   4   11  0   7   10  9   10  5   0   13  4   9   16  17  0   1   16
5   18  9   6   1   7   11  1   9   7   1   15  17  18  17  9   1   0   1
16  7   16  5   16  3   16  9   0   11  16  13  16  15  16  17  16  19  0

*)


Just for fun, here's a depiction of the multiplicative action of $$2$$ in $$\mathbb{Z}\ /\ 20\mathbb{Z}$$. Each arrow denotes multiplication by $$2$$, and here we have $$\omega(2,20)=4,\phi(2,20)=2$$. The sequence $$(2^0,2^1,2^2,\cdots)$$ is highlighted; one can see the $$1,2$$ entry into the cycle, and then the $$4,8,16,12$$ cycle. The code to produce it is below.

Maction[a_, n_] := Table[i -> Mod[i*a, n], {i, 0, n - 1}]

Orbit[b_, n_] := NestList[Mod[2*#, n] &, 1, Total[LogRemainder[b, n]]]

GraphOrbit[b_, n_] :=
Graph[Maction[b, n], VertexLabels -> Automatic,
GraphLayout -> {"PackingLayout" -> "NestedGrid"},
GraphHighlight -> Most[Orbit[b, n]]~Join~BlockMap[Rule @@ # &, Orbit[b, n], 2, 1]]

GraphOrbit[2, 20]