Sekwencja zawiera dziesiętną reprezentację liczb binarnych postaci: 10101...gdzie n-ty składnik ma n bitów.

Sekwencja jest prawdopodobnie najłatwiejsza do wyjaśnienia, po prostu pokazując związki między reprezentacjami liczb binarnych i dziesiętnych:

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

Wyzwanie:

Weź wejściową liczbę całkowitą ni zwróć pierwsze n liczb w sekwencji. Możesz wybrać sekwencję 0-indeksowaną lub 1-indeksowaną.

Przypadki testowe:

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

Wyjaśnienia są zachęcane, jak zawsze.

To jest OEIS A000975 .

Python 2 , 36 bajtów

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

Wypróbuj online! Objaśnienie: Binarna reprezentacja polega na tym, że wystarczy pomnożyć ją przez odpowiednią potęgę 2 i wziąć część całkowitą.$\frac{2}3$0.101010101...

05AB1E , 4 bajty

2 bajty zapisane przy użyciu sztuczki Neila 2/3

Lo3÷

Wypróbuj online!

Wyjaśnienie

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

05AB1E , 6 bajtów

TRI∍ηC

Wypróbuj online!

Wyjaśnienie

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

Galaretka , ... 4 bajty

Dzięki mile za -1 bajtów!

ḶḂḄƤ

Wypróbuj online!

Wyjaśnienie:

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

Galaretka , 4 bajty

Wersja Jonathana Allana.

Ḷ€ḂḄ

Wypróbuj online!

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

Wersja oparta na sztuczce Neila 2/3 daje 5 bajtów, zobacz historię zmian.

MATL , 5 bajtów

:WI/k

Na podstawie odpowiedzi Neila .

Wyjaśnienie

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

Wypróbuj online!

MATL , 9 bajtów

:q"@:oXBs

Wypróbuj online!

Wyjaśnienie

:       % 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 bajtów

^{-3 bajty dzięki user202729
-1 bajtów dzięki matmandan}

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

Wypróbuj online!

Python 3, 68 61 54 48 43 bajtów

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

Podziękowania dla user202729 za pomoc w oszczędzaniu 19 bajtów i ovs za pomoc w oszczędzaniu 6 bajtów.

Wypróbuj online

Łuska , 7 bajtów

mḋḣ↑Θݬ

Wypróbuj online!

Na podstawie 1, więc wejście n daje pierwsze n wyników.

Wyjaśnienie

     ݬ   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 bajtów ^SBCS

Przyjmuje się ⎕IO( I ndex O rigin) 0, co jest domyślne w wielu systemach. Anonimowa ukryta funkcja prefiksu. 1-indeksowany.

(2⊥⍴∘1 0)¨⍳

Wypróbuj online!

⍳ d ndices 0… n − 1

(… )¨ Zastosuj następującą funkcję ukrytą dla każdego

 ⍴∘1 0 cyklicznie przekształcaj listę [1,0]do tej długości

 2⊥ konwersja z bazy-2 (binarnej) na liczbę normalną

Perlv5.10 -n , 24 + 1 bajtów

-3 bajty dzięki Nahuelowi Fouilleulowi !

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

Wypróbuj online!

Ta sama logika co moja wersja Ruby, ale krótsza, ponieważ perl jest bardziej zwięzły. Z jakiegoś dziwnego powodu, printnie zrobiłby SEPERATOR (psiakrew!), Więc musiałem skorzystać sayz v5.10;celem tego uciekać, ja nie wiem, jak zdobyć to, więc wyjeżdżam go teraz ?. ..

Wyjaśnienie

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 bajty

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

Wypróbuj online!

APL (Dyalog) , 7 bajtów

⌊3÷⍨2*⍳

Wypróbuj online!

APL (Dyalog) , 11 bajtów

(2⊥2|⍳)¨1+⍳

Wypróbuj online!

Zastosowania ⎕IO←0.

C , 81 55 59 bajtów

1 indeksowany.

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

Pełny program, mniej golfa:

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

Wypróbuj online!

EDYCJA 2: Zakładałem, że funkcje nie muszą być wielokrotnego użytku teraz, kiedy o tym myślę, to jest całkowicie sensowne, że będą musiały być wielokrotnego użytku: P

EDYCJA: Miałem błędne przekonanie, że musiałem uwzględnić cały program w odpowiedzi, okazuje się, że potrzebowałem tylko funkcji, która to robi. To miłe.

Jestem całkiem pewien, że mogę zgolić kilka bajtów tu i tam. Użyłem już kilku sztuczek. Duża część programu jest poświęcona zdobyciu argumentu i przekształceniu go w int. To jest mój pierwszy golfowy kod. Jeśli coś robię źle, powiedz mi: P

Haskell , 47 40 53 49 44 40 34 bajtów

-4 bajty dzięki użytkownikowi202729
-6 bajtów dzięki Laikoni

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

Wypróbuj online!

Rubinowy , 26 bajtów

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

Wypróbuj online!

Pokonuje wszystkie starsze rubinowe odpowiedzi.

Wyjaśnienie

1/3wygląda na dwójkowy 0.01010101..., więc jeśli pomnożymy to przez potęgę dwóch, otrzymamy:

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

Ale Ruby podaje liczby przy podziale wewnętrznym, podając mi potrzebną sekwencję.

J , 9 bajtów

[:#.\2|i.

Jak to działa?

i. - lista 0..n-1

2| - elementy listy mod 2

\ - wszystkie prefiksy

#. - po przecinku

[: - ogranicza widelec (ponieważ mam parzystą liczbę (4) czasowników)

Wypróbuj online!

Siatkówka , 28 bajtów

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

Wypróbuj online!

Oparte na 0, więc wejście n daje pierwsze n + 1 wyników.

Wyjaśnienie

Wykorzystuje rekurencję z OEIS:

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

Przejdźmy przez program:

)K`0

Jest to stały etap: odrzuca dane wejściowe i ustawia ciąg roboczy 0na wartość początkową sekwencji. )Otacza ten etap w grupie. Ta grupa sama nie robi nic, ale prawie każdy etap (w tym etapy grupy) zapisuje swój wynik w dzienniku, a 0do działania programu potrzebujemy dwóch kopii tego dziennika.

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

Jest tu kilka konfiguracji: "$+"+owija scenę w pętlę. "$+"Są traktowane jako zmiany i $+oznacza wejście programu, to znaczy n . Oznacza to, że pętla jest uruchamiana n razy.

Następnie ¶<owija każdą iterację w stopień wyjściowy, który drukuje dane wejściowe stopnia z końcowym przesuwem linii (więc pierwsza iteracja drukuje zero, druga iteracja drukuje wynik pierwszej iteracji itd.).

Sam etap zastępuje cały ciąg roboczy podstawieniem w ostatnim wierszu. Ten korzysta z niejawnego nawiasu zamykającego i niejawnych argumentów dla operatora powtarzania *, więc w rzeczywistości jest to skrót od:

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

Elementy w nawiasach można podzielić na trzy części:

• $&*_: daje ciąg (n-1) _ s.
• _: daje singiel _.
• 2*$-1*_: daje ciąg 2 * a (n-1) _ . $-1Odnosi się do wyniku przedostatniego w dzienniku wynikowego, czyli iteracji pętli przed ostatnim. Dlatego musieliśmy na początku skopiować zero w logu, w przeciwnym razie odnosi się to do danych wejściowych programu przy pierwszej iteracji.

Następnie $.(…)mierzy długość wynikowego ciągu. Innymi słowy, obliczyliśmy a(n) = a(n-1) + 1 + 2*a(n-2)przechodząc przez jednoargumentowy (ale nie bardzo: $.(…)jest leniwy i tak naprawdę nie ocenia jego zawartości, jeśli może określić wynikową długość bezpośrednio za pomocą arytmetyki, więc jest to nawet całkiem wydajne).

Wynik końcowej iteracji pętli ( n + 1- ty element sekwencji) jest drukowany z powodu niejawnego wyjścia Retiny na końcu programu.

Brain-Flak , 36 bajtów

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

Wypróbuj online!

Wyjaśnienie:

Kolejną liczbę w sekwencji uzyskuje się za pomocą n*2+1lub 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

Rubin 42 41 43 41 37 35 31 33 30 bajtów

-2 bajty dzięki Unihedron

-3 bajty dzięki GB

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

Wypróbuj online!

> <> , 22 + 3 (flaga -v) bajtów

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

Wypróbuj online!

Wyjaśnienie

Stos zostanie zainicjowany za pomocą licznika pętli.

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 bajtów

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

Port odpowiedzi @Neil na Python 2 .
1 indeksowane i wyprowadzane bezpośrednio, każda wartość w oddzielnej linii.

Wyjaśnienie:

Wypróbuj online.

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

Odpowiedź na stare 80 bajtów:

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

1 indeksowane wejście i rozdzielane spacjami Stringwyjście

Wyjaśnienie:

Wypróbuj online.

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 bajtów

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

Wypróbuj (35)

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

Wypróbuj (30)

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

Wypróbuj (30)

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

Wypróbuj (27)

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

Wypróbuj (25)

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

Wypróbuj (20)

Rozszerzony:

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

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

Wypróbuj online!

Python 2 , 34 bajty

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

Wypróbuj online!

Zwraca w odwrotnej kolejności.

C, 47 46 bajtów

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

Akumulator azaczyna się od zera. Na każdym kroku podwajamy go ( a+=a) i dodajemy jeden, jeśli poprzedni najmniej znaczący bit wynosił zero ( !(a%2)lub równoważnie,-(~a)%2 ).

Program testowy

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

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

Wyniki

$ ./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 bajtów

Wszystkie pochodzą niezależnie od innych rozwiązań.

1-indeksowany.

õ!²mz3

Spróbuj

Wyjaśnienie

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

Spróbuj

Wersja 7-bajtowa

õ_ou ì2

Spróbuj

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

Wersja 9-bajtowa

õ_îA¤w)n2

Spróbuj

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

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

Wypróbuj online!

MATL , 7 bajtów

:&+oRXB

Wypróbuj online!

Wyjaśnienie:

         % 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

Dane wyjściowe byłyby, 0, 1, 2, 5 ...gdyby Pzostały dodane na końcu ( flip), co daje 8 bajtów.

Rubin -n ,32 30 + 1 bajtów

Ponieważ mamy dokładnie 1 linię wprowadzania, $.jest bosko wygodne!

EDYCJA: Dziwię się, że sam zdołałem wygrać z golfem, ale wydaje się, że użycie, -nktóre liczy się jako 1 (zgodnie z regułą 2 w domyślnych specjalnych warunkach , ponieważ Ruby można uruchomić z ruby -e 'full program'(a więc -n1), których wszystkie wystąpienia getssą używane tylko raz zostań golfem w dół 1 char w ten sposób; Wierzę, że jest to kamień milowy dla ruby, proszę głośno, jeśli nie zgadzasz się z tym tokiem myślenia, zanim będę go ponownie używać w przyszłości)

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

Wypróbuj online!

Wyjaśnienie

# 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 bajtów

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

Wypróbuj online!

Używa formuły bezwstydnie skradzionej z tej drugiej odpowiedzi Ruby.

Chociaż nie a=0działałby (awk traktuje „pusty” jako 0), pierwszy element 0 nie zostanie wydrukowany i zamiast tego będzie emptywierszem, który, jak twierdzę, jest prawidłowym wyjściem, prawdopodobnie nie przejdzie, więc jest to, a=0co może wstawić jako argument wiersza poleceń.

C, 52 bajty

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

1-indeksowany

Wypróbuj online!

pieprzenie mózgu , 40 bajtów

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

Wypróbuj online!

0-indeksowane. Wprowadź jako kod char, wyślij jako unarny z bajtami zerowymi oddzielającymi serię kodu char 1s. Zakłada komórki 8-bitowe, chyba że chcesz wprowadzić więcej niż 255. Zakłada komórki ujemne, chociaż można to naprawić kosztem kilku bajtów.

Poprzednio 50 bajtów

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

Wypróbuj online!

Wejścia jako kod char, wyjścia jako kod char. 1-indeksowany. Prawdopodobnie można trochę zagrać w golfa.

@Unihedron wskazuje, że zapomniałem podać, że wymaga to komórek o nieskończonych rozmiarach, w przeciwnym razie osiągnie ósmą liczbę.