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


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

  • $\begingroup$ For testing purposes, you could use this program to output $C(n)$. However, the numbers get fairly large fairly fast... $\endgroup$ – Simply Beautiful Art Dec 8 '17 at 23:18
  • 1
    $\begingroup$ 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$. $\endgroup$ – Simply Beautiful Art Dec 8 '17 at 23:32
  • 1
    $\begingroup$ 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$ $\endgroup$ – Masacroso Dec 8 '17 at 23:41
  • 1
    $\begingroup$ But the point is still there. $29$ is the smallest prime $\notin C(4)$, yet $29\times2\in C(5)$. $\endgroup$ – Simply Beautiful Art Dec 9 '17 at 13:01
  • 1
    $\begingroup$ @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! $\endgroup$ – 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$$



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



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


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


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


And thus,


Doing this again gives


And for large enough $k$,




and in general, I'm expecting


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

  • $\begingroup$ How are you getting $\psi(n_4) \ge 2k^5 + 4k^4 + k^2 + 2k$? $\endgroup$ – Deedlit Dec 19 '17 at 6:34
  • $\begingroup$ @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) $\endgroup$ – Simply Beautiful Art Dec 19 '17 at 15:01
  • $\begingroup$ 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? $\endgroup$ – Deedlit Dec 19 '17 at 20:58
  • $\begingroup$ @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)]$$ $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.