Torres de energía de $2$ $3$ - en busca de una prueba de

Question

Deje $\uparrow$ denotar el derecho asociativo operador de exponenciación: $a\uparrow b\uparrow c=a\uparrow(b\uparrow c)=a^{b^c}$

---

Hay una secuencia $A248907$ presentado recientemente a OEIS (véase también el $A256179$):

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

Representa todas las torres de energía de los números de $2$$3$, en orden creciente. En otras palabras, se compone de todos los no-vacío finito de cadenas sobre el alfabeto $\{2,3\}$ ordenado de tal manera, que una vez cada cadena de dígitos que se entremezcla con la $\uparrow$ operadores y evaluación de la secuencia de resultados es monótona creciente, es decir,

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

Estoy interesado en un razonablemente eficiente algoritmo para la generación de $n^\text{th}$ elemento $A248907$ (denota $a_n$). Se debe evitar la evaluación directa de torres de energía, de lo contrario sería ejecutar fácilmente en grandes números, que haría que el algoritmo inviable en la práctica.

Tengo un algoritmo recursivo que supongo que hace lo correcto, pero me falta una rigurosa prueba de ello.

• Si $n\le12$, los elementos correspondientes a $a_1\,..\,a_{12}$ $2, 3, 22, 23, 32, 222, 33, 322, 223, 232, 323, 332;$
• De lo contrario, si $n$ es impar, $a_n$ $a_{(n-1)/2}$ con el dígito $2$ antepone a ella;
• De lo contrario, ($n$ es incluso), $a_n$ $a_{(n-2)/2}$ con el dígito $3$ antepone a ella.

Este algoritmo genera la secuencia de un "irregular" del segmento inicial, y un "regular" cola " que consiste de pares de elementos que difieren por el primer dígito ($2$ o $3$, interleaved) que se antepone a los anteriores elementos tomados de forma secuencial a partir de un cierto desplazamiento, cada elemento se utiliza dos veces. Podría usted por favor me ayude a demostrar (o refutar) su corrección?

Answer 1

Aquí es una prueba de que el algoritmo de corrección.

Supongamos que $b_n$ es el valor numérico de la potencia de la torre, cuya cadena de dígitos se denota por a $a_n$ en el algoritmo anterior. A continuación, voy a probar por supuesto-de-valores de inducción que, para todos los $n\ge 6$, $b_{n+1}\ge 1.65 b_n$ y $b_n\ge 12$. Si $6\le n\le 12$, esto es claro por la computación. De lo contrario, si $n$ es impar, vamos a $n=2m+1$; a continuación,$m\ge 6$, $b_n=2^{b_m}$, y $b_{n+1}=3^{b_m}$. Por la hipótesis de inducción, $b_m\ge 12$$b_n\ge 2^{12}\ge 12$, e $b_{n+1}/b_n=(3/2)^{b_m}\ge (3/2)^{12}\ge 1.65.$ Por otro lado, si $n$ es incluso, deje $n=2m+2$; ahora, $m\ge 6$, $b_n=3^{b_m}$, y $b_{n+1}=2^{b_{m+1}}$. Por la hipótesis de inducción, $b_m\ge 12$$b_n\ge 3^{12}\ge 12$. También por la hipótesis de inducción, $b_{m+1}\ge 1.65 b_m$, por lo que $$\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.$$ Esto demuestra que el algoritmo genera torres en orden creciente.

Para demostrar que el algoritmo no se salte ninguna de las torres, supongamos que $S$ es no vacía cadena de $2$s y $3$s. Queremos demostrar que algunos $a_n$ es igual a $S$. Si $S\in\{2,3,22,23,32\}$,$S$$\{a_1,\ldots,a_5\}$. De lo contrario, $S$ debe terminar con un miembro del grupo,$T=\{33, 222, 322, 223, 323, 232,332\}$. Podemos demostrar por inducción sobre la longitud de $S$ que, si $S$ termina con un miembro de $T$, $S=a_m$ algunos $m\ge 6$. Si $S$ es igual a un miembro de $T$,$S\in\{a_6,\ldots,a_{12}\}$. De lo contrario, puede escribir cualquiera de las $S=2 S'$ o $3 S'$ donde $S'$ también termina con un miembro de $T$. Ahora, por la hipótesis de inducción, $S'=a_m$ algunos $m\ge 6$, por lo tanto, si $S=2 S'$,$S=a_{2m+1}$; si $S=3 S'$,$S=a_{2m+2}$. Esto demuestra que el algoritmo genera todas las torres.