7
$\begingroup$

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. enter image description here Could you please help me prove (or disprove) its correctness?

$\endgroup$
  • $\begingroup$ This is base 2 but 2s and 3s instead of ones and zero's $\endgroup$ – user253055 Jul 19 '15 at 18:30
  • $\begingroup$ @AAron It cannot be directly understood as base-2 notation, because sometimes there are leading 2s, and sometimes are leading 3s, and they both are significant. $\endgroup$ – Vladimir Reshetnikov Jul 19 '15 at 22:33
  • $\begingroup$ Oh yeah. Sorry just commenting off first glance $\endgroup$ – user253055 Jul 19 '15 at 22:37
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.