La séquence contient la représentation décimale des nombres binaires de la forme:, 10101...où le nième terme a n bits.

La séquence est probablement plus facile à expliquer en montrant simplement les relations entre les représentations binaires et décimales des nombres:

0       ->  0
1       ->  1
10      ->  2
101     ->  5
1010    ->  10
10101   ->  21
101010  ->  42

Défi:

Prenez un entier en entrée net renvoyez les n premiers nombres de la séquence. Vous pouvez choisir d'avoir la séquence indexée 0 ou 1 indexée.

Cas de test:

n = 1   <- 1-indexed
0

n = 18
0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922, 21845, 43690, 87381

Les explications sont encouragées, comme toujours.

Il s'agit d' OEIS A000975 .

Python 2 , 36 octets

lambda n:[2**i*2/3for i in range(n)]

Essayez-le en ligne! Explication: La représentation binaire de estdonc qu'il reste simplement à le multiplier par une puissance appropriée de 2 et à prendre la partie entière.$\frac{2}3$0.101010101...

05AB1E , 4 octets

2 octets enregistrés en utilisant l'astuce 2/3 de Neil

Lo3÷

Essayez-le en ligne!

Explication

L      # push range [1 ... input]
 o     # raise 2 to the power of each
  3÷   # integer division of each by 3

05AB1E , 6 octets

TRI∍ηC

Essayez-le en ligne!

Explication

T        # push 10
 R       # reverse it
  I∍     # extend to the lenght of the input
    η    # compute prefixes
     C   # convert each from base-2 to base-10

Gelée , ... 4 octets

Merci des miles pour -1 octet!

ḶḂḄƤ

Essayez-le en ligne!

Explication:

Ḷ     Ḷowered range, or UnḶength. Get [0, 1, 2, 3, ..., n-1]
 Ḃ    Ḃit. Get the last bit of each number. [0, 1, 0, 1, ...]
   Ƥ  for each Ƥrefixes [0], [0, 1], [0, 1, 0], [0, 1, 0, 1], ...
  Ḅ   convert it from Ḅinary to integer.

Gelée , 4 octets

Version de Jonathan Allan.

Ḷ€ḂḄ

Essayez-le en ligne!

Ḷ     Ḷowered range, or UnḶength.
 €    Apply for €each. Automatically convert the number n
      to the range [1,2,..,n]. Get [[0],[0,1],[0,1,2],..].
  Ḃ   Ḃit. Get the last bit from each number.
      Current value: [[0],[0,1],[0,1,0],..]
   Ḅ  Convert each list from Ḅinary to integer.

Une version basée sur l'astuce 2/3 de Neil donne 5 octets, voir l'historique des révisions.

MATL , 5 octets

:WI/k

Basé sur la réponse de Neil .

Explication

:       % Implicit input, n. Push range [1 2 ... n]
W       % 2 raised to that, element-wise. Gives [2 4 ...2^n] 
I       % Push 3
/       % Divide, element-wise
k       % Round down, element-wise. Implicit display

Essayez-le en ligne!

MATL , 9 octets

:q"@:oXBs

Essayez-le en ligne!

Explication

:       % Implicit input n. Range [1 2 ... n]
q       % Subtract 1, element-wise: gives [0 1 ... n-1]
"       % For each k in [0 1 ... n-1]
  @     %   Push k
  :     %   Range [1 2 ... k]
  o     %   Modulo 2, element-wise: gives [1 0 1 ...]
  XB    %   Convert from binary to decimal
  s     %   Sum. This is needed for k=0, to transform the empty array into 0
        % Implicit end. Implicit display

Python 2 , 45 37 36 octets

^{-3 octets grâce à user202729
-1 octet grâce à mathmandan}

s=0
exec"print s;s+=s+~s%2;"*input()

Essayez-le en ligne!

Python 3, 68 61 54 48 43 octets

c=lambda x,r=0:x and[r]+c(x-1,2*r+~r%2)or[]  

Merci à user202729 pour avoir aidé à économiser 19 octets et ovs pour avoir aidé à économiser 6 octets.

Essayez-le en ligne

Coque , 7 octets

mḋḣ↑Θݬ

Essayez-le en ligne!

Basé sur 1, donc l'entrée n donne les n premiers résultats.

Explication

     ݬ   The infinite list [1, 0, 1, 0, 1, ...]
    Θ     Prepend a zero.
   ↑      Take the first n elements.
  ḣ       Get the prefixes of that list.
mḋ        Interpret each prefix as base 2.

APL (Dyalog Unicode) , ^{SBCS de} 11 octets

Suppose que ⎕IO( I ndex O rigin) est 0, ce qui est le cas par défaut sur de nombreux systèmes. Fonction de préfixe tacite anonyme. 1 indexé.

(2⊥⍴∘1 0)¨⍳

Essayez-le en ligne!

⍳ ɩ ndices 0… n − 1

(… )¨ Appliquer la fonction tacite suivante à chacun

 ⍴∘1 0 remodeler cycliquement la liste [1,0]à cette longueur

 2⊥ convertir de base-2 (binaire) en nombre normal

Perlv5.10 -n , 24 + 1 octets

-3 octets grâce à Nahuel Fouilleul !

say$v=$v*2|$|--while$_--

Essayez-le en ligne!

Même logique que ma version Ruby, mais plus courte car perl est plus concis. Pour une raison étrange, printje ne ferais pas de séparateur (bon sang!), Donc j'ai dû utiliser sayfrom v5.10;pour que cela fonctionne, je ne sais pas comment marquer cela, donc je le laisse pour le moment?. ..

Explication

say    # Like shouting, but milder.
  $v = $v*2 | $|-- # Next element is this element times 2 bitwise-OR
                   # with alternating 0 1 0 1..., so 0b0, 0b1, 0b10, 0b101...
                   # $. is OUTPUT_AUTOFLUSH, which is initially 0 and
                   #   setting all non-zero values seem to be treated as 1
  while $_-- # do for [input] times

Haskell , 33 octets

l=1:0:l
($scanl((+).(2*))0l).take

Essayez-le en ligne!

APL (Dyalog) , 7 octets

⌊3÷⍨2*⍳

Essayez-le en ligne!

APL (Dyalog) , 11 octets

(2⊥2|⍳)¨1+⍳

Essayez-le en ligne!

Utilisations ⎕IO←0.

C , 81 55 59 octets

1 indexé.

i,j;f(c){for(i=j=0;i<c;)printf("%d ",i++&1?j+=j+1:(j+=j));}

Programme complet, moins golfé:

i;j;main(c,v)char**v;{c=atoi(*++v);for(;i<c;i++)printf("%d ",i&1?j+=j+1:(j+=j));}

Essayez-le en ligne!

EDIT 2: J'étais sous l'hypothèse que les fonctions n'avaient pas besoin d'être réutilisables maintenant que j'y pense, il est parfaitement logique qu'elles devraient être réutilisables: P

EDIT: Je pensais à tort que je devais inclure l'ensemble du programme dans la réponse, il s'avère que je n'avais besoin que de la fonction qui le fait. C'est bien.

Je suis décemment sûr de pouvoir raser quelques octets ici et là. J'ai déjà utilisé quelques astuces. Une grande partie du programme est dédiée à obtenir l'argument et à le transformer en un int. Ceci est mon premier golf de code. Si je fais quelque chose de mal, dites-moi: P

Haskell , 47 40 53 49 44 40 34 octets

-4 octets grâce à user202729
-6 octets grâce à Laikoni

(`take`l)
l=0:[2*a+1-a`mod`2|a<-l]

Essayez-le en ligne!

Rubis , 26 octets

->n{(1..n).map{|i|2**i/3}}

Essayez-le en ligne!

Bat toutes les réponses rubis plus anciennes.

Explication

1/3en binaire ressemble 0.01010101..., donc si vous le multipliez par des puissances de deux, vous obtenez:

n| 2^n/3
-+---------
1|0.1010101...
2|01.010101...
3|010.10101...
4|0101.0101...
5|01010.101...
6|010101.01...

Mais Ruby fixe les nombres sur la division int, me donnant la séquence dont j'ai besoin.

J , 9 octets

[:#.\2|i.

Comment ça marche?

i. - liste 0..n-1

2| - les éléments de la liste mod 2

\ - tous les préfixes

#. - en décimal

[: - coiffe la fourche (comme j'ai un nombre pair (4) de verbes)

Essayez-le en ligne!

Rétine , 28 octets

)K`0
"$+"+¶<`.+
$.(*__2*$-1*

Essayez-le en ligne!

Basé sur 0, donc l'entrée n donne le premier n + 1 résultats.

Explication

Utilise la récursivité d'OEIS:

a(n) = a(n-1) + 2*a(n-2) + 1

Passons en revue le programme:

)K`0

Il s'agit d'une étape constante: elle supprime l'entrée et définit la chaîne de travail sur 0, la valeur initiale de la séquence. L' )encapsule cette étape dans un groupe. Ce groupe lui-même ne fait rien, mais presque chaque étape (y compris les étapes de groupe) enregistre son résultat dans un journal, et nous aurons besoin de deux copies de 0ce journal pour que le programme fonctionne.

"$+"+¶<`.+
$.(*__2*$-1*

Il y a un tas de configuration ici: "$+"+enveloppe la scène en boucle. Le "$+"est traité comme une substitution et $+fait référence à l'entrée du programme, c'est-à-dire n . Cela signifie que la boucle est exécutée n fois.

¶<Enveloppe ensuite chaque itération dans une étape de sortie, qui imprime entrée de avec un saut de ligne de fin (donc la première itération imprime le zéro, la deuxième itération imprime le résultat de la première itération et ainsi de suite).

L'étape elle-même remplace la chaîne de travail entière par la substitution sur la dernière ligne. Celui-ci utilise une parenthèse de fermeture implicite et des arguments implicites pour l'opérateur de répétition *, il est donc en fait court pour:

$.($&*__2*$-1*_)

Le contenu entre parenthèses peut être divisé en trois parties:

• $&*_: donne une chaîne de a (n-1) _ s.
• _: donne un single _.
• 2*$-1*_: donne une chaîne de 2 * a (n-1) _ . Le $-1fait référence à l'avant-dernier résultat dans le journal des résultats, c'est-à-dire l'itération de boucle avant le dernier. C'est pourquoi nous avions besoin de copies du zéro sur le journal pour commencer, sinon cela ferait référence à l'entrée du programme lors de la première itération.

$.(…)Mesure ensuite la longueur de la chaîne résultante. En d'autres termes, nous avons calculé a(n) = a(n-1) + 1 + 2*a(n-2)en passant par unaire (pas vraiment cependant: $.(…)est paresseux et n'évalue pas réellement son contenu s'il peut déterminer la longueur résultante directement par arithmétique, donc c'est même assez efficace).

Le résultat de l'itération finale de la boucle (le n + 1 ème élément de la séquence) est imprimé en raison de la sortie implicite de Retina à la fin du programme.

Brain-Flak , 36 octets

{([()]{}<((({}<>)<>){}([{}]()))>)}<>

Essayez-le en ligne!

Explication:

Le nombre suivant de la séquence est obtenu par n*2+1ou n*2+0.

{([()]{}< Loop input times
  (
   (({}<>)<>){} Copy n to other stack; n*2
   ([{}]())  i = 1-i
  ) push n*2 + i
>)} End loop
<> Output other stack

Rubis 42 41 43 41 37 35 31 33 30 octets

-2 octets grâce à Unihedron

-3 octets grâce à GB

->x{a=0;x.times{a-=~a+p(a)%2}}

Essayez-le en ligne!

> <> , 22 + 3 (-v flag) octets

0:nao::1+2%++$1-:?!;$!

Essayez-le en ligne!

Explication

La pile est initialisée avec le compteur de boucles.

0:nao                  : Push 0 to the stack, duplicate and print with a new line.
                         [7] -> [7, 0]
     ::1+              : Duplicate the stack top twice more then add 1 to it.
                         [7, 0] -> [7, 0, 0, 1]
         2%++          : Mod the stack top by 2 then add all values on the stack bar the loop counter.
                         [7, 0, 0, 1] -> [7, 1]
             $1-:?!;$! : Swap the loop counter to the top, minus 1 from it and check if zero, if zero stop the program else continue.

Java 8, 115 81 80 52 octets

n->{for(int i=2;n-->0;i*=2)System.out.println(i/3);}

Réponse de Port of @Neil Python 2 .
1 indexé et sorti directement, chaque valeur sur une ligne séparée.

Explication:

Essayez-le en ligne.

n->{                           // Method with integer parameter and no return-type
  for(int i=2;                 //  Start integer `i` at 2
      n-->0;                   //  Loop `n` times:
      i*=2)                    //    Multiply `i` by 2 after every iteration
    System.out.println(i/3);}  //   Print `i` integer-divided by 3 and a new-line

Ancienne réponse de 80 octets:

n->{String t="",r=t;for(Long i=0L;i<n;)r+=i.parseLong(t+=i++%2,2)+" ";return r;}

Entrée indexée 1 et Stringsortie délimitée par des espaces

Explication:

Essayez-le en ligne.

n->{                             // Method with integer parameter and String return-type
  String t="",r=t;               //  Temp and result-Strings, both starting empty
  for(Long i=0L;i<n;)            //  Loop from 0 to `n` (exclusive)
    r+=                          //   Append the result-String with:
       i.parseLong(        ,2);  //    Binary to integer conversion
                   t+=           //     append the temp-String with:
                      i  %2      //      current index `i` modulo-2
                       ++        //      and increase `i` by one afterwards
       +" ";                     //    + a space
  return r;}                     //  Return the result-String

Perl 6 ,  35 30 27 25  20 octets

{[\~](0,+!*...*)[^$_]».&{:2(~$_)}}

Essayez-le (35)

{(0,{$_*2+|($+^=1)}…*)[^$_]}

Essayez-le (30)

{(⅓X*(2,4,8…2**$_))».Int}

Essayez-le (30)

{(⅔,* *2…*)[^$_]».Int}

Essayez-le (27)

{((2 X**1..$_)X/3)».Int}

Essayez-le (25)

{(2 X**1..$_)Xdiv 3}

Essayez-le (20)

Étendu:

{
 (
  2                  # 2
    X**              # cross to the power of
       1..$_         # Range from 1 to the input (inclusive)
            )

             Xdiv    # cross using integer divide
                  3  # by 3
}

Python 2 , 33 octets

s=2
exec"print s/3;s*=2;"*input()

Essayez-le en ligne!

Python 2 , 34 octets

f=lambda n:n*[f]and[2**n/3]+f(n-1)

Essayez-le en ligne!

Retourne dans l'ordre inverse.

C, 47 46 octets

a;f(n){for(a=0;n--;a+=a-~a%2)printf("%d ",a);}

L'accumulateur acommence par zéro. À chaque étape, nous le doublons ( a+=a) et en ajoutons un si le bit le moins significatif précédent était zéro ( !(a%2), ou de manière équivalente,-(~a)%2 ).

Programme de test

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv)
{
    while (*++argv) {
        f(atoi(*argv));
        puts("");
    }
}

Résultats

$ ./153783 1 2 3 4 5 6
0 
0 1 
0 1 2 
0 1 2 5 
0 1 2 5 10 
0 1 2 5 10 21 

Japt , 10 9 7 6 octets

Tous dérivent indépendamment d'autres solutions.

1 indexé.

õ!²mz3

L'essayer

Explication

õ        :[1,input]
 !²      :Raise 2 to the power of each
   m     :Map
    z3   :Floor divide by 3

L'essayer

Version 7 octets

õ_ou ì2

L'essayer

õ            :[1,input]
 _           :Pass each through a function
   o         :[0,current element)
    u        :Modulo 2 on above
      ì2     :Convert above from base-2 array to base-10

Version 9 octets

õ_îA¤w)n2

L'essayer

õ            :[1,input]
 _           :Pass each through a function
   A         :10
    ¤        :Convert to binary
     w       :Reverse
  î          :Repeat the above until it's length equals the current element
      )      :Close nested methods
       n2    :Convert from binary to base-10

Haskell , 52 octets

(`take`map a[0..])
a 0=0
a 1=1
a n=a(n-1)+2*a(n-2)+1

Essayez-le en ligne!

MATL , 7 octets

:&+oRXB

Essayez-le en ligne!

Explication:

         % Implicitly grab input, n
:        % Range: 1 2 ... n

 &+      % Add the range to itself, transposed
         % 2 3 4 5 ...
         % 3 4 5 6 ...
         % 4 5 6 7 ...
         % 5 6 7 8 ...

   o     % Parity (or modulus 2)
         % 0 1 0 1 ...
         % 1 0 1 0 ...
         % 0 1 0 1 ...
         % 1 0 1 0 ...

    R    % Upper triangular matrix:
         % 0 1 0 1
         % 0 0 1 0
         % 0 0 0 1
         % 0 0 0 0

    XB   % Convert rows to decimal:
         % [5, 2, 1, 0]
         % Implicitly output

La sortie serait 0, 1, 2, 5 ...if a Pété ajoutée à end ( flip), ce qui en fait 8 octets.

Rubis -n ,32 30 + 1 octets

Puisque nous avons exactement 1 ligne d'entrée, $.c'est très pratique!

EDIT: Je suis étonné d'avoir réussi à me surpasser, mais il semble que l'utilisation -nqui compte comme 1 (par la règle 2 dans les conditions spéciales par défaut , car Ruby peut être exécutée avec ruby -e 'full program'(donc -n1) toutes les instances getsqui ne sont utilisées qu'une seule fois peut être joué au golf 1 caractère de cette façon; je crois que c'est une étape importante pour le rubis, veuillez vous exprimer si vous n'êtes pas d'accord avec ce courant de pensée avant de le réutiliser à plusieurs reprises à l'avenir)

v=0
?1.upto($_){p v=v*2|$.^=1}

Essayez-le en ligne!

Explication

# while gets(); -- assumed by -n
v=0            # First element of the sequence
?1.upto($_){   # Do from "1" to "$LAST_READ_LINE" aka: Repeat [input] times
  p            # print expression
  v=v*2|$.^=1  # Next element is current element times two
               # bitwise-or 0 or 1 alternating
               # $. = lines of input read so far = 1 (initially)
}
# end           -- assumed by -n

AWK a=0 , 31 octets

{for(;$1--;a=a*2+1-a%2)print a}

Essayez-le en ligne!

Utilise la formule sans vergogne volée de cette autre réponse Ruby.

Bien que ne pas avoir a=0fonctionnerait (awk traite "vide" comme 0), le premier élément de 0 ne sera pas imprimé et sera plutôt une emptyligne, ce qui, bien que je dirais, est qu'une sortie valide ne passera probablement pas, donc il y a a=0qui peut être inséré comme argument de ligne de commande.

C, 52 octets

i,k;f(n){for(i=k=0;i<n;k=++i%2+2*k)printf("%d ",k);}

1 indexé

Essayez-le en ligne!

brainfuck , 40 octets

,[>.>>[>]<[.->[>]+[<]+<]+<[[-<+>]>-<]<-]

Essayez-le en ligne!

0 indexé. Entrée en tant que code de caractère, sortie en tant qu'unaire avec des octets nuls séparant les séries de code de caractère 1s. Suppose des cellules 8 bits, sauf si vous souhaitez entrer plus de 255. Suppose des cellules négatives, bien que cela puisse être corrigé au détriment de plusieurs octets.

Auparavant, 50 octets

,[[<]>->>[<-<->>>>-<]<[->>++<<]>>+[-<<+>>]<<.<<+>]

Essayez-le en ligne!

Entrées sous forme de code char, sorties sous forme de code char. 1 indexé. On pourrait probablement jouer un peu au golf.

@Unihedron souligne que j'ai oublié de spécifier que cela nécessite des cellules de taille infinie, sinon il arrive en tête au 8e nombre.