In mathematics, Gijswijt's sequence (named after D.C. Gijswijt by Neil Sloane) is a self-describing sequence where each term counts the maximal number of repeated blocks in the sequence up to that term.
Contents
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
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:
-
a ( 1 ) = 1 -
a ( n + 1 ) = k , wherek is the largest natural number such that the worda ( 1 ) a ( 2 ) a ( 3 ) . . . a ( n ) can be written in the formx y k x andy , withy 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.
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
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:
Likewise, the density of any given natural number within the sequence is not known.
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
The next step is to recursively build up the sequence. Define
Notice we assigned
This process can be continued indefinitely with
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.