### 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.

Pages: 1 2

### 13 Responses to “Hofstadter’s FIGURE-FIGURE Sequences”

1. wert310 said

```fs = g 1 [2..] where g n (x:xs) = (n,x) : g (n+x) (filter (/= (n+x)) xs)
f = map fst fs
s = map snd fs
```
2. […] Problem: Hofstadter’s FIGURE-FIGURE sequences […]

3. sc120 said

Pyhon:

def r_series(n):
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)]

4. vinoth said

Ruby solution

figure_seq=
space_seq=

(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(" ")

5. matthew said

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");
}
```

```import Data.List.Ordered
h = 1 : 3 : scanl (+) 7 (minus [5..] h) :: [Int]
main = print (take 20 h)
```

And finally, for Escher, BCM2835 GPU assembler, for a Raspberry Pi:

```.set N, 64
.set output, ra1
.set first, ra2
.set i, ra3
.set j, ra4
.set n, r1
.set last, r2

mov output, unif # Get address of output

# Set up VPM writes (VPM is sequentially
# accessed internal GPU memory)
mov vw_setup, vpm_setup(0, 1, h32(0,0))

mov j, 64-1
mov last, 1
mov first, 1
mov n, 1
mov i, 1
mov vpm, 1 # First element

:loop
sub.setf -, n, first  # Compare
add.ifz n, n, 1       # Increment if equal
mov vpm, last	      # Add to sequence in VPM
sub j, j, 1
brr.anynz -, :loopend # Branch if not equal
nop # Branch delay
nop
nop

# Read element i from VPM
mov r0, vpm_setup(1, 1, h32(0,0))
mov vr_setup, r0
mov first, vpm

:loopend
mov.setf -, j
brr.anynz -, :loop
nop # Branch delay
nop
nop

# Write sequence out to RAM
mov vw_setup, vdw_setup_0(64, 16, dma_h32(0,0))
mov vw_setup, vdw_setup_1(0)
mov -, vw_wait

:end
mov interrupt, 1;
nop; nop; thrend
nop
nop
```
6. matthew said

@praxis: Hope you are feeling better. GEB is fun, haven’t read it for a long time – have added to my Christmas list.

7. scott said
```x, y = , [2, 4]
l, i, j = 15, 0, 0

for n in range(l):
x.append(x[i] + y[j])
for num in range(max(x[i]+1, y[-1]+1), x[i+1]):
y.append(num)
i += 1
j += 1

print x[:l]
print y[:l]
```
8. Mike said

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]

```
9. matthew said

@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):

```import Data.Function

hof1 = generate (fix ((2:) . elr . map (subtract 2) . tail . generate)) where
generate = scanl (+) 2
elr (0:s) = 2 : elr s
elr (n:s) = 1 : elr (n-1:s)

hof2 = scanl (+) 1 hof1
main = print (take 53 hof2)
```
10. matthew said

Here’s a better solution, including series h0, the second differences series. The elr function is the same, but rewritten to use basic functions.

```import Data.Function

elr = concatMap ((++ ) . (flip replicate 1) . (subtract 2))

h0  = fix (elr . scanl (+) 2) -- http://oeis.org/A056731
h1  = fix (scanl (+) 2 . elr) -- http://oeis.org/A030124
h2  = scanl (+) 1 h1          -- http://oeis.org/A005228

main =
print (take 1000 (scanl (+) 2 h0) == take 1000 h1) >>
print (take 93 h0) >>
print (take 68 h1) >>
print (take 53 h2)
```
```-- True
-- [2,1,1,2,1,1,1,2,1,1,1,1,2,1,1,1,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,
--  1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,
--  1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1]
-- [2,4,5,6,8,9,10,11,13,14,15,16,17,19,20,21,22,23,24,25,27,28,29,30,31,
--  32,33,34,36,37,38,39,40,41,42,43,44,46,47,48,49,50,51,52,53,54,55,57,
--  58,59,60,61,62,63,64,65,66,67,68,70,71,72,73,74,75,76,77,78]
-- [1,3,7,12,18,26,35,45,56,69,83,98,114,131,150,170,191,213,236,260,285,312,
--  340,369,399,430,462,495,529,565,602,640,679,719,760,802,845,889,935,982,
--  1030,1079,1129,1180,1232,1285,1339,1394,1451,1509,1568,1628,1689]
```
11. nitishch said
```def figure1(maxSize):
l = [1, 3, 7]
index = 2
if maxSize < 3:
return l[:maxSize]
while len(l) < maxSize:
else:
index += 1
return l

def figure2(maxSize):
l = [2, 4, 5]
index = 2
if maxSize < 3:
return l[:maxSize]
while len(l) < maxSize:
if l[-1] + 1 != dontAdd:
l.append(l[-1] + 1)
else: