Growth rate of the nth natural number not constructable with n steps of addition and multiplication

While messing around with the idea of ordinal collapsing functions, I stumbled upon an interesting simple function:

$$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\}$$

The explanation is simple. We start with $\{0,1\}$ and repeatedly add it's elements to themselves:

$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]$

And $\psi(n)$ is defined as the smallest integer not within $C(n)$, which is $2^n+1$.

I then extended my function. Imagine all the same definition, except that we now have

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

This simple change gives us something a bit more complicated. The first few sets are

$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$

If $\psi(n)$ is the smallest natural number not found in $C(n)$, asymptotically, how fast does $\psi$ grow?

The first few values of $\psi$ are

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

Here's a program that outputs $\psi$ and here's a program that outputs $C$.

I'm looking for better bounds and/or asymptotic formulas in the form of

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

Solution 1:

Let's suppose that $\psi(n)=k+1$. It thus follows that

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

By adding these together, we may find that

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

And thus, the simple bound of

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

or

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

By adding and multiplying, we find that

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

And by adding these again, we find that

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

Which encompasses all of the numbers from $0$ to $k^2+2k$, hence

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

or,

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

By adding and multiplying instead of just adding in the previous step, we find that

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

And by adding these, once again, we find that

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

which will encompass all of the numbers from $0$ to $2k^3+2k$, hence

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

which is not at all pretty, but since $2\psi(n)\ge1$ for all $n$, we get

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

And if $\psi(n)\ge\frac1{1-2^{-1/3}}\approx4.8$, then

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

And thus,

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

Doing this again gives

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

And for large enough $k$,

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

hence,

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

and in general, I'm expecting

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

For all $x$, large enough $n$, and some $y$.

Solution 2:

Building from Simply Beautiful Art's answer, let $A(n)$ be the greatest member of $C(n)$ less than $\psi(n+1)$. Then, $\psi(n+2) \geq \psi(n+1) + A(n)\psi(n)$. If we define $K = \lim \inf_{n->\infty} \frac{A(n)}{\psi(n)}$, then $\psi(n+2) > K\psi(n)\psi(n+1)$, and we should have that $\psi = O(b^{\phi^{n}})$ for some $b$.