All examples By author By category About

bmershon

Hofstadter's Chaotic Q Sequence

The sequence in question.

Following the recursive function G presented by Hofstader in Gödel, Escher, Bach (p. 137), the author describes a beast of a recursive function whose pattern is rather chaotic.

Function Q(n) describes the value of the node which must be placed under a node with value n:

Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n - 2)) for n > 2,
Q(1) = Q(2) = 1.

The function produces the sequence:

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, ...

The third element in the sequence is 2, so the diagram must have 2 below 3 (2 is a parent of 3).

The tree produced by this recursive definition has been drawn so that the distance of a node from the root (1, in this case), is proportional to its value. This technique helps emphasize the chaotic nature of the jumps made by values in the tree.

Compare to the relatively tame and orderly Hofstadter Function G.