Hofstadter's G Sequence

The sequence in question.

See also Hofstadter's chaotic Function Q.

In Douglas Hofstadter's book, Gödel, Escher, Bach, a recursive definition is presented for a tree-structure with a few interesting properties (p. 137).

Diagram G gives rise to the Fibonacci numbers if you read the numbers going up the right side of the tree (i.e., (1), 1, 2, 3, 5, 8, 13, 21, ...). To achieve this pattern, we follow a recursive blueprint for building the tree (like a fractal) and number the nodes we construct from left to right as we move "up" in the diagram. The recursive structure can be gleaned by staring at any of the junctures somewhere in the middle of the tree: up and to the left the pattern is replicated; up and to the right, we add a node and then proceed to repeat the pattern of the structure.

Curiously, Diagram G can be described by a recursive algebratic definition that tells us which value we must put under each other value as we build the tree. To build the tree we must:

put 1 under 2
put 2 under 3
put 3 under 4
put 3 under 5
put 4 under 6
put 4 under 7
and so on...

The definition:

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

happens to descibe this pattern. We place a node with value G(n) under a node with value n.

The function G produces the sequence:

0, 1, 1, 2, 3, 4, 4, 5, 6, 6, ...

where the index of each element is n, and the element itself is the value of the node which must be a parent to the node with value n. It is this sequence that is computed using a memoized recursive function and then built into a tree structure so that we can visualize the graphical presentation of the function G.

Note that numbers appear twice when they serve as the parent for two other nodes in the tree.

A challenge Hofstadter poses to the reader involves attempting to find an algebraic definition like the one above which can be used to label the same tree after it has been flipped, as if in a mirror. In other words: we flip the structure of the nodes and then label them, again proceeding left to right as you move up (down the tree). We want a recursive definition which tells us how the values are related to one another. In the case of the original Diagram G, the recursive definition describes the immediate successors for each node in the tree.

It turns out that such a recursive definition for flipped Diagram G is rather tricky to come up with.

<!DOCTYPE html>
<meta charset="utf-8">
<style>

.node circle {
  fill: #000;
}

.node text {
  font: 0.8em sans-serif;
}

.node--internal text {
  text-shadow: 0 1px 0 #fff, 0 -1px 0 #fff, 1px 0 0 #fff, -1px 0 0 #fff;
}

.link {
  fill: none;
  stroke: #555;
  stroke-opacity: 0.4;
  stroke-width: 1.5px;
}

</style>
<svg width="960" height="960"></svg>
<script src="https://d3js.org/d3.v4.0.0-alpha.44.min.js"></script>
<script src="hofstadter.js"></script>
<script>

var svg = d3.select("svg"),
    width = +svg.attr("width"),
    height = +svg.attr("height");

var svg = d3.select("svg")
    .attr("width", width)
    .attr("height", height)
  .append("g")
    .attr("transform", "translate(40,0)");

var y = d3.scaleLinear().domain([0, height]).range([height - 160, 0]);

var g,
    gp,
    generator,
    sequence,
    root,
    N = 56,
    nodes;

/*
  Build Diagram G from recursive algebratic function
*/
var tree = d3.tree()
    .size([width - 160, height - 160]);

sequence = d3.range(N).map(function(d, i) {
  return d3.Hofstadter.function.G(i);
});

nodes = sequence.slice(1).map(function(d, i) {
  var parent = (i === 0) ? "" : d;
  return {name: "" + (i + 1), parent: "" + parent};
});

root = d3.stratify()
       .id(function(d) { return d.name; })
       .parentId(function(d) { return d.parent; })
       (nodes);

tree(root);

/*
  Render tree of Diagram G.
*/
var link = svg.selectAll(".link")
      .data(root.descendants().slice(1))
    .enter().append("path")
      .attr("class", "link")
      .attr("d", function(d) {
        return "M" + d.x + "," + y(d.y)
            + "L" +  d.x  + "," + y(d.parent.y)
            + " " + d.parent.x + "," + y(d.parent.y);
      });

var node = svg.selectAll(".node")
      .data(root.descendants())
    .enter().append("g")
      .attr("class", "node")
      .attr("transform", function(d) { return "translate(" + d.x + "," + y(d.y) + ")"; })

node.append("circle")
      .attr("r", 2.5);

node.append("text")
      .attr("dy", "1em")
      .attr("x", "1em")
      .style("text-anchor", "middle")
      .text(function(d) { return d.id.substring(d.id.lastIndexOf(".") + 1); });

</script>

https://d3js.org/d3.v4.0.0-alpha.44.min.js