# Power tower made of $2$s and $3$s: too high, too soon?

A power tower of a number $x$ is typified by

$$x^{x^{x^{x^{x^{x^{x^{x^{x^x}}}}}}}}.$$

Here, however, we take the liberty of referring to the set $T$ of "$\{2,3\}$-power towers"; i.e., numbers

$$x_1^{x_2^{x_3^{ \cdots\cdots^{x_k}}}},$$

where each $x_h$ is $2$ or $3,$ and $k \geq 2.$ Let $T_2$ be the subset of $T$ consisting of towers rising from $x_1=2.$ Let $R$ be the sequence of ranks of towers in $T_2$ when all the towers in $T$ are jointly ranked. For example, $7 \in R$ means that the $7$th smallest element in $T$ is a power of $2$, not of $3$. (The term jointly ranked is borrowed from statistics: if the numbers in two or more sets are combined and arranged in nondecreasing order, they are said to be jointly ranked.)

The first $15$ terms of $R$ are $$1, 2, 4, 7, 8, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29.$$ What are the next terms?

Note that $T$ can be obtained recursively from $t_2 = \{2^2,2^3,3^2,3^3\}$ by defining

$$t_n =2^{t_{n-1}} \cup 3^{t_{n-1}}$$

for $n \geq 3;$ then $T$ is the union of the sets $t_n$ for $n \geq 2.$

For a top-first version of the problem, change $x_1=2$ to $x_k=2,$ where $k$ is the height of the tower. Then the first $17$ terms are $$1,3,4,6,10,11,12,15,16,19,20,23,24,25,26,27,28,\ldots.$$ Here, too, the question is: what are the next terms?

Added later: Thanks, Yaakov, you are right, so my question is, what are the positions of the numbers in $T_2$ in the sequence in the sequence $(1,2,3,\ldots)$. I have the first $30$ positions (or ranks) and would like to see a method for finding more terms.

It may help to see a list of the first $20$ towers ranked:

$$4 = 2^2$$ $$8 = 2^3$$ $$9 = 3^2$$ $$16 = 2^{2^{2}}$$ $$27 = 3^3$$ $$81 = 3^{2^{2}}$$ $$256 = 2^{2^{3}}$$ $$512 = 2^{3^{2}}$$ $$6561 = 3^{2^{3}}$$ $$19683 = 3^{3^{2}}$$ Continuing with tuple notation instead of tower notation: $(2,2,2,2), (3,2,2,2), (2,3,3), (3,3,3), (2,3,2,2), (3,3,2,2), (2,2,2,3), (3,2,2,3), (2,2,3,2), (3,2,3,2), (2,3,2,3).$

My method, so far, has been by computer sort, which reaches overflow pretty quickly. Surely there must be a more insightful method. A related question: what is the position (or rank) of $(2,2,2,2,2,2)?$

• What does jointly ranked mean? – David Handelman Jan 29 '18 at 14:24
• Jointly ranked means arranged in increasing order: $t_2 = \{4,8,16,256,\ldots\}$ and $t_3 = \{9,27,81,\ldots\},$ so that the joint ranking is $(4,8,9,16,27,81,256,\ldots).$ – Clark Kimberling Jan 29 '18 at 15:12
• $8=2^2$? $9=2^3$?? – Gerry Myerson Jan 29 '18 at 22:07
• I find a certain rough affinity of this question with my question on math.SE about how to order the numbers in the googol-stack-bang-plex hierarchy: math.stackexchange.com/q/72646/413 – Joel David Hamkins Jan 29 '18 at 22:40
• $512=2^{3^3}$? – Gerry Myerson Jan 30 '18 at 1:30

Let $s_1=2^2$, $s_2=2^3$, $s_3=3^2$ and so on. For $i\ge 5$, it holds that $s_{i+1}\ge 2s_i$. This can be proved by induction. Then $s_{2i+3}=2^{s_i}$ and $s_{2i+4}=3^{s_i}$. In particular, all the remaining elements of $R$ are precisely the odd numbers larger than the ones shown, and the solution of the top-first version of the problem consists of sequences of consecutive numbers doubling in length. The rank of $(2,2,2,2,2,2)$ can be found out simply by enumerating the sequences up to it.
• This argument can be extended to completely settle the problem: if two towers have the same length, their relative ranking is determined only by the top $3$ terms; if the towers have different length, the longer one has higher ranking unless the lengths differ by $1$ and the top of the longer tower is $2^{2^2}$, while the top of the shorter is $3^3$. – Yaakov Baruch Feb 3 '18 at 17:18