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

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

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

• For testing purposes, you could use this program to output $C(n)$. However, the numbers get fairly large fairly fast... – Simply Beautiful Art Dec 8 '17 at 23:18
• It would seem to me that $C(5)$ contains all of the natural numbers from $0$ to $177$, as well as a lot of other numbers. As long as the gap from one consecutive number to the next is less than $178$, we can fill it by adding all of our numbers to the lower number. The smallest gap I can find in $C(5)$ which is larger than $178$ is above $6000$, and $4^6$ is only $4096$. – Simply Beautiful Art Dec 8 '17 at 23:32
• yes, I see the pattern of the last element of $C(n)$ as $2^1,2^2,2^4,2^8,...$ so a "brutal" upper bound could be $\psi(n)\le 2^{(2^{n-1})}+1$ – Masacroso Dec 8 '17 at 23:41
• But the point is still there. $29$ is the smallest prime $\notin C(4)$, yet $29\times2\in C(5)$. – Simply Beautiful Art Dec 9 '17 at 13:01
• @simply look here just get the gaps and remove additions, they are pretty much familiar prime gaps that are filled with supplementary primes not existing in originated set multiplied by numbers from the same set! my conjecture is that $\phi(n)$ is either a prime not included in $C(n-1)$ or multiplied by a number included in it! – Abr001am Dec 10 '17 at 16:47

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

$$\{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$.

• How are you getting $\psi(n_4) \ge 2k^5 + 4k^4 + k^2 + 2k$? – Deedlit Dec 19 '17 at 6:34
• @Deedlit It's $(k^2+2k)(2k^3+2k)$, that is, we can represent all multiples of $2k^3+2k$ up to that, and the gap may be filled with addition. (IIRC) – Simply Beautiful Art Dec 19 '17 at 15:01
• I'm not quite seeing it... to fill in the gaps by addition, we need all the multiples of $2k^3 + 2k$ by C(n+3), and to get those multiples, we need $2k^3 + 2k$ by C(n+2). How do you get there? – Deedlit Dec 19 '17 at 20:58
• @Deedlit Note that $$[0,k^2+2k]\cup\{2k^3\}\subset C(n+2)\\\implies\{2k^3x_0:x_0\in[0,k^2+2k]\}\subset C(n+3)\\ [0,2k^3+2k]\subset C(n+3)\\ \implies\{2k^3x_0+x_1:x_0\in [0,k^2+2k],x_1\in [0,2k^3+2k]\}\subset C(n+4)\\ [0,2k^3(k^2+2k)+2k^3+2k]\subset C(n+4)]$$ – Simply Beautiful Art Apr 14 '18 at 22:49

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