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}$$
 A: 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$.
A: 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$.
