The Golomb sequence is a self-describing sequence of integers, beginning with 1, wherein each nth term in the sequence specifies the total number of times that n shall occur in the sequence. The first 28 terms of the sequence are:
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9
Considering the sequence as a function, we can state that g(n) is the number of times that n occurs in the sequence.
To clarify the nature of the sequence, let’s note the following:
- Term 1 of the sequence is 1, stipulating that 1 shall occur 1 time.
- Term 2 of the sequence is 2, stipulating that 2 shall occur 2 times.
- Term 3 of the sequence is 2, stipulating that 3 shall occur 2 times.
- Term 9 of the sequence is 5, stipulating that 9 shall occur 5 times.
- In the portion of the sequence displayed above, 9 already occurs 5 times, so the next term in the sequence would be 10.
- Runs of identical terms increase in length over the course of the sequence, therefore, g(n) rises slowly, in fact, ever more slowly as the sequence proceeds.
The following code, written for Processing Python Mode, renders the sequence graphically, with runs of identical terms represented alternately in black and white.
def setup():
size(800, 800)
noLoop()
def draw():
# store part of the Golomb sequence
g = [0, 1, 2, 2] # initialize
i = 3
while len(g) <= width * 60:
g.extend([i] * g[i])
i += 1
# graph the stored portion of the Golomb sequence
c = 255
old_g = 0
for n in range(1, len(g)):
# if g[n] changed, switch the stroke
new_g = g[n]
if new_g != old_g:
if c == 255:
c = 0
else:
c = 255
stroke(c)
old_g = new_g
# represent a g[n] value, wrapping whenever right margin is reached
line(n % width, g[n] - 4, n % width, g[n] + 4)
Screen capture of a portion of the sketch:
The pattern is caused by the gradual change in the lengths of the runs, resulting in a changing spatial relationship between the black and white phases.