Diagram G and Recursive Sequences

From Geb

The author poses a problem of flipping diagram G as in a mirror, renumbering the nodes from left to right and finding an algebraic description of the new function. This is the third day I've spent thinking about it. Got it figured out? -- Nope! What troubles me most is that I can't think of any compelling reason why there couldn't be such a function. I spent about a week puzzling over it a couple years ago, shortly after finishing a BS in Mathematics and taking a year-long track in Abstract Algebra. I applied every trick I could think of to it, framing it in terms of recursive functions, digrams and number theory, trying to establish either a function or a proof that there couldn't exist such a function, all to no avail. Maybe some skilled programmer could try to brute-force a solution?


Well, I did finally find a solution. It was in the form I was trying to get at the start and I'm not happy about it, because it doesn't use the trick I figured out.

The solution is an algebraic definition, but it uses helper recursive functions. I was hoping for one recursive function...

It works in terms of diagram G, actually flipping it around.

Define function L:

L(1) = 1

L(n) = L(G(n)) + 1

This is the Level function, for any n, L(n) is the level n is on. 

Example: 
L(19) 
= L(G(19))                    + 1 
= L(12)                       + 1 
= L(G(12))                + 1 + 1 
= L(8)                    + 1 + 1 
= L(G(8))             + 1 + 1 + 1 
= L(5)                + 1 + 1 + 1 
= L(G(5))         + 1 + 1 + 1 + 1
= L(3)            + 1 + 1 + 1 + 1
= L(G(3))     + 1 + 1 + 1 + 1 + 1
= L(2)        + 1 + 1 + 1 + 1 + 1
= L(G(2)) + 1 + 1 + 1 + 1 + 1 + 1
= L(1)    + 1 + 1 + 1 + 1 + 1 + 1
= 1       + 1 + 1 + 1 + 1 + 1 + 1
= 7

The function deposits 1 for each level. L(19) = 7 means that 19 is on the seventh level.

The second helper function is F(n), which gives the nth Fibonacci number. The definition is, of course

F(0) = F(1) = 1

F(n) = F(n-1) + F(n-2)

This is from noting the fact that the rightmost node at level n is the nth Fibonacci number (I defined them here starting at F(0) against convention, it simplifies the expression of the final function).

And you can already see what I am going to tell you.

For each n, we know the number in the rightmost node on its level: it is F(L(n)). And we know the number of nodes in its level: it is F(L(n)) - F(L(n)-1) (except for n=1).

Now we are ready to perform the procedure of flipping. Define another function, M(n). This will mirror-label the nodes in the tree.

M(n) = F(L(n)) - [n - F(L(n)-1)] + 1

Here the term in square brackets is the node's number from the left in its level. The effect of M(n) is counting down [n - F(L(n)-1)] elements from the rightmost node in the tree.

For example, apply it to 19. 19 is the sixth element in the seventh level. If we flipped the diagram, we would label it 16 (the sixth element from the right on that level): 

M(19) = F(L(19)) - [19 - F(L(19)-1)] + 1
      = F(7)     - 19  + F(7-1)      + 1
      = 21       - 19  + 13          + 1
      = 3 + 13
      = 16

As planned.

In the mirror function of G(n), if we want to find the parent of element n, we look for the parent of M(n) in the diagram G and then applying M to this parent will give us the parent in the mirror tree of diagram G.

The summary. MG(n) is the function we want to find, the mirror function of G(n). It is 

MG(n) = M(G(M(n))
    where
      M(1) = 1
      M(n) = F(L(n)) - [n - F(L(n)-1)] + 1
      L(1) = 1
      L(n) = L(G(n)) + 1
      F(0) = 1
      F(1) = 1
      F(n) = F(n-1) + F(n-2)

Note: In the above, we can expand M and we can write F(n) in terms of a sum of exponents of the Golden Ratio (see Wikipedia, Fibonacci numbers). So MG(n) will be in terms of constants, n, G(n) and L(n). What I really wanted, however, was a recursive function in terms of n and MG(k)s for k < n.

Now, the trick I was talking about. It turned out that I didn't realise that Hofstadter mentioned it when he said "And so it goes, for any degree of nesting." after the exposition of diagram H on page 137. What this means to me now is that we can take a sequence of such functions with their corresponding elementary structures forming a progression: 

G(0) = 0
G(n) = n - G(G(n-1))

      G
      |
G     o       =   G       (the circles represent numbers)
|__o__|
   |

H(0) = 0
H(n) = n - H(H(H(n-1)))

      H
      |
      o
      |
H     o       =   H
|__o__|
   |

I(0) = 0
I(n) = n - I(I(I(I(n-1))))

      I
      |
      o
      |
      o
      |
I     o       =   I
|__o__|
   |

J(0) = 0
J(n) = n - J(J(J(J(J(n-1)))))

      J
      |
      o
      |
      o
      |
      o
      |
J     o       =   J
|__o__|
   |

Et cetera

So the number of nodes in the left side is the number of times the function is applied to itself inside itself.

We just have to go one step back and we get: 

Q(0) = 0
Q(n) = n - Q(n-1)

The tree for this function is symmetric. The Nth level has 2^N nodes. The elementary structure of it is 

Q       Q
|___o___|      = Q
    |

So now we need to somehow undo the application of the function onto itself within itself one more time, and nodes will start to appear on the left side of the elementary structure. Then we would get 

X
|
o       X
|___o___|    = X
    |

The function we are looking for. But what is a way of reversing this?

Perhaps, if the G(G(n-1)) term is responsible for adding nodes on the right branch of the elementary structure, there is another term, which adds nodes to the left? I haven't found one.

At this point in thought, I found the function L(n) above and then the solution and stopped looking.

--Evgeni Sergeev


In only a few hours I wrote a Python script that draws trees. Here is the Diagram G script and the Diagram G script output. This was a lot more fun than thinking about girls. --Evgeni Sergeev

Retrieved from "http://editthis.info/geb/Diagram_G_and_Recursive_Sequences"
Personal tools