algorithm - OEIS A002845: Número de valores distintos tomados por 2 ^ 2 ^... ^ 2(con n 2 y paréntesis insertados de todas las formas posibles)

numbers sequence

Question

Estoy buscando un algoritmo razonablemente rápido para calcular los términos de la secuencia A002845 OEIS. Permítanme replantear su definición aquí.

Sea ^ el operador exponencial. Considere expresiones de la forma 2 ^ 2 ^ ... ^ 2 que tienen n 2 con paréntesis insertados de todas las formas posibles (el número de paréntesis posibles está dado por números catalanes ). Algunas de estas expresiones tendrán el mismo valor, por ejemplo (2 ^ 2) ^ 2 = 2 ^ (2 ^ 2). Estamos interesados ​​en el número de valores distintos para un n dado.

Existe una solución obvia de fuerza bruta a través del cálculo directo de estas expresiones, pero está claro que el tiempo y el espacio requeridos exceden rápidamente todos los límites razonables, incluso para n relativamente pequeños. Estoy interesado en una solución de tiempo polinomial para este problema.

Answer 1

Creo que la mejor solución aquí involucra programación dinámica, un concepto difícil de entender, pero muy eficiente si se hace correctamente. La idea es minimizar el número de veces que tiene que hacer un determinado cálculo, recordando los resultados de los cálculos que ya ha realizado y luego utilizar este conocimiento para dividir el problema en un subconjunto de problemas más simples.

Por ejemplo, en su ejemplo de 2 ^ (2 ^ 2) = (2 ^ 2) ^ 2, ahora podemos recordar esto como dos cosas que son equivalentes al valor de 16. Así que ahora, cuando veamos esto en 2 ^ (2 ^ (2 ^ 2)) = 2 ^ ((2 ^ 2) ^ 2) podemos identificar rápidamente cada uno de estos como 2 ^ 16, hacer el cálculo una vez, y ahora tenemos dos nuevas ecuaciones para agregar al Lista de valores que nunca tendremos que volver a calcular.

Sin embargo, es posible que esto no ayude mucho cuando terminas con una serie muy larga de preguntas entre paréntesis, con conjuntos de equivalencias aún más largos, te ahorrará tiempo y complejidad, en lo que son cálculos muy largos para una computadora. en números muy grandes. Pseudo código a continuación, me disculpo, este es un código psuedo muy amplio, este problema es bastante difícil, por lo que no quería escribir un algoritmo completo. Realmente esbozó el concepto con más detalle

 sortedEquivalencyVector; //Sorted greatest first, so we are more likely to se longest matches
function(expression)
if(portion of expression exists) //Remember, you can only do this from the end of the expression in toward the middle!
replace value at end of expression that matches with its already computed value
if(simplified version exists in vector) add original expression to vector
else compute value and add it to the vector
end

Answer 2

Un enfoque que es mucho mejor que la fuerza bruta (pero que ciertamente es caro) es usar el concepto de "forma estándar" en el primer documento vinculado. Dada una n , genere cada forma estándar de grado n , evalúela y mantenga todos los valores en un conjunto. Al final, comprueba el tamaño del conjunto.

La gramática para una forma estándar es

S -> (2 ^ P)
P -> (S * P)
P -> S
S -> 2

Comienzas con una S , y al final debes tener n terminales (es decir, 2 s).

Answer 3

Simplemente represente los números en la base iterativa 2: un Num tiene una lista (posiblemente vacía) de hijos distintos x1,...,xp de tipo Num , de modo que Num([x1,...,xp]) == 2^x1 + ... + 2^xp .

Esto define una forma única de escribir un entero no negativo; Recuerda ordenar los exponentes para que la comparación tenga sentido. Las igualdades:

• 2^x + 2^x == 2^(x+1) == Num([x+1])
• 2^x + 2^y == Num([x,y]) cuando x != y
• (2^2^x)^2^y == 2^2^(x+y) == Num([Num([x+y])])

junto con la asociatividad / conmutatividad de la suma le permite agregar números arbitrarios y calcular x^y para los números de la forma 2 ^ 2 ^ k; esta clase de números contiene 2 (con k = 0) y está cerrada bajo ^ por lo que garantiza que todos los números que necesitamos manipular son de esta forma.

Además, las ecualizaciones definidas anteriormente nunca aumentan el número de nodos en el árbol, por lo que todos los Num son de tamaño O(n) .

Entonces, la complejidad del tiempo es en realidad O(C * n^k) que es casi lineal en C (C es el (n-1) -no número catalán).