Power towers of $2$ and $3$ - looking for a proof

Question

Let $\uparrow$ denote the right-associative exponentiation operator: $a\uparrow b\uparrow c=a\uparrow(b\uparrow c)=a^{b^c}$

---

There is a sequence $A248907$ recently submitted to OEIS (see also $A256179$):

$2, 3, 22, 23, 32, 222, 33, 322, 223, 232, 323, 332, 2222, 3222, 233, 333, 2322, ...$

It represents all power towers of numbers $2$ and $3$ in increasing order. In other words, it consists of all non-empty finite strings over the alphabet $\{2,3\}$ ordered in such a way, that once each string of digits is interspersed with the $\uparrow$ operators and evaluated, the sequence of results is monotonically increasing, i.e.

$2=2$
$3=3$
$2\uparrow2=4$
$2\uparrow3=8$
$3\uparrow2=9$
$2\uparrow2\uparrow2=16$
$3\uparrow3=27$
$3\uparrow2\uparrow2=81$
$...$

I'm interested in a reasonably efficient algorithm for generating $n^\text{th}$ element of $A248907$ (denote it $a_n$). It should avoid direct evaluation of power towers, otherwise it would easily run into huge numbers that would make the algorithm unfeasible in practice.

I have a recursive algorithm that I suppose does the right thing, but I lack a rigorous proof of that.

• If $n\le12$, the corresponding elements $a_1\,..\,a_{12}$ are $2, 3, 22, 23, 32, 222, 33, 322, 223, 232, 323, 332;$
• Otherwise, if $n$ is odd, $a_n$ is $a_{(n-1)/2}$ with the digit $2$ prepended to it;
• Otherwise ($n$ is even), $a_n$ is $a_{(n-2)/2}$ with the digit $3$ prepended to it.

This algorithm builds the sequence from an "irregular" initial segment, and a "regular" tail consisting of pairs of elements that differ by the first digit ($2$ or $3$, interleaved) that is prepended to previous elements taken sequentially from a certain offset, each element is used twice. Could you please help me prove (or disprove) its correctness?

Answer 1

Here is a proof of the algorithm's correctness.

Suppose that $b_n$ is the numerical value of the power tower whose string of digits is denoted by $a_n$ in the above algorithm. Then I will prove by course-of-values induction that, for all $n\ge 6$, $b_{n+1}\ge 1.65 b_n$ and $b_n\ge 12$. If $6\le n\le 12$, this is clear by computation. Otherwise, if $n$ is odd, let $n=2m+1$; then $m\ge 6$, $b_n=2^{b_m}$, and $b_{n+1}=3^{b_m}$. By the induction hypothesis, $b_m\ge 12$ so $b_n\ge 2^{12}\ge 12$, and $b_{n+1}/b_n=(3/2)^{b_m}\ge (3/2)^{12}\ge 1.65.$ On the other hand, if $n$ is even, let $n=2m+2$; now, $m\ge 6$, $b_n=3^{b_m}$, and $b_{n+1}=2^{b_{m+1}}$. By the induction hypothesis, $b_m\ge 12$ so $b_n\ge 3^{12}\ge 12$. Also by the induction hypothesis, $b_{m+1}\ge 1.65 b_m$ so $$ \frac{b_{n+1}}{b_n}=\frac{2^{b_{m+1}}}{3^{b_m}}\ge \frac{2^{1.65 b_m}}{3^{b_m}} =(\frac{2^{1.65}}{3})^{b_m}\ge 1.046^{b_m}\ge 1.046^{12}\ge 1.65. $$ This proves that the algorithm generates towers in increasing order.

To prove that the algorithm does not skip any towers, suppose that $S$ is a nonempty string of $2$s and $3$s. We wish to prove that some $a_n$ equals $S$. If $S\in\{2,3,22,23,32\}$, then $S$ is in $\{a_1,\ldots,a_5\}$. Otherwise, $S$ must end with a member of the set $T=\{33, 222, 322, 223, 323, 232,332\}$. We prove by induction on the length of $S$ that, if $S$ ends with a member of $T$, then $S=a_m$ for some $m\ge 6$. If $S$ is equal to a member of $T$, then $S\in\{a_6,\ldots,a_{12}\}$. Otherwise, we can write either $S=2 S'$ or $3 S'$, where $S'$ also ends with a member of $T$. Now, by the induction hypothesis, $S'=a_m$ for some $m\ge 6$, so, if $S=2 S'$, then $S=a_{2m+1}$; if $S=3 S'$, then $S=a_{2m+2}$. This proves that the algorithm generates all towers.