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

  • 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
  • 1
    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
  • 1
    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
  • 1
    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
  • 1
    @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
up vote 3 down vote accepted

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

  • 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 at 22:49

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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