La secuencia contiene la representación decimal de los números binarios de la forma:, 10101...donde el enésimo término tiene n bits.

La secuencia es probablemente más fácil de explicar simplemente mostrando las relaciones entre las representaciones binarias y decimales de los números:

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

Reto:

Tome un entero de entrada ny devuelva los primeros n números en la secuencia. Puede elegir tener la secuencia indexada en 0 o indexada en 1.

Casos de prueba:

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

Se alientan las explicaciones, como siempre.

Este es OEIS A000975 .

Python 2 , 36 bytes

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

Pruébalo en línea! Explicación: la representación binaria de esasí que simplemente queda multiplicarlo por una potencia apropiada de 2 y tomar la porción entera.$\frac{2}3$0.101010101...

05AB1E , 4 bytes

2 bytes guardados usando el truco 2/3 de Neil

Lo3÷

Pruébalo en línea!

Explicación

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

05AB1E , 6 bytes

TRI∍ηC

Pruébalo en línea!

Explicación

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

Jalea , ... 4 bytes

Gracias millas por -1 byte!

ḶḂḄƤ

Pruébalo en línea!

Explicación:

Ḷ     Ḷ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.

Jalea , 4 bytes

La versión de Jonathan Allan.

Ḷ€ḂḄ

Pruébalo en línea!

Ḷ     Ḷ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.

Una versión basada en el truco 2/3 de Neil da 5 bytes, ver historial de revisiones.

MATL , 5 bytes

:WI/k

Basado en la respuesta de Neil .

Explicación

:       % 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

Pruébalo en línea!

MATL , 9 bytes

:q"@:oXBs

Pruébalo en línea!

Explicación

:       % 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 bytes

^{-3 bytes gracias a user202729
-1 byte gracias a mathmandan}

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

Pruébalo en línea!

Python 3, 68 61 54 48 43 bytes

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

Gracias a user202729 por ayudar a guardar 19 bytes y ovs por ayudar a guardar 6 bytes.

Pruébalo en línea

Casco , 7 bytes

mḋḣ↑Θݬ

Pruébalo en línea!

Basado en 1, por lo que la entrada n da los primeros n resultados.

Explicación

     ݬ   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) , 11 bytes de ^SBCS

Asume ⎕IO( I ndex O rigin) ser 0, que es predeterminado en muchos sistemas. Función de prefijo tácito anónimo. 1 indexado.

(2⊥⍴∘1 0)¨⍳

Pruébalo en línea!

⍳ d ndices 0 ... n − 1

(... )¨ aplique la siguiente función tácita a cada

 ⍴∘1 0 reformar cíclicamente la lista [1,0]a esa longitud

 2⊥ convertir de base-2 (binario) a número normal

Perlv5.10 -n , 24 + 1 bytes

-3 bytes gracias a Nahuel Fouilleul !

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

Pruébalo en línea!

Misma lógica que mi versión Ruby, pero más corta porque Perl es más conciso. Por alguna extraña razón, printno haría un separador (maldita sea!), Así que tuve que utilizar saydesde v5.10;el fin de la misma para ejecutar, no estoy seguro de cómo anotar esto, así que estoy dejando por ahora ?. ..

Explicación

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 bytes

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

Pruébalo en línea!

APL (Dyalog) , 7 bytes

⌊3÷⍨2*⍳

Pruébalo en línea!

APL (Dyalog) , 11 bytes

(2⊥2|⍳)¨1+⍳

Pruébalo en línea!

Usos ⎕IO←0.

C , 81 55 59 bytes

1 indexado.

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

Programa completo, menos golf:

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

Pruébalo en línea!

EDIT 2: estaba bajo el supuesto de que las funciones no necesitaban ser reutilizables ahora que lo pienso, tiene mucho sentido que tendrían que ser reutilizables: P

EDITAR: estaba bajo la idea errónea de que tenía que incluir todo el programa en la respuesta, resulta que solo necesitaba la función que lo hace. Eso es bueno.

Estoy bastante seguro de que puedo reducir algunos bytes aquí y allá. Ya he empleado algunos trucos. Una gran parte del programa está dedicada a obtener el argumento y convertirlo en un int. Este es mi primer código de golf. Si estoy haciendo algo mal dime: P

Haskell , 47 40 53 49 44 40 34 bytes

-4 bytes gracias a user202729
-6 bytes gracias a Laikoni

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

Pruébalo en línea!

Rubí , 26 bytes

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

Pruébalo en línea!

Supera todas las respuestas de rubí más antiguas.

Explicación

1/3en binario se ve así 0.01010101..., así que si lo multiplicas por potencias de dos, obtienes:

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

Pero Ruby pone los números en la división int, dándome la secuencia que necesito.

J , 9 bytes

[:#.\2|i.

¿Cómo funciona?

i. - lista 0..n-1

2| - los elementos de la lista mod 2

\ - todos los prefijos

#. - a decimal

[: - tapa el tenedor (ya que tengo un número par (4) de verbos)

Pruébalo en línea!

Retina , 28 bytes

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

Pruébalo en línea!

Basado en 0, por lo que la entrada n da el primer n + 1 resultados.

Explicación

Utiliza la recursividad de OEIS:

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

Veamos el programa:

)K`0

Esta es una etapa constante: descarta la entrada y establece la cadena de trabajo en 0el valor inicial de la secuencia. El )envuelve esta etapa en un grupo. Ese grupo en sí no hace nada, pero casi todas las etapas (incluidas las etapas del grupo) registran su resultado en un registro, y necesitaremos dos copias de 0ese registro para que el programa funcione.

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

Hay un montón de configuraciones aquí: "$+"+envuelve el escenario en un bucle. El "$+"se trata como una sustitución y se $+refiere a la entrada del programa, es decir, n . Esto significa que el ciclo se ejecuta n veces.

Luego ¶<envuelve cada iteración en una etapa de salida, que imprime la entrada de la etapa con un salto de línea final (por lo que la primera iteración imprime el cero, la segunda iteración imprime el resultado de la primera iteración y así sucesivamente).

La etapa misma reemplaza toda la cadena de trabajo con la sustitución en la última línea. Ese utiliza un paréntesis de cierre implícito y argumentos implícitos para el operador de repetición *, por lo que en realidad es la abreviatura de:

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

Las cosas dentro de los paréntesis se pueden dividir en tres partes:

• $&*_: da una cadena de a (n-1) _ s.
• _: da un sencillo _.
• 2*$-1*_: da una cadena de 2 * a (n-1) _ . Se $-1refiere al penúltimo resultado en el registro de resultados, es decir, la iteración del bucle antes del último. Por eso, para empezar, necesitábamos copias del cero en el registro, de lo contrario, esto se referiría a la entrada del programa en la primera iteración.

Luego $.(…)mide la longitud de la cadena resultante. En otras palabras, hemos calculado a(n) = a(n-1) + 1 + 2*a(n-2)yendo a través de unary (aunque en realidad no: $.(…)es vago y en realidad no evalúa su contenido si puede determinar la longitud resultante directamente a través de la aritmética, por lo que esto es incluso bastante eficiente).

El resultado de la iteración final del bucle (el elemento n + 1º de la secuencia) se imprime debido a la salida implícita de Retina al final del programa.

Brain-Flak , 36 bytes

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

Pruébalo en línea!

Explicación:

El siguiente número en la secuencia se obtiene por n*2+1o 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

Ruby 42 41 43 41 37 35 31 33 30 bytes

-2 bytes gracias a Unihedron

-3 bytes gracias a GB

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

Pruébalo en línea!

> <> , 22 + 3 (-v indicador) bytes

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

Pruébalo en línea!

Explicación

La pila se inicializa con el contador de bucle.

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 bytes

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

Puerto de la respuesta Python 2 de @Neil .
1 indexado y enviado directamente, cada valor en una línea separada.

Explicación:

Pruébalo en línea.

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

Antigua respuesta de 80 bytes:

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

Entrada indexada 1 y Stringsalida delimitada por espacios

Explicación:

Pruébalo en línea.

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 bytes

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

Pruébalo (35)

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

Pruébalo (30)

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

Pruébalo (30)

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

Pruébalo (27)

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

Pruébalo (25)

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

Pruébalo (20)

Expandido:

{
 (
  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 bytes

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

Pruébalo en línea!

Python 2 , 34 bytes

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

Pruébalo en línea!

Devoluciones en orden inverso.

C, 47 46 bytes

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

El acumulador acomienza con cero. En cada paso, lo duplicamos ( a+=a) y agregamos uno si el bit menos significativo anterior fue cero ( !(a%2)o equivalente -(~a)%2).

Programa de prueba

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

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

Resultados

$ ./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 bytes

Todo derivado independientemente de otras soluciones.

1 indexado.

õ!²mz3

Intentalo

Explicación

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

Intentalo

Versión de 7 bytes

õ_ou ì2

Intentalo

õ            :[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

Versión de 9 bytes

õ_îA¤w)n2

Intentalo

õ            :[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 bytes

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

Pruébalo en línea!

MATL , 7 bytes

:&+oRXB

Pruébalo en línea!

Explicación:

         % 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 salida sería 0, 1, 2, 5 ...si Pse agregara al final ( flip), lo que lo convierte en 8 bytes.

Rubí -n ,32 30 + 1 bytes

Ya que tenemos exactamente 1 línea de entrada, ¡ $.es muy conveniente!

EDITAR: Estoy sorprendido de que logré superarme a mí mismo, pero parece usar el -nque cuenta como 1 (por la regla 2 en condiciones especiales predeterminadas , ya que Ruby se puede ejecutar con ruby -e 'full program'(por lo tanto, -nes 1), todas las instancias de las getscuales solo se usan una vez. se golfed 1 char de esta manera; creo que este es un hito para el rubí, por favor, hable si no está de acuerdo con este tren de pensamiento antes de reutilizarlo repetidamente en el futuro)

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

Pruébalo en línea!

Explicación

# 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 bytes

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

Pruébalo en línea!

Utiliza la fórmula descaradamente robada de esta otra respuesta de Ruby.

Si bien no haber a=0funcionado (awk trata "vacío" como 0), el primer elemento de 0 no se imprimirá y en su lugar será una emptylínea, que si bien diría que una salida válida probablemente no pasará, por lo a=0que puede ser insertado como argumento de línea de comando.

C, 52 bytes

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

1 indexado

Pruébalo en línea!

brainfuck , 40 bytes

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

Pruébalo en línea!

0 indexado. Entrada como código de caracteres, salida como unario con bytes nulos que separan series de códigos de caracteres 1. Asume celdas de 8 bits a menos que desee ingresar más de 255. Asume celdas negativas, aunque esto podría solucionarse a expensas de varios bytes.

Anteriormente, 50 bytes

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

Pruébalo en línea!

Entradas como código char, salidas como código char. 1 indexado. Probablemente podría jugar un poco al golf.

@Unihedron señala que olvidé especificar que esto necesita celdas de tamaño infinito, de lo contrario, supera el octavo número.