Hofstadter’s FIGURE-FIGURE Sequences
December 1, 2015
I had too much Thanksgiving; more specifically, the stuffing went bad, and I’ve felt poorly the last few days. In between trips to the bathroom, I picked up my copy of Hofstadter’s GEB and looked again at the FIGURE-FIGURE sequences of Chapter III:
1, 3, 7, 12, 18, 26, 35, 45, 56, 69, …
and
2, 4, 5, 6, 8, 9, 10, 11, 13, 14, …
where the two sequences together contain each of the natural numbers exactly once and the second sequence comprises the differences between the numbers in the first sequence. I love that book; in probably a dozen attempts, I am probably about 5% of the way to the enlightenment it offers.
Your task is to write programs that generate the two sequences. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Haskell:
[…] Problem: Hofstadter’s FIGURE-FIGURE sequences […]
Pyhon:
def r_series(n):
‘Hofstadter’s FIGURE-FIGURE Sequences’
def r(n):
if n<=1:return 1
else:return r(n-1)+s(n-1, r_list)
def s(n, r_list):
if n<=1: return 2
else:
check = False
i=1
while not check:
if s(n-1,r_list)+i not in r_list: break
i+=1
return s(n-1,r_list)+i
r_list=[]
for i in xrange(1,n):r_list.append(r(i))
return r(n)
def s_series(n):
return r_series(n+1) -r_series(n)
print [r_series(x) for x in xrange(1,10)]
print [s_series(x) for x in xrange(1,10)]
Solution in python http://pastebin.com/zCF7b3m6
Ruby solution
figure_seq=[1]
space_seq=[2]
(0..15).each do |x|
figure_item = figure_seq[x]+space_seq[x]
puts figure_item
space_item = space_seq[x].next
figure_seq<<figure_item
until !figure_seq.include? space_item
space_item += 1
end
space_seq<<space_item
end
puts figure_seq.join(" ")
puts space_seq.join(" ")
Here are three solutions, a nice C loop (this is the Bach solution):
#include <stdio.h> void h(int *a, int N) { int *p = a, *q = a+1, n; for (*p = n = 1; q < a+N; q++, n++) { if (n == *p) { p++; n++; } *q = *(q-1) + n; } } int main() { int N = 20, a[N]; h(a,N); for (int i = 0; i < N; i++) { printf("%d ", a[i]); } printf("\n"); }A Gödelian solution in Haskell:
And finally, for Escher, BCM2835 GPU assembler, for a Raspberry Pi:
@praxis: Hope you are feeling better. GEB is fun, haven’t read it for a long time – have added to my Christmas list.
Here’s a single python generator that generates sequence 1 if called with an argument of 1 and the second sequence if called with an argument of 2.
def seq(which): ns = {1:False} n = 1 for d in it.count(1): if ns.pop(d, True): yield n if which == 1 else d n += d ns[n] = False list(it.islice(seq(1), 20)) => [1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260] list(it.islice(seq(2), 20)) => [2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25]@Mike: nice solution and got me thinking about bit representations and run length encoding. Finally came up with this (I think rather fine) Haskell solution, note that “elr” is “rle” backwards and “scanl (+) n s” generates the sequence from n whose (first) differences are s. hof2 is the 1,3,7.. sequence, hof1 is the complement (my previous solutions only generated hof2):
Here’s a better solution, including series h0, the second differences series. The elr function is the same, but rewritten to use basic functions.
def figure1(maxSize): l = [1, 3, 7] adder = 5 index = 2 if maxSize < 3: return l[:maxSize] while len(l) < maxSize: if l[index] != adder: l.append(adder + l[-1]) else: index += 1 adder += 1 return l def figure2(maxSize): l = [2, 4, 5] dontAdd = 7 index = 2 if maxSize < 3: return l[:maxSize] while len(l) < maxSize: if l[-1] + 1 != dontAdd: l.append(l[-1] + 1) else: dontAdd += l[index] index += 1 l.append(l[-1] + 2) return lfigure1(s) generates the first s elements of first sequence and similarly figure2(s)
[…] A quick and dirty, powershell solution to the hofstadters-figure-figure-sequences problem. […]