17
\$\begingroup\$

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.

\$\endgroup\$

9 Answers 9

6
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ You've missed the s out of aditsu when typing the url for the interpreter \$\endgroup\$
    – Beta Decay
    Sep 10, 2014 at 10:44
  • \$\begingroup\$ @BetaDecay then why not edit to fix it ;) \$\endgroup\$ Sep 10, 2014 at 10:53
  • \$\begingroup\$ @Martin I didn't think I had enough rep... \$\endgroup\$
    – Beta Decay
    Sep 10, 2014 at 10:54
  • 2
    \$\begingroup\$ @BetaDecay You don't, but you can still suggest them (which even gives you 2 rep if they are accepted). \$\endgroup\$ Sep 10, 2014 at 10:59
  • \$\begingroup\$ I felt so clever for golfing off 8 additional bytes of my code. Then I realized that it now does exactly the same as the answers from histocrat, matsjoyce and Peter Taylor... \$\endgroup\$
    – Dennis
    Sep 10, 2014 at 14:06
6
\$\begingroup\$

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]
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ How does it work? \$\endgroup\$ Sep 9, 2014 at 18:46
  • 1
    \$\begingroup\$ FWIW you could use 2..2*n. I have to use n*n because I'm doing effectively b = [x]^b so I need the largest element of b to be larger than the largest value of x, but your b -= [x] just requires that b contains the largest possible value of the output sequence. \$\endgroup\$ Sep 10, 2014 at 14:02
4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ If you replace ^ with \-, you can replace ).* with 3*. This won't save any bytes, but it drastically reduces run time and memory usage. -- You should be able to save one byte by keeping the integer on top of the array. The loop will have the same byte count, but initialization will be one byte shorter. \$\endgroup\$
    – Dennis
    Sep 10, 2014 at 15:30
  • 2
    \$\begingroup\$ Set union works even better than difference: ~.3*,1>\{(\(.p@+\|}*; \$\endgroup\$
    – Dennis
    Sep 10, 2014 at 15:43
3
\$\begingroup\$

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;)
                ;
        }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ That inner for loop is quite impressively obfuscated, but I think you can save a few bytes. Byte.valueOf saves three, and since the question doesn't specify the range of input I think it should be acceptable. Outside the loops, m is only used to initialise n, so k++<m could be m-->0, eliminating k entirely. int[] n can be initialised as int n[] and merged into the previous initialiser. n never holds values other than 1, so n[...]!=0 could be n[...]>0. The initialiser can then become the initialiser part of the first for loop. \$\endgroup\$ Sep 10, 2014 at 21:46
  • \$\begingroup\$ And if you get rid of u and just use ++w, there's no need to set n[q] or n[w]. There's one bug, in that you run off the end of n when m==2, which seems to be best fixed by initialising n=new int[2*m*m], but I think it's down to 157 bytes. \$\endgroup\$ Sep 10, 2014 at 21:55
  • \$\begingroup\$ What I meant about the initialiser becoming the initialiser part of the first for loop was for(int q=1,w=2,m=...,n[]=...;m-->0;){... saving a semicolon. \$\endgroup\$ Sep 11, 2014 at 9:04
3
\$\begingroup\$

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}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Python 2 - 68

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

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.

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.