Skip to content

Instantly share code, notes, and snippets.

@bmershon
Last active September 27, 2023 10:12
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bmershon/372fe12a6d2b560513b3aa8d6c5a4b31 to your computer and use it in GitHub Desktop.
Save bmershon/372fe12a6d2b560513b3aa8d6c5a4b31 to your computer and use it in GitHub Desktop.
Hofstadter's G Sequence
border: no
height: 960
license: gpl-3.0

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.

(function() {
var Hofstadter;
function g(n) {
var A = [],
i;
A[0] = 0;
A[1] = 1;
for (i = 2; i <= n; i++) {
A[i] = i - A[A[i - 1]];
}
return A[n];
}
Hofstadter = {};
Hofstadter.function = {};
Hofstadter.function.G = g;
d3.Hofstadter = Hofstadter;
})();
<!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>
@cnrmck
Copy link

cnrmck commented Apr 18, 2020

I've spent way too much time trying to figure this out. Do you actually define the algebraic method to flip the tree, and if so can you please share it? I need to sleep this week.

I only see the standard Hofstadter function defined here (A[i] = i - A[A[i - 1]];) but I don't see the method to invert

EDIT: Nvm figured it out

@willa4you
Copy link

The function G produces the sequence:
0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ...

I think you missed a three.

@tchaivorak
Copy link

I've spent way too much time trying to figure this out. Do you actually define the algebraic method to flip the tree, and if so can you please share it? I need to sleep this week.

I only see the standard Hofstadter function defined here (A[i] = i - A[A[i - 1]];) but I don't see the method to invert

EDIT: Nvm figured it out

Is it A[i] = i - A[A[i - 2]] for i>2 ???

@vramesh6760
Copy link

I get this sequence very easily 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12. How do I draw the Diagram G from this sequence?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment