Dans Gödel, Escher, Bach , Douglas Hofstadter introduit une séquence entière qui est communément appelée la séquence figure-figure:

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

Vous pouvez apprécier d'élaborer la définition de la séquence vous-même dans le cadre du défi, mais si vous ne pouvez pas ou ne voulez pas la comprendre, vous pouvez la trouver sur OEIS en tant que séquence A030124 et une définition légèrement plus claire sur Wikipédia .

Écrivez un programme ou une fonction qui, donné nvia STDIN, ARGV ou argument de fonction, imprime une liste des premiers nnombres de la séquence dans STDOUT dans n'importe quel format de liste raisonnable.

Il s'agit du code golf, la solution la plus courte en octets gagne.

CJam, 38 30 29 21 octets

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

Essayez-le en ligne.

Comment ça fonctionne

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.                  ";

Exemple d'exécution

$ 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

Haskell, 67 61 60 56 55 53 caractères

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

retour au premier algorithme.

cette solution calcule la séquence du complément en additionnant les éléments de départ de la séquence. il calcule ensuite la séquence comme tous les nombres entre les numéros de séquence du complément.

(#)est la fonction qui calcule les nombres entre la séquence du complément.
hest la séquence elle-même.
gest la fonction qui répond à la question.

la fonction g est définie pour prendre juste la quantité nécessaire d'éléments de h.

subtilités:

hest en fait la séquence de figure figure à l'exception des 2 premiers éléments.
non pas la séquence du complément est calculée, mais la séquence du complément avec 1 ajouté pour chaque élément.
ces deux subtilités sont la raison scanl(+)8h(qui est le code de la séquence complémentaire (à l'exception des 2 premiers éléments) avec des 1 ajoutés) 8. c'est pour le troisième élément de la séquence du complément avec 1 ajouté.
la raison pour laquelle le calcul ne manque pas les deux premiers éléments est qu'ils sont ajoutés gdans 2:4:h.

exemple:

>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]

Rubis, 54 48

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

Démo

Edit: J'ai joué au golf un peu plus une fois que j'ai réalisé que je n'avais pas besoin de garder la séquence complète du complément en mémoire. Voici comment cela fonctionne maintenant: nous utilisons xpour garder une trace du plus grand nombre calculé dans la séquence complémentaire, et best un pool de candidats pour la séquence. nfois, nous sortons le plus petit élément restant dans bet l'ajoutons à xpour calculer le nombre suivant dans la séquence du complément. Ensuite, nous supprimons les deux nombres du pool de candidats, donc nous émettons toujours le plus petit nombre qui n'a pas déjà été ajouté à l'une ou l'autre séquence.

Astuces de golf Ruby: La syntaxe lambda Stabby est plus courte qu'une définition de méthode. L'exigence que la sortie soit donnée à STDOUT au lieu d'une valeur de retour m'a inspiré à utiliser le fait que la valeur de retour de p(x)est x, ce dont je ne me souviens pas normalement car ce n'est pas le cas dans la version Ruby utilisée dans Anarchy Golf.

GolfScript ( 24 21 octets)

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

Démo en ligne

Cela a commencé tout à fait différemment, mais a fini par converger vers un port GolfScript de la solution Ruby d ' histocrat avant que Dennis ne fasse quelques suggestions qui l' amènent dans une direction légèrement différente. En particulier, l'impression des numéros tels que nous les identifions permet d'économiser un peu plus que de les rassembler dans un tableau pour l'impression à la fin; la raison en est que cela signifie qu'à aucun moment nous n'avons à nous soucier de plus de 3 objets sur la pile.

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

J - 28 caractères

Prise de fonction ncomme argument.

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

Nous exécutons une fonction, avec ncomme argument gauche, sur son argument droit à plusieurs reprises jusqu'à ce qu'elle ne produise aucun changement. L'argument pour commencer est la liste 2 4.

Dans la fonction elle-même, nous prenons les sommes partielles +/\et la somme complète +/, puis les incrémentons toutes les deux avec &:>:. Nous générons ensuite chaque entier de 2 à un de plus que la somme totale ( 2+i.), et fixons soustrayons ( -.) les sommes partielles, laissant une séquence figure-figure plus longue par définition. Enfin, nous raccourcissons ou étendons cycliquement la liste à la longueur n.

Le résultat est que cela 2 4devient 3 7, et cela est retiré de la 2..8sortie 2 4 5 6 8. Après un autre tour, 2 4 5 6 8devient 3 7 12 18 26devient

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

De cette façon, nous étendons à plusieurs reprises la séquence figure-figure. Le $comportement de longueur est juste un moyen non trivial d'économiser des caractères d'attendre que la séquence atteigne une longueur nou plus, et de sortir les npremières valeurs lorsqu'elles cessent de changer. Nous n'avons pas non plus à attendre très longtemps: nous pouvons obtenir jusqu'à 46336 termes à partir de quatre applications du verbe intérieur.

La même fonction en k:

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

Java - 183 158

C'est le plus que je n'ai jamais joué au golf, et j'en suis fier! (Bien qu'il ne soit nulle part près du haut des graphiques (car c'est Java))

Merci à Peter Taylor pour ses 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;);}}}

plus gros -

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

Python 2 - 77 octets

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

Fonctionne de la même manière que la solution de @ histocrat, sauf que l'entrée provient de stdin.

Python 2 - 68

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

Gelée , 15 octets

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

Essayez-le en ligne!

Erreur de mémoire à l'entrée de 6.

Comment ça fonctionne

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

Version plus efficace, 16 octets

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

Essayez-le en ligne!

Utilise une idée de cette réponse J . Tronquez à la longueur souhaitée à chaque itération et prenez le point fixe. J'ai pensé utiliser S(somme) au lieu de Ṁ‘(max + 1), mais je ne peux pas garantir son exactitude.