Home » maths » Hofstadter sequence

On the book Gödel, Escher, Bach: an Eternal Golden Braid, on Chapter III page 73 there is a puzzle on a sequence of numbers:

1  3  7  12  18  26  35  45  56  69  …

The puzzle is about characterising the sequence of numbers, that is, coming up with a way to find the next number of the sequence. You may want to try it yourself before reading the rest of the post.

The section of the chapter where this puzzle belongs talks about Recursive Enumerable Sets vs Recursive Sets. The main point of the chapter is that:

There exist formal systems whose set of non-theorems is not the set of theorems of any formal system.

When the author presents the puzzle, he calls for some reflection on the chapter in order to find a formula that describes the sequence.

Trying to solve that, I started observing the differences between subsequent numbers, which in our case is

2  4  5  6  8  9  10  11  13

And then again I looked at the differences of between those numbers

2  1  1  2  1  1  1  2

Now, this sequence rings a bell. The notes in music have differences in tones and semitones:

si (1/2) do (1/1) re (1/1) mi (1/2) fa (1/1) sol (1/1) la (1/1) si

where 1/2 represents a semitone and 1/1 represents a tone.

If we look carefully, we notice that the last sequence of differences that we found is the same one as the one in tones and semitones where the fractions are reversed.

I thought this could be a solution since one of the main topics of the book is the interplay of music and maths. On the other hand, the discussion on the chapter was not used. By looking up the description of the sequence on the web, I found the Hofstadter sequence. Looking at the sequence, I had doubts that I had found an equivalent definition.

Finally, a simple Python script to check whether the two sequences are the same.

Apparently, they are not equivalent. Moreover, we don’t even know whether the Hofstandter sequence is defined for all n.

Nevertheless, the beginning of the sequence presents a funny coincidence and writing the Python code to check the non-equivalence of the two sequences made me appreciate even more the power of generators in Python.

1. Joaquin says:

Now i may be wrong but i think you went completly overboard.
If you observe the difference between subsequent numbers of the sequence, youll notice that the numbers missing are the ones on the sequence.

1 3 7 12 18 26 35 45 56 69
2 4 5 6 8 9 10 11 13

The seuqence adds the enxt number with n+1 but it checks to see if that number exists in the sequence if it is go to next number if not add that number.

so the next number woudld be 69+(13+1) = 83

• dimle says:

Exactly, this is the right observation to define the sequence that the author implies. I was confused because the values listed on the book didn’t make it that obvious to me that this is the right definition.