In mathematics, Gijswijt's sequence (named after Dion Gijswijt by Neil Sloane[1]) is a self-describing sequence where each term counts the maximum number of repeated blocks of numbers in the sequence immediately preceding that term.
The sequence begins with: The sequence is similar in definition to the Kolakoski sequence, but instead of counting the longest run of single terms, the sequence counts the longest run of blocks of terms of any length.
Gijswijt's sequence is known for its remarkably slow rate of growth.
[1] The process to generate terms in the sequence can be defined by looking at the sequence as a series of letters in the alphabet of natural numbers: The sequence is base-agnostic.
That is, if a run of 10 repeated blocks is found, the next term in the sequence would be a single number 10, not a 1 followed by a 0.
At this point, the sequence decreases for the first time: The 1 in the fourth term represents the length 1 of the block of 2s in the 3rd term, as well as the length 1 of the block "1, 2" spanning the second and third term.
There is no block of any repeated sequence immediately preceding the fourth term that is longer than length 1.
The 1 in the fifth term represents the length 1 of the "repeating" blocks "1" and "2, 1" and "1, 2, 1" and "1, 1, 2, 1" that immediately precede the fifth term.
The 2 in the sixth term represents the length of the repeated block of 1s immediately leading up to the sixth term, namely the ones in the 4th and 5th terms.
This "3-number word" occurs twice immediately leading up to the seventh term - so the value of the seventh term is 2.
The 2 in the eighth term represents the length of the repeated block of 2s immediately leading up to the eighth term, namely the twos in the sixth and seventh terms.
The 3 in the 9th term represents the thrice-repeated block of single 2s immediately leading up to the 9th term, namely the twos in the sixth, seventh, and eighth terms.
Only limited research has focused on Gijswijt's sequence.
As such, very little has been proven about the sequence and many open questions remain unsolved.
Though it is known that each natural number occurs at a finite position within the sequence, it has been shown that the sequence has a finite mean.
To define this formally on an infinite sequence, where re-ordering of the terms may matter, it is known that Likewise, it is known that any natural number has a positive density in the sequence.
[2] In 2006 Gijswijt proved that the sequence contains every natural number.
[3] The sequence grows roughly super-logarithmically, with the first occurrence of any natural
A closed-form expression for the earliest index at which a given positive integer
appears was found by Levi van de Pol, in terms of a constant
Expanded out, this number is approximately The first instance of two consecutive 4's starts at position These numbers both have 108 digits, and were first published by van de Pol.
Noting that the sequence starts with
This process can be continued indefinitely with
It turns out that we can discover a glue string
[4] It has also been proven that Gijswijt's sequence can be built up in this fashion indefinitely ‒ that is,
[3] 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.