Uwaga: kiedy mówię „neguj”, mam na myśli zastąpienie wszystkich zerami (tzn. Negacją bitową)

Sekwencja Thue-Morse'a wygląda jak 01101001

Sposób jego generowania to:

Zacznij od przyjęcia 0. Neguj to, co zostało, i dołącz do końca.

Więc weź 0. Neguj to i dodaj do końca -01

Następnie weź to i zaneguj i dodaj do końca - 0110

I tak dalej.

Inną interesującą właściwością tego jest to, że odległość między zerami tworzy „irracjonalny” i niepowtarzalny ciąg.

Więc:

0110100110010110
|__|_||__||_|__|
 2  1 0 2 01 2          <------------Print this!

Czy potrafisz napisać program, który po wprowadzeniu n wypisze pierwsze n cyfr ciągu do wydrukowania?

To jest kod golfowy, więc wygrywa najmniejsza liczba bajtów!

Galaretka, 9 bajtów

;¬$‘¡TI’ḣ

Wypróbuj online!

Jak to działa

;¬$‘¡TI’ḣ  Main link. Argument: n

  $        Create a monadic chain that does the following to argument A (list).
 ¬         Negate all items of A.
;          Concatenate A with the result.
   ‘¡      Execute that chain n + 1 times, with initial argument n.
     T     Get all indices of truthy elements (n or 1).
      I    Compute the differences of successive, truthy indices.
       ’   Subtract 1 from each difference.
        ḣ  Keep the first n results.

Python 3 2, 104 92 88 84 bajtów

Jest to dość podstawowe rozwiązanie oparte na budowaniu od podstaw trójskładnikowej sekwencji Thue-Morse. Ta sekwencja jest identyczna z zadawaną, chociaż ktoś inny będzie musiał napisać dokładniejsze wyjaśnienie, dlaczego tak jest. W każdym razie ta sekwencja jest tylko trywialną modyfikacją tej, A036580 .

Edycja: Zmieniłem pętlę for na zrozumienie listy, zmieniłem funkcję z programu i całą rzecz na Python 2. Dzięki Dennis za pomoc w grze w golfa.

n=input()
s="2"
while len(s)<n:s="".join(`[1,20,210][int(i)]`for i in s)
print s[:n]

Julia, 56 50 bajtów

n->(m=1;[m=[m;1-m]for _=0:n];diff(find(m))[1:n]-1)

Jest to anonimowa funkcja, która przyjmuje liczbę całkowitą i zwraca tablicę liczb całkowitych. Aby go wywołać, przypisz go do zmiennej.

Generujemy sekwencję Thue-Morse'a bitów wymieniane zaczynając od liczby całkowitej m = 1, następnie dodać 1-mdo mpostaci tablicy n+1czasu, gdzie njest wejście. To generuje więcej warunków, niż potrzebujemy. Następnie lokalizujemy te za pomocą find(m), uzyskujemy różnicę między kolejnymi wartościami za pomocą diffi odejmujemy 1 elementarnie. Biorąc pierwsze nwarunki wynikowej tablicy daje nam to, czego chcemy.

Zaoszczędziłem 6 bajtów i naprawiłem problem dzięki Dennisowi!

PowerShell, 102 bajty

filter x($a){2*$a+([convert]::toString($a,2)-replace0).Length%2}
0..($args[0]-1)|%{(x($_+1))-(x $_)-1}

Trochę inny sposób obliczeń. PowerShell nie ma łatwego sposobu na „uzyskanie wszystkich indeksów w tej tablicy, w których wartość tego indeksu jest równa takiej i takiej ”, więc musimy być nieco kreatywni.

W tym przypadku używamy A001969 , „liczb z parzystą liczbą 1 w ich rozwinięciu binarnym”, które całkowicie przypadkowo dają indeksy 0 w sekwencji Thue-Morse. ;-)

filterOblicza tę liczbę. Na przykład x 4dałbym 9. Następnie po prostu zapętlamy od 0naszego wejścia $args[0], odejmując, 1ponieważ jesteśmy indeksowani do zera, a każda iteracja pętli wypisuje różnicę między kolejną liczbą a bieżącą liczbą. Dane wyjściowe są dodawane do potoku i domyślnie dane wyjściowe z nowymi liniami.

Przykład

PS C:\Tools\Scripts\golfing> .\print-the-difference-in-the-thue-morse.ps1 6
2
1
0
2
0
1

Haskell, 42 bajty

l=2:(([[0..2],[0,2],[1]]!!)=<<l)
(`take`l)

Przykład użycia: (`take`l) 7-> [2,1,0,2,0,1,2].

Jest to realizacja a036585_listod A036585 przesunięty w dół 0, 1i 2. Gra w golfa: concat (map f l)jest f =<< li f 0=[0,1,2]; f 1=[0,2]; f 2=[1]jest ([[0..2],[0,2],[1]]!!).

Uwaga: ljest sekwencją nieskończoną. Zaimplementowanie funkcji „pierwszeństwo npierwiastków” zajmuje 10 bajtów lub około 25% .

Mathematica, 79 68 70 bajtów

(Differences[Join@@Position[Nest[#~Join~(1-#)&,{0},#+2],0]]-1)[[;;#]]&

MATL , 14 11 bajtów

Q:qB!Xs2\dQ

Wypróbuj online!

Jak wskazał @TimmyD w swojej odpowiedzi , pożądana sekwencja jest podana przez kolejne różnice A001969 . Ten ostatni można z kolei uzyskać jako sekwencję Thue-Morse plus 2 * n . Dlatego pożądana sekwencja jest podana przez (kolejne różnice sekwencji Thue-Morse) plus jeden .

Z drugiej strony sekwencję Thue-Morse'a można uzyskać jako liczbę jedynek w binarnej reprezentacji n , zaczynając od n = 0.

Q:q    % take input n implicitly and generate row vector [0,1,...,n]
B!     % 2D array where columns are the binary representations of those numbers
Xs     % sum of each column. Gives a row vector of n+1 elements
2\     % parity of each sum
d      % consecutive differences. Gives a row vector of n elements
Q      % increase by 1. Display implicitly

05AB1E , 14 13 bajtów

Kod:

ÎFDSÈJJ}¥1+¹£

Wyjaśnienie:

Î              # Push 0 and input
 F     }       # Do the following n times
  DS           # Duplicate and split
    È          # Check if even
     JJ        # Join the list then join the stack
        ¥1+    # Compute the differences and add 1
           ¹£  # Return the [0:input] element

Wypróbuj online!

Python, 69 bajtów

t=lambda n:n and n%2^t(n/2)
lambda n:[1+t(i+1)-t(i)for i in range(n)]

iP określenie tej sekwencji 1+t(i+1)-t(i), gdzie tto funkcja Thue-Morse. Kod implementuje go rekurencyjnie, czyli krócej niż

t=lambda n:bin(n).count('1')%2

Mathematica, 65 bajtów

SubstitutionSystem[{"0"->"012","1"->"02","2"->"1"},"0",#][[;;#]]&

Przebija moją drugą odpowiedź, ale nie pokonuje wyjątkowo pikantnej wersji gry w golfa. Teraz normalnie wstawiam kod w cudzysłów, a następnie go wyciągam, ponieważ Mathematica uwielbia dodawać spacje do kodu (które nic nie robią), ale nigdy nie zadziera z łańcuchami, ale to nie działa dla kodu, który sam zawiera cudzysłowy ...

Cokolwiek, po prostu używam do tego wbudowanej magii. Dane wyjściowe to ciąg znaków.

Mathematica, 58 bajtów

Differences[Nest[Join[#,1-#]&,{0},#]~Position~0][[;;#]]-1&

Perl, 45 + 2 = 47 bajtów

$_=2;s/./(1,20,210)[$&]/ge until/.{@F}/;say$&

Wymaga flagi -pi -a:

$ perl -pa morse-seq.pl <<< 22                                                                            
2102012101202102012021

Port odpowiedzi @ Sherlock9

Zaoszczędź 9 bajtów dzięki Ton

JavaScript (ES6), 73 67 bajtów

f=(n,s="2")=>s[n]?s.slice(0,n):f(n,s.replace(/./g,c=>[1,20,210][c]))

Port odpowiedzi @ Sherlock9.

edycja: Zapisano 6 bajtów dzięki @WashingtonGuedes.

CJam (19 bajtów)

1ri){2b:^}%2ew::-f-

Demo online

Wykorzystuje to podejście polegające na zwiększaniu kolejnych różnic między elementami sekwencji Thue-Morse.

Moje najkrótsze podejście przy użyciu reguł przepisywania to 21 bajtów:

ri_2a{{_*5*)3b~}%}@*<

(Ostrzeżenie: wolne). To koduje reguły przepisywania

0  ->  1
1  ->  20
2  ->  210

tak jak

x -> (5*x*x + 1) in base 3

Rubinowy, 57 bajtów

Port odpowiedzi Python na xnor. Zmiany przeważnie leżą w trójskładnikowych oświadczenie w tmiejscu z andpowodu 0bycia truthy w Ruby i korzystania (1..n).mapi 1+t[i]-t[i-1]zapisać bajtów vs. importowania listy bezpośrednio ze zrozumieniem.

t=->n{n<1?n:n%2^t[n/2]}
->n{(1..n).map{|i|1+t[i]-t[i-1]}}

Mathematica ( prawie niewerbalny), 107 110 bajtów

({0}//.{n__/;+n<2#}:>{n,{n}/.x_:>(1-x)/._[x__]:>x}//.{a___,0,s:1...,0,b___}:>{a,+s/.(0->o),0,b}/.o->0)[[;;#]]&

Sekwencja jest generowana przez wielokrotne stosowanie reguły zastępowania. Kolejna reguła przekształca ją w pożądany wynik. Jeśli wystarczająco dużo osób jest zainteresowanych, wyjaśnię to szczegółowo.

wersja niealfanumeryczna

({$'-$'}//.{$__/;+$/#
<($'-$')!+($'-$')!}:>
{$,{$}/.$$_:>(($'-$')
!-$$)/.{$$__}:>$$}//.
{$___,$'-$',$$:($'-$'
)!...,$'-$',$$$___}:>
{$,+$$/.($'-$'->$$$$)
,$'-$',$$$}/.$$$$->$'
-$')[[;;#]]

zgodnie z sugestią CatsAreFluffy.