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.

Pages: 1 2

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

  1. wert310 said

    Haskell:

    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):
    ‘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)]

  4. vinoth said

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

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

    A Gödelian solution in Haskell:

    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
    add last, last, n
    mov vpm, last	      # Add to sequence in VPM
    sub j, j, 1
    add n, n, 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))
    add r0, r0, i
    mov vr_setup, r0
    add i, i, 1
    nop # VPM read latency
    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_addr, output
    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 = [1], [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 ((++ [2]) . (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]
        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 l
    
    

    figure1(s) generates the first s elements of first sequence and similarly figure2(s)

  12. […] A quick and dirty, powershell solution to the hofstadters-figure-figure-sequences problem. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: