Question

Golomb’s self-generating sequence is the unique non-decreasing sequence of positive integers \({a_1},\,{a_2},\,{a_3},...\) that has the property that it contains exactly \({a_k}\) occurrence of \(k\) for each positive integer \(k\).

Find the first 20 terms of Golomb’s self-generating sequence.

Short answer

The first 20 terms of Golomb’s self-generating sequence are \(1,\;2,\;2,\;3,\;3,\;4,\;4,\;4,\;5,\;5,\;5,\;6,\;6,\;6,\;6,\;7,\;7,\;7,\;7,\;8\).

Step-by-step solution

Golomb’s self-generating sequence

Non-decreasing Golomb’s self-generating sequence is given by

\({a_k} \le {a_{k + 1}}\)

Exactly\({a_k}\)occurrences of \(k\)means that if \({a_k} = n\)then \(k\) must appear exactly \(n\) times in a sequence.

Find the first 20 terms of Golomb’s self-generating sequence

Here we have the sequence of positive integers.

So, \({a_1} = 1\)

Therefore, 1 occurs exactly one time in the sequence.

Do not take \({a_2} = 1\) since \({a_1} = 1\).

So, \({a_2} \ge 2\). This suggests 2 appears at least 2 times in sequence.

But if \({a_2} > 2\) 2 will not appear in sequence.

So, \({a_2} = 2\)

Now, 2 appears 2 time in a sequence. So, \({a_3} = 2\)

For\({a_3} = 2\). This suggests 3 appears at least 2 times in sequence

So, \({a_4} = 3\) and \({a_5} = 3\).

For\({a_4} = 3\). This suggests 4 appears at least 3 times in sequence

So, \({a_6} = {a_7} = {a_8} = 4\)

For\({a_5} = 3\). This suggests 5 appears at least 3 times in sequence.

So, \({a_9} = {a_{10}} = {a_{11}} = 5\)

For\({a_6} = 4\). This suggests 6 appears at least 4 times in sequence.

So, \({a_{12}} = {a_{13}} = {a_{14}} = {a_{15}} = 6\)

For\({a_7} = 4\). This suggests 7 appears at least 4 times in sequence.

So, \({a_{16}} = {a_{17}} = {a_{18}} = {a_{19}} = 7\)

For\({a_8} = 4\). This suggests 8 appears at least 4 times in sequence.

So, \({a_{20}} = 8\)

Hence, the first 20 terms of Golomb’s self-generating sequence are\(1,\;2,\;2,\;3,\;3,\;4,\;4,\;4,\;5,\;5,\;5,\;6,\;6,\;6,\;6,\;7,\;7,\;7,\;7,\;8\).