Rate of growth

Given that 5 does not appear until around ${\displaystyle 10^{10^{23}}}$, brute force search techniques would never find the first occurrence of a term greater than 4. It has, however, been proven that the sequence contains every natural number.^[2] The exact rate of growth is not known, but is conjectured to grow super-logarithmically, with the first occurrence of any natural ${\displaystyle n}$ positioned near ${\displaystyle 2^{2^{3^{4^{5^{.^{.^{.{n-1}}}}}}}}}$.^[3]

Average value

Though it is known that each natural number occurs at a finite position within the sequence, it has been conjectured that the sequence may have a finite mean. To define this formally on an infinite sequence, where re-ordering of the terms may matter, the conjecture is that:

${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{i=1}^{n}a(i)<\infty }$

Likewise, the density of any given natural number within the sequence is not known.^[1]

First occurrences

As mentioned, the first 4 appears at position 220. The first instance of two consecutive 4's starts at position

255,895,648,634,818,208,370,064,452,304,769,558,261,700,170,817,472,823,

398,081,655,524,438,021,806,620,809,813,295,008,281,436,789,493,636,144.

This number has 108 digits, and was first published by Levi van de Pol.^[4]

Van de Pol also gives an exact formula for the position of the first 5:

${\displaystyle \phi ^{(1)}(5)=\lfloor 1-\epsilon _{1}+\epsilon _{1}\cdot 2^{418090195952691922788353}\rfloor }$

where ${\displaystyle \epsilon _{1}\approx 3.48669886438365597023}$. Expanded out, this number is approximately

${\displaystyle 3.2719044223289929745\cdot 10^{125857689874791897769333}}$

Recursive structure

The sequence can be broken into discrete "block" and "glue" sequences, which can be used to recursively build up the sequence. For example, at the base level, we can define ${\displaystyle B_{1}=1}$ and ${\displaystyle S_{1}=2}$ as the first block and glue sequences, respectively. Together, we can see how they form the beginning of the sequence:

${\displaystyle B_{1}B_{1}S_{1}=1,1,2}$

The next step is to recursively build up the sequence. Define ${\displaystyle B_{2}=B_{1}B_{1}S_{1}}$. Noting that the sequence starts with ${\displaystyle B_{1}B_{1}}$, we can define a glue string ${\displaystyle S_{2}=2,2,3}$ which gives:

${\displaystyle B_{2}B_{2}S_{2}=1,1,2,1,1,2,2,2,3}$

We assigned ${\displaystyle S_{2}}$ to a particular sequence which gives the property that ${\displaystyle B_{2}B_{2}S_{2}B_{2}B_{2}S_{2}}$ also occurs at the top of the sequence.

This process can be continued indefinitely with ${\displaystyle B_{n+1}=B_{n}B_{n}S_{n}}$. It turns out that we can discover a glue string ${\displaystyle S_{n}}$ by noting that ${\displaystyle S_{n}}$ will never have a 1, and that it stops once it reaches the first 1 to follow ${\displaystyle B_{n}B_{n}}$.^[3] It has also been proven that Gijswijt's sequence can be built up in this fashion indefinitely ‒ that is, ${\displaystyle B_{n}}$ and ${\displaystyle S_{n}}$ are always finite in length for any ${\displaystyle n}$.^[2]

Clever manipulation of the glue sequences in this recursive structure can be used to demonstrate that Gijswijt's sequence contains all the natural numbers, among other properties of the sequence.