1. ## Diagrams for Hofstadter M/F Functions, Anyone?

I'm reading "Godel, Escher, Bach" and note that the author claims there are simple diagrams to functions defined:

M(n) = n - F(M(n-1)), n > 0,
F(n) = n - M(F(n-1)), n > 0,
F(0) = 1,
M(0) = 0.

I think I have the answer but it's not as elegant as I expect. The diagrams here for those unfamiliar with the problem involve discovering a recursive structure to the tree graph that forms with a low number as the root. Each node has as its children all the values of n which produce that node by the function.

Here is my solution, upside-down (root at the top) for ease of reproducing it here:

M is (starting from 3):
Code:
  |
--O--
|   |
N   M'
N is:
Code:
|
O
|
N
M' is:
Code:
  |
--O--
|   |
G   M'
and F is simply (starting from 2):
Code:
  |
--O--
|   |
O   F
|
G
If you don't have the book, G is:
Code:
  |
--O--
|   |
O   G
|
G
G is the diagram for G(n) = n - G(G(n-1)), which yields the Fibonacci sequence.

N is a rising tower of non-recursive nodes that forms the Fibonacci sequence exactly. In F, the same sequence is seen along the right side (when you remain in F without switching to G).

1) Have I erred?

2) If not, is there a more elegant approach?

2. ## Re: Diagrams for Hofstadter M/F Functions, Anyone?

I believe this is correct!

I wrote some code in Mathematica to generate the tree:

Code:
treedepth = 9; F[n_] := F[n] = n - M[F[n - 1]]; M[n_] := M[n] = n - F[M[n - 1]]; F[0] = 1; M[0] = 0;
TreePlot[Reverse[Table[i -> F[i], {i, 4, Fibonacci[treedepth + 3]}]], Bottom, VertexLabeling -> True]
TreePlot[Reverse[Table[i -> M[i], {i, 3, Fibonacci[treedepth + 3] - 1}]], Bottom, VertexLabeling -> True]
Diagram M:

Diagram F:

3. ## Re: Diagrams for Hofstadter M/F Functions, Anyone?

Wow, what a blast from the past!

Thanks for the confirmation. I'll have to re-read what I wrote up there to see if it seems to be minimal.