See first the file FunG for the study of:

• G (S n) + G (G n) = S n
• G 0 = 0

and the associated tree where nodes are labeled breadth-first from left to right. Now, question by Hofstadter: what if we still label the nodes from right to left, but for the mirror tree ? What is the algebraic definition of the "parent" function for this flipped tree ?

9 10 11 12  13
 \/   |  \ /
  6   7   8
   \   \ /
    4   5
     \ /
      3
      |
      2
      |
      1

References:

• Hofstadter's book: Goedel, Escher, Bach, page 137.
• Sequence A123070 on the Online Encyclopedia of Integer Sequences http://oeis.org/A123070

The flip function

If we label the node from right to left, the effect on node numbers is the flip function below. The idea is to map a row [1+fib (k+1);...;fib (k+2)] to the flipped row [fib (k+2);...;1+fib (k+1)] .

Two special cases : leftmost and rightmost node at a given depth

flip is involutive (and hence a bijection)

flip and neighbors

The fg function corresponding to the flipped G tree

This equation, along with initial values up to n=3, characterizes fg entirely. It can hence be used to give an algebraic recursive definition to fg, answering the Hofstader's question.

fg and the shape of its tree

We already know that fg is onto, hence each node has at least a child. Moreover, fg_max_two_antecedents says that we have at most two children per node.

We could even exhibit at least one child for each node

rightmost son, always there

leftmost son, always there (but might be equal to the rightmost son for unary nodes)

Hence the shape of the fg tree is a repetition of this pattern:

    r
    |
    p   q
     \ /
      n

where n and q and r are binary nodes and p is unary. As expected, this is the mirror of the G tree. We hence retrieve the fractal aspect of G, flipped.

Comparison of fg and g

First, a few technical lemmas

Now, the proof that fg(n) is either g(n) or g(n)+1. This proof is split in many cases according to the shape of the Fibonacci decomposition of n.

The main result:

Note: the positions where fg and g differ start at 7 and then are separated by 5 or 8 (see Fib.ThreeOdd_next and related lemmas). Moreover these positions are always unary nodes in G (see FunG.decomp_unary). In fact, the g tree can be turned into the fg tree by repeating the following transformation whenever s below is ThreeOdd:

  r   s t             r s   t
   \ /  |             |  \ /
    p   q   becomes   p   q
     \ /               \ /
      n                 n

In the left pattern above, s is ThreeOdd, hence r and p and n are Two, q is ThreeEven and t is High. Some immediate consequences:

fg and "delta" equations

We can characterize fg via its "delta" (a.k.a increments). Let d(n) = fg(n+1)-fg(n). For n>3 :

• a) if d(n-1) = 0 then d(n) = 1
• b) if d(n-1) ≠ 0 and d(fg(n)) = 0 then d(n) = 1
• c) if d(n-1) ≠ 0 and d(fg(n)) ≠ 0 then d(n) = 0

In fact these deltas are always 0 or 1. FD is a relational presentation of these "delta" equations.

fg is an implementation of FD (hence the only one).

The three situations a) b) c) expressed in terms of fg.

An old auxiliary lemma stating the converse of the c) case

Presentation via a "delta" function

An alternative equation for fg

Another short equation for fg, but this one cannot be used for defining fg recursively :-(

This last equation f(f(n)) + f(n-1) = n for n > 3 is nice and short, but unfortunately it doesn't define a unique function, even if the first values are fixed to 0 1 1 2. For instance:

We will show below that if we require this equation along with a monotonicity constraint, then there is a unique solution (which is hence fg). Study of the alternative equation and its consequences.

Alas, f(n) isn't unique for n>5 (e.g 4 or 5 for n=6)