Gijswijt's sequence

In mathematics, Gijswijt's sequence (named after D.C. Gijswijt by Neil Sloane^[1]) is a self-describing sequence where each term counts the maximal number of repeated blocks in the sequence up to 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 $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:

$a(1)=1$
$a(n+1)=k$ , where $k$ is the largest natural number such that the word $a(1)a(2)a(3)...a(n)$ can be written in the form $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.

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 $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$ positioned near $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:

\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 $B_{1}=1$ and $S_{1}=2$ as the first block and sequences, respectively. Together, we can see how they form the beginning of the sequence:

B_{1}B_{1}S_{1}=1,1,2

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

B_{2}B_{2}S_{2}=1,1,2,1,1,2,2,2,3

Notice we assigned $S_{2}$ to a particular sequence which gives the property that $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 $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 $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.

References

1 2 3 "OEIS A090822". OEIS. The OEIS Foundation.
1 2 Gijswijt, D.C. (2006). "A Slow-Growing Sequence Defined by an Unusual Recurrence". arXiv:math/0602498 [math].
1 2 Sloane, Neil. "Seven Staggering Sequences" (PDF). AT&T Shannon Lab. p. 3.

External links

First 50 million terms
A091579 (the lengths of the glue sequences)

This article is issued from Wikipedia - version of the 11/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.