In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Gijswijt's sequence (named after
Dion Gijswijt by
Neil Sloane
__NOTOC__
Neil James Alexander Sloane FLSW (born October 10, 1939) is a British-American mathematician. His major contributions are in the fields of combinatorics, error-correcting codes, and sphere packing. Sloane is best known for being the cre ...
) is a
self-describing sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
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, ...
The sequence is similar in definition to the
Kolakoski sequence
In mathematics, the Kolakoski sequence, sometimes also known as the Oldenburger–Kolakoski sequence, is an infinite sequence of symbols that is the sequence of run lengths in its own run-length encoding. It is named after the recreational math ...
, 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
rd term.
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
An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...
of
natural numbers
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...
:
#
, and
#
, where
is the largest natural number such that the word
can be written in the form
for some words
and
, with
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.
Average value
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
A mean is a quantity representing the "center" of a collection of numbers and is intermediate to the extreme values of the set of numbers. There are several kinds of means (or "measures of central tendency") in mathematics, especially in statist ...
. 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
Density (volumetric mass density or specific mass) is the ratio of a substance's mass to its volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' (or ''d'') can also be u ...
in the sequence.
Rate of growth and first occurrences
In 2006 Gijswijt proved that the sequence contains every natural number.
The sequence grows roughly
super-logarithmically, with the first occurrence of any natural
positioned at approximately
. 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
and a sequence of constants
.
For example, the position of the first 5 is given by
:
where
. Expanded out, this number is approximately
:
.
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 van de Pol.
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
and
as the first block and glue sequences, respectively. Together, we can see how they form the beginning of the sequence:
:
The next step is to recursively build up the sequence. Define
. Noting that the sequence starts with
, we can define a glue string
which gives:
:
We assigned
to a particular sequence which gives the property that
also occurs at the top of the sequence.
This process can be continued indefinitely with
. It turns out that we can discover a glue string
by noting that
will never have a 1, and that it stops once it reaches the first 1 to follow
.
It has also been proven that Gijswijt's sequence can be built up in this fashion indefinitely ‒ that is,
and
are always finite in length for any
.
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
In mathematics, the look-and-say sequence is the integer sequence, sequence of integers beginning as follows:
: 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, ... .
To generate a member of the sequence from the previous ...
*
Kolakoski sequence
In mathematics, the Kolakoski sequence, sometimes also known as the Oldenburger–Kolakoski sequence, is an infinite sequence of symbols that is the sequence of run lengths in its own run-length encoding. It is named after the recreational math ...
*
Autogram
An autogram ( = self, = letter) is a sentence that describes itself in the sense of providing an inventory of its own characters. They were invented by Lee Sallows, who also coined the word ''autogram''. An essential feature is the use of full ca ...
References
External links
First 50 million terms* -- (the lengths of the glue sequences)
: {{OEIS el, 1=A090822, 2=Gijswijt's sequence, formalname=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
Parity (mathematics)