Skip to content

Instantly share code, notes, and snippets.

@bmershon

bmershon/.block

Last active March 22, 2017 12:26
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bmershon/1f8e8abe9f54b09c66704bbb468749b2 to your computer and use it in GitHub Desktop.
Save bmershon/1f8e8abe9f54b09c66704bbb468749b2 to your computer and use it in GitHub Desktop.
Download ZIP
Hofstadter's Chaotic Q Sequence
Raw
.block
border: no
license: gpl-3.0
height: 2000
Raw
README.md

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.

Raw
hofstadter.js
(function() {
var Hofstadter;
// Hofstadter's chaotic function Q
// computed using a dynamic programming
function q(n) {
var A = [],
i;
A[0] = 0
A[1] = 1;
A[2] = 1;
for (i = 3; i <= n; i++) {
A[i] = A[i - A[i - 1]] + A[i - A[i - 2]];
}
return A[n];
}
Hofstadter = {};
Hofstadter.function = {};
Hofstadter.function.Q = q;
d3.Hofstadter = Hofstadter;
})();
Raw
index.html
<!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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment