Results 1 to 3 of 3

Thread: Diagrams for Hofstadter M/F Functions, Anyone?

  1. #1
    Member
    Joined
    Aug 2011
    Posts
    128

    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?

    Thanks for your eyes!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2015
    From
    Seattle
    Posts
    1

    Cool 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:
    Diagrams for Hofstadter M/F Functions, Anyone?-diagramm.jpg

    Diagram F:
    Diagrams for Hofstadter M/F Functions, Anyone?-diagramf.jpg
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2011
    Posts
    128

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Diagrams
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 7th 2010, 10:47 AM
  2. Vin diagrams? is there any other way..
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 25th 2009, 03:34 PM
  3. relationship b/w diagrams
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: April 5th 2009, 09:57 AM
  4. draw diagrams
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: April 4th 2008, 02:23 PM
  5. Using tree diagrams
    Posted in the Statistics Forum
    Replies: 2
    Last Post: March 23rd 2008, 03:35 AM

Search Tags


/mathhelpforum @mathhelpforum