Just For Fun

The Golomb Sequence

In previous blogs, we’ve looked at some interesting integer sequences. We started with the daddy of all integer sequences, the Fibonacci sequence. Then, the Look and Say sequence. Today’s sequence is the Golomb sequence.

The sequence is named after its founder, American mathematician Solomon Golomb. Golomb was not only an accomplished mathematician in number and coding theory – he was also a bit of a pioneer when it comes to board games. He invented Cheskers, a mix between chess and checkers. He also popularised polyominoes (think dominoes but with more than two squares per domino).

How to generate the sequence

The Golomb sequence is sequence A001462 on the OEIS.

The sequence has to begin with 1. It is also a non-decreasing sequence. This means that the next term cannot be smaller than the previous term.

Like the Look and Say sequence we saw in the previous blog, the Golomb sequence is a self-describing sequence. In the Golomb sequence, the nth term of the sequence describes the number of times n appears in the sequence. The reason I like this sequence is that finding the next term of the sequence is basically like a mini logic puzzle.

So, as the first term in the sequence is 1, this means that 1 appears only once in the sequence.

What is the second term in the sequence? Well, if you think about it logically, it has to be 2. Let me explain:

Because 1 only appears once, the second term cannot be 1.
It cannot be 0 either, as the sequence must not decrease.
It cannot be 3 either (or any number greater than 3) because remember – the second term describes the number of times the number 2 appears in the sequence. If we are saying that 2 appears three times in the sequence, then that must mean 2 will appear later in the sequence. But it cannot, as the sequence cannot decrease.

So the only term possible is 2.

The second term is 2, meaning that there are two 2’s in the sequence. So the sequence needs another 2 in it. It has to therefore be the next term as if the sequence increases then it cannot decrease back down to 2.

So the third term is 2.

Since the third term is 2, this means that the sequence must contain two 3’s. The fourth term therefore must be 3, as the sequence as if the sequence goes to 4, it cannot decrease back down to 3 (and therefore the sequence will not be able to contain two 3’s).

So the fourth term is 3.

We need another 3 in the sequence, so the fifth term is also 3.

The fourth term was 3, meaning there are three 4’s – this means that the next three terms must all be 4. So the sixth, seventh and eighth terms are all 4.

The fifth term was 3. This means that the next three terms must all be 5. So the ninth, tenth and eleventh terms are all 5.

Hopefully, you are starting to understand how the sequence works. Here are the first few terms in the sequence:

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, ….

See if you can continue the sequence on yourself.

Golomb’s sequence is not examinable in GCSE or A-Level maths – this blog is just for fun. But if your son or daughter needs some extra help with any aspect of mathematics, book in a free taster session.

Other posts

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.