February 1, 2013
Before you can write the program, you have to figure out the rule that produces the sequence. The solution is the R sequence given by:
R1 = 1, Rn = Rn−1 + Sn−1
where Sn is the smallest positive integer not present in R0..n or S0..n−1.
At this point in his book Hofstadter is discussing the figure and ground of two sequences, similar to the foreground and background of an image. He characterizes the two sequences given above as a figure-figure sequence, with no ground, because the two sequences are complements of each other.
The program to calculate the R sequence is on the next page.