Una forma interesante de producir enteros positivos

Question

Si definimos $$\cal N _1 := \{ 1\} $$ y por inducción $$\cal N_{n+1}:=\{x\in \mathbb N | \exists a,b \in\cal N_n : x= a+b \text{ or }x=ab \text{ or }x=a^b \}$$ es fácil demostrar que, para cada $m \in \mathbb N\backslash \{0\}$ existe $n\le m$ tal que $m\in \cal N_n$ .

Si definimos $\deg (n):= \min\{m\in \mathbb N | \;n\in\cal N_m\} $ (llamémoslo grado de n ), ¿puede encontrar una forma de calcular el grado de cada entero positivo (que sea al menos mejor que fuerza bruta )?

Answer 1

El problema de la suma justa es ya un problema difícil y objeto de muchas investigaciones. La frase clave que hay que buscar es cadena de adición .

Answer 2

Es muy poco probable, incluso si se elimina la exponenciación y se deja sólo la suma y la multiplicación.

Como dijo Erdos sobre la conjetura de Collatz, "las matemáticas aún no están preparadas para estos problemas". La dificultad estriba en la mezcla de suma y multiplicación, que deja el problema con poca estructura explotable. Otros problemas muy difíciles de esta naturaleza, además de la conjetura de Collatz, son la conjetura de Goldbach, la infinitud de primos de la forma $x^2+1$ etc.

Aunque me sorprendería que existiera una forma fácil de calcular exactamente el grado de un número, por supuesto se puede intentar demostrar los límites. Una mejora obvia para los p.s., para los números compuestos: $$\deg(n) \leq 1+\log_2 \omega(n) + \log_2 \max(P(n), Q(n))$$ donde $P(n)$ es el mayor primo de $n$ y la factorización primaria de $Q(n)$ es la mayor potencia.