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:
1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, ... (sequence A090822 in the OEIS)
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. For example, the first 4 appears at the 220th term, and the first 5 appears near the \( {\displaystyle 10^{10^{23}}}\) rd term.[1]
Definition
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:
\( {\displaystyle a(1)=1}, and
\( {\displaystyle a(n+1)=k}, where k is the largest natural number such that the word \( {\displaystyle a(1)a(2)a(3)...a(n)} \) can be written in the form \( {\displaystyle xy^{k}} \) for some words x and y , with y having non-zero length.
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.
Explanation
The sequence begins with 1 by definition. The 1 in the second term then represents the length 1 of the block of 1s that is found immediately before it in the first term. The 2 in the third term represents the length 2 of the block of 1s that are in the first and second term. 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 block of two 1s in the first and second term cannot be considered for the 4th term because they are separated by a different number in the 3rd term.
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. None of these blocks are repeated more than once, so the fifth term is 1. 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. The 2 in the seventh term represents the 2 repetitions of the block "1, 1, 2" spanning terms 1-3 and then 4-6. 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.
Properties
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.
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 n {\displaystyle n} 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]
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:
B 2 B 2 S 2 = 1 , 1 , 2 , 1 , 1 , 2 , 2 , 2 , 3 {\displaystyle B_{2}B_{2}S_{2}=1,1,2,1,1,2,2,2,3} {\displaystyle B_{2}B_{2}S_{2}=1,1,2,1,1,2,2,2,3}
We assigned \( 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 \( S_{n} \) by noting that \( 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, \( B_{n} \) and \( S_{n} \) are always finite in length for any 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.
See also
Look-and-say sequence
Kolakoski sequence
Autogram
References
Sloane, N. J. A. (ed.). "Sequence A090822 (Gijswijt's sequence: a(1) = 1; for n>1, a(n) = largest integer k such that the word a(1)a(2)...a(n-1) is of the form xy^k for words x and y (where y has positive length), i.e., the maximal number of repeating blocks at the end of the sequence so far)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
Gijswijt, D.C. (2006). "A Slow-Growing Sequence Defined by an Unusual Recurrence". arXiv:math/0602498.
Sloane, Neil. "Seven Staggering Sequences" (PDF). AT&T Shannon Lab. p. 3.
External links
First 50 million terms
OEIS sequence A091579 (Lengths of suffix blocks associated with A090822) -- (the lengths of the glue sequences)
OEIS sequence A090822 (Gijswijt's sequence)
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
