Gijswijt's sequence

Key takeaways

Gijswijt's sequence belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Gijswijt's sequence to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Gijswijt's sequence from memory before moving on to harder problems.

Reference excerpt

In mathematics, Gijswijt's sequence (named after Dion Gijswijt by Neil Sloane) 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 10 10 23 {\displaystyle 10^{10^{23}}} 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 of natural numbers:

a ( 1 ) = 1 {\displaystyle a(1)=1} , and

a ( n + 1 ) = k {\displaystyle a(n+1)=k} , where k {\displaystyle k} is the largest natural number such that the word a ( 1 ) a ( 2 ) a ( 3 ) . . . a ( n ) {\displaystyle a(1)a(2)a(3)...a(n)} can be written in the form x y k {\displaystyle xy^{k}} for some words x {\displaystyle x} and y {\displaystyle y} , with y {\displaystyle 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.

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. To define this formally on an infinite sequence, where re-ordering of the terms may matter, it is known that

lim n → ∞ 1 n ∑ i = 1 n a ( i ) ≈ 1.904 < ∞ {\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{i=1}^{n}a(i)\approx 1.904<\infty } . Likewise, it is known that any natural number has a positive density in the sequence.

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Gijswijt's sequence

Start with the simplest possible case. Write down what Gijswijt's sequence claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Gijswijt's sequence before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Gijswijt's sequence ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Gijswijt's sequence

In research: Gijswijt's sequence appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Gijswijt's sequence in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Gijswijt's sequence is common in secondary-school and first-year university syllabi. It links to neighbouring topics Integer sequences, Recurrence relations, so understanding it makes those chapters shorter.
In everyday life: Look for Gijswijt's sequence outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Gijswijt's sequence in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Gijswijt's sequence means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Gijswijt's sequence out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Gijswijt's sequence in simple terms?

In mathematics, Gijswijt's sequence (named after Dion Gijswijt by Neil Sloane) 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…

Why does Gijswijt's sequence matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Gijswijt's sequence?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Gijswijt's sequence.