Hofstadter's Chaotic Q Sequence

The sequence in question.

Following the recursive function G presented by Hofstader in Gödel, Escher, Bach (p. 137), the author describes a beast of a recursive function whose pattern is rather chaotic.

Function Q(n) describes the value of the node which must be placed under a node with value n:

Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n - 2)) for n > 2,
Q(1) = Q(2) = 1.

The function produces the sequence:

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, ...

The third element in the sequence is 2, so the diagram must have 2 below 3 (2 is a parent of 3).

The tree produced by this recursive definition has been drawn so that the distance of a node from the root (1, in this case), is proportional to its value. This technique helps emphasize the chaotic nature of the jumps made by values in the tree.

Compare to the relatively tame and orderly Hofstadter Function G.

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

.node circle {
  fill: #fff;
  stroke: #000;
  stroke-width: 1px;
}

.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-width: 1.5px;
  stroke-opacity: 0.4;
}

</style>
<svg width="960" height="2000"></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"),
    node, link,
    width = +svg.attr("width"),
    height = +svg.attr("height"),
    padding = 50;

var tree, root,
    max, N = 80,
    y;

svg = svg
    .attr("width", width)
    .attr("height", height)
  .append("g")
    .attr("transform", "translate(" + padding / 2 + ",0)");

y = d3.scaleLinear().range([height, 0]);

/*
  Build Diagram G from algebraic function
*/
tree = d3.tree()
    .size([width - padding, height - padding]);

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

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

max = d3.max(data, function(d) { return +d.name; });
y.domain([0, max + 1]);

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

tree(root);

/*
  Render tree of Diagram G.
*/
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.data.name)
            + "C" + (d.x + d.parent.x) / 2 + "," + y(+d.data.name)
            + " " + (d.x + d.parent.x) / 2 + "," + y(+d.parent.data.name)
            + " " + d.parent.x + "," + y(+d.parent.data.name);
      });

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

node.append("circle")
      .attr("r", 12)

node.append("text")
      .attr("dy", "0.3em")
      .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