Tasa de crecimiento del enésimo número natural no construible con n pasos de suma y multiplicación

Question

Mientras jugaba con la idea de las funciones de colapso ordinal, me topé con una interesante función simple:

$$C(0)=\{0,1\}\\C(n+1)=C(n)\cup\{\gamma+\delta:\gamma,\delta\in C(n)\}\\\psi(n)=\min\{k\notin C(n),k>0\}$$

La explicación es sencilla. Empezamos con $\{0,1\}$ y se añaden repetidamente sus elementos a sí mismos:

$C(1)=\{0,1,2\}\\ C(2)=\{0,1,2,3,4\}\\ C(3)=\{0,1,2,3,4,5,6,7,8\}\\\vdots\\C(n)=[0,2^n]$

Y $\psi(n)$ se define como el menor número entero que no está dentro de $C(n)$ que es $2^n+1$ .

---

A continuación, amplié mi función. Imagina toda la misma definición, excepto que ahora tenemos

$$C(n+1)=C(n)\cup\{\gamma+\delta,\color{red}{\gamma\cdot\delta}:\gamma,\delta\in C(n)\}$$

Este simple cambio nos da algo más complicado. Los primeros conjuntos son

$C(1)=\{0,1,2\}\\ C(2)=\{0,1,2,3,4\}\\ C(3)=\{0,1,2,3,4,5,6,7,8,9,12,16\}\\ C(4)=\small\left\{\begin{align}0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 28, 30,\\ 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 60, 63, 64, 72, 80, 81, 84, 96, 108, 112, 128, 144, 192, 256\end{align}\right\}\\ C(5)=\{0,\dots,177,179,\dots\}\\ \vdots$

Si $\psi(n)$ es el número natural más pequeño que no se encuentra en $C(n)$ asintóticamente, ¿cuál es la velocidad de $\psi$ ¿Crecer?

Los primeros valores de $\psi$ son

$$2,3,5,10,26,178,\dots$$

Este es un programa que produce $\psi$ y aquí hay un programa que produce $C$ .

---

Estoy buscando mejores límites y/o fórmulas asintóticas en forma de

$$\psi(n)\approx x^{y^n}$$

Answer 1

Supongamos que $\psi(n)=k+1$ . Por lo tanto, se deduce que

$$\{x:x\in[0,k]\}\subset C(n)$$

Al sumarlos, podemos encontrar que

$$\{k+x:x\in C(n)\}\subset C(n+1)$$

Y así, el límite simple de

$$\psi(n+1)\ge k+k+1=2\psi(n)-1$$

o

$$\psi(n)\ge2^n+1$$

---

Sumando y multiplicando, encontramos que

$$\{k+x,k\cdot x:x\in C(n)\}\subset C(n+1)$$

Y sumando estos de nuevo, encontramos que

$$\{k\cdot x_0+x_1:x_0,x_1\in C(n)\}\subset C(n+2)$$

Que engloba todos los números de $0$ a $k^2+2k$ Por lo tanto

$$\psi(n+2)\ge k^2+2k+1=\psi(n)^2$$

o,

$$\psi(n)\ge2^{2^{n/2}}$$

---

Al sumar y multiplicar en lugar de sólo sumar en el paso anterior, encontramos que

$$\{x_0,x_1k^2:x_0,x_1\in C(n+1)\}\subset C(n+2)$$

Y sumando estos, una vez más, encontramos que

$$\{x_1k^2+x_0:x_0,x_1\in C(n+1)\}\subset C(n+3)$$

que abarcará todos los números de $0$ a $2k^3+2k$ Por lo tanto

$$\psi(n+3)\ge2k^3+2k+1=2\psi(n)^3-6\psi(n)^2+8\psi(n)-3$$

que no es nada bonito, pero como $2\psi(n)\ge1$ para todos $n$ obtenemos

$$\psi(n+3)\ge2(\psi(n)-1)^3$$

Y si $\psi(n)\ge\frac1{1-2^{-1/3}}\approx4.8$ entonces

$$2(\psi(n)-1)^3\ge\psi(n)^3$$

Y así,

$$\psi(n)\ge5^{3^{(n-2)/3}},{\rm~large~enough~}n$$

---

Haciendo esto de nuevo se obtiene

$$\psi(n+4)\ge2k^5+4k^4+2k^3+k^2+2k$$

Y para que sea lo suficientemente grande $k$ ,

$$2k^5+4k^4+2k^3+k^2+2k>(k+1)^5=\psi(n)^5$$

por lo tanto,

$$\psi(n)\ge5^{5^{(n-2)/4}},{\rm~large~enough~}n$$

---

y en general, espero

$$\psi(n)\ge2^{(2^x+1)^{(n-y)/(x+2)}}>2^{2^{x(n-y)/(x+2)}}$$

Para todos $x$ , lo suficientemente grande $n$ y algunos $y$ .

Answer 2

A partir de la respuesta de Simply Beautiful Art, dejemos $A(n)$ ser el mayor miembro de $C(n)$ menos de $\psi(n+1)$ . Entonces, $\psi(n+2) \geq \psi(n+1) + A(n)\psi(n)$ . Si definimos $K = \lim \inf_{n->\infty} \frac{A(n)}{\psi(n)}$ entonces $\psi(n+2) > K\psi(n)\psi(n+1)$ y deberíamos tener eso $\psi = O(b^{\phi^{n}})$ para algunos $b$ .