Generate Hofstadter's Figure-Figure Sequence

Question

In Gödel, Escher, Bach, Douglas Hofstadter introduces an integer sequence which is commonly referred to as the figure-figure sequence:

2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ...

You may enjoy working out the definition of the sequence yourself as part of the challenge, but if you can't or don't want to figure it out you can find it on OEIS as sequence A030124 and a slightly clearer definition on Wikipedia.

Write a program or function which, given n via STDIN, ARGV or function argument, prints a list of the first n numbers of the sequence to STDOUT in any reasonable list format.

This is code golf, the shortest solution in bytes wins.

Answer 1

CJam, 38 30 29 21 bytes

li_3*,2>\{(_pX+:X-}*;

Try it online.

How it works

li                     " Read an integer N from STDIN.              ";
  _3*,2>               " Push S := [ 2 3 ... (N * 3 - 1) ].         ";
        \{        }*   " Do the following N times:                  ";
          (            " Shift an integer I from S.                 ";
           _p          " Print a copy of I, followed by a linefeed. ";
             X+:X      " Execute X += I. (X is initialized to 1.)   ";
                 -     " Remove X from S.                           ";
                    ;  " Discard S from the stack.                  ";

Example run

$ cjam <(echo 'li_3*,2>\{(_pX+:X-}*;') <<< 20
2
4
5
6
8
9
10
11
13
14
15
16
17
19
20
21
22
23
24
25

Answer 2

Haskell, 67 61 60 56 55 53 characters

g n=take n$2:4:h
a#(x:s)=[a..x-2]++x#s
h=5#scanl(+)8h

back to the first algorithm.

this solution computes the complement sequence by summing the starting elements of the sequence. it then computes the sequence as all the numbers between the complement's sequence numbers.

(#) is the function that calculates the numbers between the complement sequence.
h is the sequence itself.
g is the function that answers the question.

the g function is defined to just take the needed amount of elements from h.

subtleties:

h is actually the figure figure sequence except for the first 2 elements.
not the complement sequence is computed, but the complement sequence with added 1 for each element.
these two subtleties are the reason scanl(+)8h (which is the code for the complement sequence (except for the first 2 elements) with added 1's) has 8 in it. it is for the third element of the complement sequence with 1 added to it.
the reason the computation is not missing the first two elements is because they are added in g in 2:4:h.

example:

>g 50
[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]

Answer 3

Ruby, 54 48

f=->n{x=1
b=*2..n*n
n.times{b-=[x+=p(b.shift)]}}

Demo

Edit: Golfed this a bit more once I realized I don't need to hold the full complement sequence in memory. Here's how it works now: We use x to keep track of the largest computed number in the complement sequence, and b is a pool of candidates for the sequence. n times, we output the smallest remaining element in b and add it to x to compute the next number in the complement sequence. Then we remove both numbers from the pool of candidates, so we're always outputting the smallest number that wasn't already added to either sequence.

Ruby golf tricks: Stabby lambda syntax is shorter than a method definition. The requirement that output is given to STDOUT instead of as return value inspired me to use the fact that the return value of p(x) is x, which I don't normally remember because it's not the case in the Ruby version used in Anarchy Golf.

Answer 4

GolfScript (24 21 bytes)

~.3*,1>\{(\(.p@+\|}*;

Online demo

This started out quite differently, but ended up converging on a GolfScript port of histocrat's Ruby solution before Dennis made some suggestions which take it in a slightly different direction. In particular, printing the numbers as we identify them saves quite a bit over gathering them in an array for printing at the end; the reason is that it means that at no point do we have to worry about more than 3 items on the stack.

Dissection

~.3*,           # Eval input n, dup, multiply by 3, make list [0 1 ... 3n-1]
1>              # Discard 0, which is part of neither sequence
\{              # Execute n times: stack contains pool of numbers not yet seen
                # in either sequence and the first element of it is the next element of the
                # complement sequence
  (\(           #   Pop two numbers from the start of the pool: stack is
                #     pool[0] pool[2..max] pool[1]
  .p            #   Print pool[1]
  @+            #   Rotate pool[0] to top and add to pool[1]
  \|            #   Place pool[0]+pool[1] at the start of the pool and
                #   (this is the clever bit) remove it from later in the pool
}*
;               # Discard the unused remainder of the pool

Answer 5

J - 28 char

Function taking n as argument.

($+/\(-.~2+i.)&:>:+/)^:_&2 4

We run a function, with n as left argument, onto its right argument repeatedly until it produces no change. The argument to start is the list 2 4.

In the function itself, we take the partial sums +/\ and the full sum +/, and then increment them both with &:>:. We then generate every integer from 2 to the one more than full sum (2+i.), and set subtract (-.) the partial sums, leaving a longer figure-figure sequence by definition. Finally, we shorten or cyclically extend the list to length n.

The result is that 2 4 becomes 3 7, and this is removed from 2..8 leaving 2 4 5 6 8. After another round, 2 4 5 6 8 becomes 3 7 12 18 26 becomes

2 4 5 6 8 9 10 11 13 14 15 16 17 19 20 21 22 23 24 25 27

In this way, we repeatedly extend the figure-figure sequence. The $ length behaviour is just a non-trivial character saving way of waiting for the sequence to grow to length n or greater, and outputting the n first values when they stop changing. We don't have to wait very long, either: we can get as many as 46336 terms from four applications of the inner verb.

The same function in k:

• k2, 37 chars: {{x#y@&~_lin[y:1+!1+/y;1+\y]}[x]/2 4}
• k4, 36 chars: {{x#y@&~(y:2+!1+/y)in\:1+\y}[x]/2 4}

Answer 6

Java - 183 158

This was the most I have ever golfed anything, and I am proud of it! (Although it is nowhere near the top of the charts(because it's Java))

Thanks to Peter Taylor for suggestions

class f{public static void main(String[]a){int q=1,m=Byte.valueOf(a[0]),w=2,n[]=new int[m*m*2];for(n[q+=w]=1;m-->0;){System.out.println(w);for(;n[++w]>0;);}}}

bigger -

public class f {
    public static void main(String[] a) {
        int q = 1, m = Byte.valueOf(a[0]), w = 2, n[] = new int[m * m * 2];
        for (n[q += w] = 1; m-- > 0;) {
            System.out.println(w);
            for (; n[++w] > 0;)
                ;
        }
    }
}

Answer 7

Python 2 -- 77 bytes

---

Code:

n=input();x=1;b=range(2,n*n)
while n:v=b.pop(0);x+=v;print v;b.remove(x);n-=1

Works the same as @histocrat's solution, except input comes from stdin.

Answer 8

Python 2 - 68

R=[1]
s=0
n=input()
while n:s+=1+(s+1in R);R+=[R[-1]+s];print s;n-=1

Answer 9

Jelly, 15 bytes

SƤŻ‘µṀ‘Rḟ
2dz¡ḣ

Try it online!

Memory error at the input of 6.

How it works

SƤŻ‘µṀ‘Rḟ  Aux. link (monad). Input: part of the desired sequence
SƤŻ‘       Sum of prefixes, then prepend a zero and increment
           This is a list of numbers to exclude from the next iteration
    µ      Re-focus on the above
     Ṁ‘Rḟ  Create range 1..Max + 1, then remove all elements of the above
           +1 is needed to progress from [2] to [2,4]

2dz¡ḣ  Main link (monad). Input: n, number of terms
2dz¡   Starting from 2, apply aux. link n times
    ḣ  Take n elements from the beginning

More efficient version, 16 bytes

SƤŻ‘µṀ‘Rḟḣ³
2ÇÐL

Try it online!

Uses an idea from this J answer. Truncate to the desired length each iteration, and take the fixpoint. I thought using S (sum) instead of Ṁ‘ (max+1), but I can't guarantee its correctness.