Recursive Structure of Hofstadter Sequences

I'm slowly (but surely!) making my way through Godel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter. As I've mentioned before, so far it's been quite an awesome, thought-provoking read; exploring some pretty deep ideas from both mathematics and computer science.

One of those deep ideas is that of recursion. Upon introducing the idea with an amusing "story within a story within a story" dialogue, we are shown several peculiar sequences: starting with the G(n), H(n), F(n) and M(n) sequences. These are examples of Hofstadter sequences. The trick to these sequences is not only that they are recursively defined, but that they are, in fact, non-linearly recursive. G and H are both defined in terms of compositions of themselves. Even more strangely, F and M are defined in terms of nested compositions of each other!

The exercise that Hofstadter gives the reader is to determine the recursive structures that can be created by forming a graph of each of the sequences: where we label some nodes '1' through 'n', and let 'n' be the node directly above the node 'G(n)' in the graph. As we'll see, the graphs branch up and out like a tree, and we'll be able to notice some recursive patterns that define the infinite construction of the entire graph.

So let's get to it! To save having to calculate the values of the sequence by hand, we'll code up some recursive functions in Clojure that we can use to easily find the values for each of the Hofstadter sequences.

The G(n) Hofstadter Sequence

The first sequence we are shown is the G(n) sequence, defined as follows.

This translates directly into the following recursive Clojure function.


[Note that we're more concerned with readability over efficiency here, so we won't worry about the fact that we'd easily blow our stack for a sufficiently large value of n by computing the sequence this way. The right way to do it in Clojure would be to use memoization and lazy sequences – actually, Stuart Halloway and Aaron Bedra even use the exact example of the F/M Hofstadter sequences to demonstrate these techniques in their book Programming Clojure!]

We can then use this function to generate a range of values for G(n), as shown below.

     (range 1 (inc 21))
     ;> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21)

     (map g (range 1 (inc 21)))
     ;> (1 1 2 3 3 4 4 5 6 6 7 8 8 9 9 10 11 11 12 12 13)

Now we can actually use this sequence to generate a graph that visualizes the structure of the recursion, as Hofstadter does in the book. What we do is start with a node labeled '1' at the bottom, and for each new node labeled 'n', we place that node directly on top of the one labeled 'G(n)'.

So for instance, if we tabulate n and G(n) just as we calculated them...

  n:    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
  G(n): 1 1 2 3 3 4 4 5 6  6  7  8  8  9  9 10 11 11 12 12 13

Then we can just read it right from the table. So the node '2' goes on top of the node '1', node '3' goes on top of '2', nodes '4' and '5' both go on top of '3', and so on.

When we do this, we'll generate the following graph.

There are some very nice things about this graph. For one, we can immediately notice our old friends the Fibonacci numbers working their way up the right-most branch of the graph. Given the way the graph was constructed, this means that if F_n is the nth Fibonacci number, then G(F_n) = F_n-1, which is interesting.

But more than that, notice that we appear to have the same shape repeating itself over and over as we branch up. Starting from node '3', the entire graph appears to be completely defined by the repetition of this one shape on two branches (I've colour-coded the different occurrences.)

That is, we can define the graph (call it G) recursively. We'll start by isolating the repeated shape, which will be the initial form for G:

And we have that the graph G is defined in terms of itself: we replace the 'G's that appear in the top left and right corners by exact copies of the graph G. And those new copies of G will in turn be defined by more copies of G, and so on. As we repeatedly add more and more copies of G, the graph will branch up and out, as shown.

And we can see that this recursive structure matches up with the one we had for the labeled nodes earlier!

So that's the recursive structure for the G function. But Hofstadter then asks us to consider the mirror-image of the graph of G (with the nodes still labeled from left to right, but we've flipped the structure horizontally).

That is, we are to consider the following graph (which we'll call G_flip):

Now the repeated "shape" for the recursive structure of G_flip is obvious: it's just the mirror-image of the recursive structure for our original graph G.

However, suppose we wanted to derive the recursive function that we may have used to build this graph?

We had that the graph G was built from the function G(n) = n - G(G(n-1)). If we rearrange that equation slightly, we can get n = G(n) + G(G(n-1)). Then given that we define n to be the number of the node on top of G(n) in the graph, we can see that this equation is actually telling us an invariant for the graph:

1. Pick any node n (for example, n = 6).
2. Note the node directly beneath n (ie. the node G(n), which is G(6) = 4 for our example.)
3. We move to the node n-1 (eg. n = 5 in our example: in our case, we've moved off of the left-hand side of the graph and circled back around to the right-hand side.)
4. Then we consider the node that is exactly two nodes down from node n-1. That is, since G(n-1) is the node directly below n-1, we want G(G(n-1)), the next node down. (In our example, G(G(5)) = G(3) = 2.)
5. And here's the invariant: that node, when added to the node we made a note of in step 2, must always gives us n; ie. G(n) + G(G(n-1)) = n. (In our example, 2 + 4 = 6, so this holds.)

So we can use this procedure to suggest a way that we might find an equation for the invariant of the graph of G_flip. After trying different things and messing around a bit, we can arrive at the following "solution" for the invariant:

1. If we pick a node n,
2. Then the node directly beneath the node n-1, ie. G_flip(n-1) ...
3. ... when added to the node obtained by moving two nodes down from n, ie. G_flip(G_flip(n)) ...
4. ... must add up to n, ie. G_flip(n-1) + G_flip(G_flip(n)) = n.

So we have G_flip(n-1) + G_flip(G_flip(n)) = n for our invariant.

If we make a quick visual check on the above diagram, this does appear to be a valid invariant – at least for the nodes above node '3'. And it's sort of symmetric with the original function G(n) too, so that's nice.

But there's a problem with our formula, right? We can't rearrange that equation to get an expression for G_flip(n). Shifting our index n forward isn't going to help us, and to get at that nested G_flip(n) term we'd need to have a sensible inverse function G_flip^-1(n) defined, which the graph already tells us is impossible. (For instance, G_flip(9) = 6 and G_flip(10) = 6, so what is G_flip^-1(6)? Is it 9, or is it 10? It can't be both.)

It actually seems to be very difficult to find a properly recursive formula to generate the graph of G_flip, which is sort of surprising given that G has a relatively nice recursive formula. I've certainly spent a good few hours trying, with no luck. Perhaps it's not even possible?

The H(n) Hofstadter Sequence

Next we are given the H(n) sequence, which looks like this:

It's very similar to the G(n) sequence, except that we have another level of recursive nesting.

Once again, the translation into a working Clojure function is mechanical.


We can easily get the first 28 values for H(n) by mapping the function over the range [1, 28]:

     (range 1 (inc 28))
     ;> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
     ;> 23 24 25 26 27 28)
 
     (map h (range 1 (inc 28)))
     ;> (1 1 2 3 4 4 5 5 6 7 7 8 9 10 10 11 12 13 13 14 14 15 16 
     ;> 17 17 18 18 19)

And just like with the G(n) function, the H(n) function can be used to generate a graph. We do the same thing we did before by making sure that the node labeled 'n' is always directly above the node labeled 'H(n)'.

So we'll tabulate the values like before:

  n:    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
  H(n): 1 1 2 3 4 4 5 5 6  7  7  8  9 10 10 11 12 13 13 14 14 15

  n:    23 24 25 26 27 28
  H(n): 16 17 17 18 18 19

And then we can use this table to help us draw the following graph:

Once again, we can see a repeating pattern here that defines the entire graph, from node '4' onwards. (We also have a sort of "elongated Fibonacci sequence" appearing on the right-hand side, where each node is the sum of the node directly below it together with the node that is two nodes below it (so working our way up from node '4' at the bottom, we have 4 = 3 + 1, 6 = 4 + 2, 9 = 6 + 3, 13 = 9 + 4, and so on.))

So we can define the graph for H(n), which we'll call H, using the following building block:

The repeated shape for the graph of H(n) looks very similar to the one for G(n), but we have an extra node on the right-hand branch each time. Our graph will grow up and out as we add on more copies of H, just like the graph G did.

But let's consider the mirror-image of H, which we'll call H_flip:

Given the similarities between the graphs G and H, we might expect there to be corresponding similarities between the graphs G_flip and H_flip. More precisely, since we had the invariant G_flip(n-1) + G_flip(G_flip(n)) = n for the G_flip graph, we might immediately wonder whether the same sort of symmetrical equation for H_flip works, ie.
H_flip(n-1) + H_flip(H_flip(H_flip(n))) = n.

Sure enough, it holds! So this expression does indeed describe the invariant for the graph H_flip. However, we've still got the same problem that we had before. This recurrence equation can't converge to our base case as it is, and we can't rewrite it into an expression for H_flip(n). So unfortunately, this means that we can't actually use this equation to generate the graph.

(Since the graphs G_flip and H_flip are quite similar, we also expect that finding a recursive algebraic equation for H_flip should pose the same amount of difficulty as we saw when we tried to find an expression for G_flip. So we'll quietly move along; besides, we've got some other interesting sequences to look at!)

The F(n) and M(n) Hofstadter Sequences

Here's an interesting pair of sequences. Note that they are recursively intertwined and defined in terms of each other:

We can write these sequences as mutually-recursive Clojure functions (note that we have to use a forward declaration here.)


Then we can use these functions to produce the first 33-34 values for each sequence as follows.

We'll look at the graph for F(n) first. We can use our Clojure function f to generate the first 34 values by mapping over the range [1, 34]:

     (range 1 (inc 34))
     ;> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
     ;> 23 24 25 26 27 28 29 30 31 32 33 34)

     (map f (range 1 (inc 34)))
     ;> (1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 13 14 14 15
     ;> 16 16 17 17 18 19 19 20 21 21)

We can then tabulate these, and use the table to help us draw the graph for F(n), which we'll denote by F.

The table is as follows:

  n:    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
  F(n): 1 2 2 3 3 4 5 5 6  6  7  8  8  9  9 10 11 11 12 13 13 14 

  n:    23 24 25 26 27 28 29 30 31 32 33 34
  F(n): 14 15 16 16 17 17 18 19 19 20 21 21

Using the values from the table (with the same convention of placing n above F(n), at least for the larger values of n (we won't worry too much about the fact that the nodes '1', '2' and '3' don't seem to work too well with this idea)), we arrive at the following diagram:

We can notice a peculiar pair of repeated patterns here. We have one of the shapes repeating itself over and over on the right-hand branch (which I've coloured in shades of blue in the graph). But check out the shape that's repeating itself on the left branch each time (which I've coloured in red.) Does it look familiar?

Yep! On the left-hand branch, we have the same graph G that we were working with at the start of this blog post!

Perhaps it's a little surprising that we have G showing up in the graph for an apparently unrelated function F(n). But if we look back at the function G(n) for a comparison, we can see that F(n) and G(n) are kind of similar: the only difference is that F(n) makes a call to the function M(n) for its outer recursive call.

So the recursive building block for the graph F is as follows:

Finally, we'll look at the function M(n). Mapping our function m over the range [1, 33] at the Clojure REPL, we get the following:

     (range 1 (inc 33))
     ;> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
     ;> 23 24 25 26 27 28 29 30 31 32 33)
 
     (map m (range 1 (inc 33)))
     ;> (0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 13 14 14 15 
     ;> 16 16 17 17 18 19 19 20 20)

These values can be tabulated as follows.

  n:    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
  M(n): 0 1 2 2 3 4 4 5 6  6  7  7  8  9  9 10 11 11 12 12 13 14 

  n:    23 24 25 26 27 28 29 30 31 32 33
  M(n): 14 15 16 16 17 17 18 19 19 20 20

And so the graph M for the function M(n) looks like this:

Once again, we've got a repeated pattern that builds up on the right-hand branch each time from node '4' onwards (which I've coloured blue), and at each point, we've got the graph for G appearing on the left branch (in red.)

Notice that we also have the very conspicuous tower of Fibonacci numbers appearing on the left-hand side, which is kind of cool. This means that the function M(n) has the same interesting property that the function G(n) did: if F_n is the nth Fibonacci number, then M(F_n) = F_n-1.

Finally, we can note that the graph M is built up recursively from the following base:

To some extent, we can think of the G graph that appears in both the F and M graphs as hinting at the interaction between the two, due to the mutual recursion between the functions F(n) and M(n).

As one last note, we can make a remark on the simplicity of the recursive structures here, particularly with these last two intertwined functions F(n) and M(n). The recursive building blocks are quite elegant, given how convoluted the recurrence equations were.

So we've seen some pretty neat recursive structures so far. In his book, Hofstadter goes on to talk about another recursive sequence Q(n) that has the weird property that it bounces around chaotically as the value of n grows larger.  In fact, not a lot is known about the behaviour of this sequence at all. Perhaps we ought to explore it in a future blog post?