Existem alguns desafios neste site que solicitam que você imprima uma sequência, e isso não é exceção.

(A seguinte explicação da sequência para este desafio assume que os símbolos na sequência são 0e 1.)

A definição recursiva da sequência de Thue-Morse é que

T_0 = 0
T_2n = T_n
T_2n+1 = 1 - T_n

Uma definição mais directa é que a sequência a partir 0de 2**m-1e 2**m to 2**(m+1)-1são complementos binários. Então 0é seguido por 1, 01é seguido por 10, 0110é seguido por 1001e, pulando um pouco adiante, 0110100110010110é seguido por 1001011001101001.

O desafio é escrever um programa ou uma função que imprima a sequência de Thue-Morse para os primeiros nelementos, onde né qualquer número inteiro não negativo. A saída pode usar quaisquer dois símbolos, como mostrado nos exemplos abaixo.

Exemplos

>>> tm_01(20)
01101001100101101001
>>> tm_ab(42)
abbabaabbaababbabaababbaabbabaabbaababbaab
>>> tm_paren(37)
())()(())(()())()(()())(())()(())(()(
>>> tm_space_star(12)
 ** *  **  *
>>> tm_01(0)
                # to show that this is a valid input

Regras

• A entrada será qualquer número inteiro não negativo. Você pode assumir que todas as entradas são válidas.

• A saída deve ser o primeiro nelemento da sequência Thue-Morse, usando quaisquer símbolos que sejam convenientes. Se desejar, você também pode adicionar um separador. Nos meus exemplos, eu não tenho. Nota: Esta regra permite listas (como as do Python), como ,é um separador válido e não me importo com caracteres iniciais ou finais, como [e ]na saída.

• Isso é código de golfe, então o menor número de bytes vence.

Como sempre, se o problema não estiver claro, entre em contato. Boa sorte e bom golfe!

Catálogo

var QUESTION_ID=65549;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}

body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>

Pitão, 6 bytes

xMjR2Q

Experimente online: Demonstração

Com base na solução de @ThomasKwa e uma variação de @FryAmTheEggman.

Ele utiliza o seguinte formular: o idígito -ésimo na sequência Thue-Morse é: xor(digits of i in base 2).

Explicação:

xMjR2Q   implicit: Q = input number
  jR2Q   convert each number in [0, 1, ..., Q-1] to its binary digits
xM       xor each binary list

CJam, 17 9 bytes

ri{2b:^}/

ou

ri,2fb::^

Teste aqui.

Explicação

Isso usa a definição alternativa dada na Wikipedia, com base na paridade do número de 1s na representação binária do arquivo n.

ri   e# Read input and convert to integer n.
{    e# For each i from 0 to n-1...
  2b e#   Convert i to base 2.
  :^ e#   Fold XOR over the bits to compute the parity of the number of 1s.
}/

A solução alternativa costuma ,se transformar nexplicitamente em um intervalo [0 ... n-1]antes de usar operadores infix para calcular as representações binárias e o XOR sem precisar de um bloco.

Soluções de bônus

Aqui estão algumas soluções baseadas em outras definições. Se houver duas soluções, a mais curta explodirá a memória muito rapidamente (porque a pré-computação gera 2^nbits antes de truncar para n).

Como um sistema L com 0 --> 01e 1 --> 10:

ri_2mL2,\{2,aA+f=s:~}*<
ri_2,\{2,aA+f=s:~}*<

Negando e anexando a parte anterior:

ri_2mL2,\{_:!+}*<
ri_2,\{_:!+}*<

Usando a relação de recorrência apresentada no desafio, use divmode XOR para distinguir entre as duas definições recursivas:

ri{Ta{2md\j^}j}/

(Embora, é claro, essa relação de recorrência seja apenas uma maneira diferente de expressar a sequência de Thue-Morse como a paridade dos 1 bits na representação binária de n.)

Dyalog APL, 8 7 bytes

≠⌿⍴∘2⊤⍳

Este é um trem monádico que espera uma origem de índice de 0 ( ⎕IO←0). A função não-trem equivalente é {≠⌿(⍵⍴2)⊤⍳⍵}.

Explicação:

      ⍳      List of numbers from 0 to (input-1)
  ⍴∘2        (input) copies of 2
     ⊤       Convert all the elements in ⍳ to base 2 to (input) digits
≠⌿           Reduce over the first axis by not-equal

Saída é uma lista separada por espaços de 0e 1. Experimente aqui .

Mathematica, 35 21 bytes

O Mathematica possui um built-in para a sequência Thue-Morse!

Array[ThueMorse,#,0]&

Resposta original:

#&@@@DigitCount[Range@#-1,2]~Mod~2&

LabVIEW, 15 primitivas do LabVIEW

agora como gif super chique com uma sonda

J, 12 11 bytes

@ MartinBüttner salvou um byte.

~:/@#:"0@i.

Esta é uma função monádica (ou seja, unária), usada da seguinte maneira:

   f =: ~:/@#:"0@i.
   f 10
0 1 1 0 1 0 0 1 1 0

Explicação

Estou usando a definição alternativa de que T _n é a paridade do número de 1 bits na representação binária de n.

~:/@#:"0@i.  Input is n.
~:/          Output is XOR folded over
   @#:       the binary representations of
      "0     each element of
        @i.  integers from 0 to n-1.

Pitão, 11 10 bytes

m%ssM.Bd2Q

Saídas como uma lista no estilo Python.

Japonês , 29 11 bytes

Uo ®¤¬r@X^Y

Experimente online!

Produz diretamente como uma matriz, que economiza cerca de 4 bytes.

Ungolfed e explicação

Uo ®   ¤  ¬ r@  X^Y
Uo mZ{Zs2 q rXY{X^Y}}
        // Implicit: U = input number
Uo      // Create an array of integers in the range `[0, U)`. 
mZ{Zs2  // Map each item Z in this range to Z.toString(2),
q rXY{  //  split into chars, and reduced by
X^Y}}   //   XORing.
        //  This returns (number of 1s in the binary string) % 2.
        // Implicit: output last expression

Editar: agora você pode usar o seguinte código de 8 bytes (não válido; recurso publicado após este desafio):

Uo ®¤¬r^

Haskell, 39 36 35 bytes

take<*>(iterate([id,(1-)]<*>)[0]!!)

Experimente online!

Como funciona: comece com [0]e aplique os tempos de x ++ invert xfunção n. Pegue os primeiros nelementos da lista resultante. Graças à preguiça de Haskell, apenas os primeiros nelementos são realmente calculados. Nota: o primeiro <*>está no contexto da função, o segundo no contexto da lista.

Com o GHC v8.4 (que não estava disponível no momento do desafio), há uma solução de 34 bytes:

take<*>(iterate(id<>map(1-))[0]!!)

Edit: -3 resp. -4 bytes graças a @Laikoni. -1 byte graças a @ Ørjan Johansen.

Haskell, 54 bytes

Menos compacto que a solução de nimi, mas eu não queria negar a você essa parte da ofuscação do código funcional. Funciona para qualquer par de objetos; por exemplo, você pode substituir (f 0.f 1)por (f 'A'.f 'B').

Com base na definição de que os primeiros 2 ⁿ dígitos são seguidos pela mesma sequência de dígitos invertidos. O que fazemos é criar duas listas lado a lado; um para a sequência, um para o inverso. Anexamos continuamente partes cada vez mais longas de uma lista à outra.

A implementação consiste em três definições:

t=(f 0.f 1)t
f c=flip take.(c:).g 1
g n l=l n++g(n+n)l

A função taceita qualquer número e retorna a sequência Thue-Morse desse comprimento. As outras duas funções são ajudantes.

• Função frepresenta uma das listas; f 0é para a sequência, f 1para o inverso.
• A função gcuida de acrescentar repetições cada vez mais longas de uma lista à outra.

Fiddle: http://goo.gl/wjk9S0

Pari / GP , 33 bytes

n->[sumdigits(x,2)%2|x<-[0..n-1]]

Experimente online!

Burlesco, 21 bytes

{0}{J)n!_+}400E!jri.+

Exemplos:

blsq ) "20"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1}
blsq ) "42"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1}

Explicação:

{0}      -- setup
{J)n!_+} -- duplicate, map invert, concatenate
400E!    -- do 400 times (this will eventually run
            out of memory).
jri.+    -- take n elements

Sem a jri.+parte, você ficará sem memória (porque calculará a sequência morse de um número incrivelmente grande ). Mas como Burlesque é preguiçoso, apenas pedir o primeiro n-elemento funcionará de qualquer maneira.

K5, 27 13 bytes

{x#((log x)%log 2){x,~x}/0}

Calcular a sequência é bastante fácil, o problema é evitar o cálculo excessivo. Podemos reconhecer que a fácil expansão da sequência nos dá uma sequência de cordas que são potências sucessivas de duas de comprimento. Tomar a base de log 2 da entrada e arredondar para cima nos dará o suficiente para trabalhar e, em seguida, podemos reduzi-la ao tamanho apropriado:

  {x#((log x)%log 2){x,~x}/0}'(20 42 37 12 0)
(0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0
 0 1 1 0 1 0 0 1 1 0 0 1
 ())

Editar:

Uma solução baseada em paridade:

~=/'(64#2)\'!

Em ação:

  ~=/'(64#2)\'!20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Observe que, como o K5 não possui uma primitiva arbitrária de conversão para binário, preciso especificar, por exemplo, uma decodificação de 64 bits. O K5 não usa matemática de precisão arbitrária; portanto, haverá um limite para o tamanho das entradas com as quais podemos lidar em qualquer caso.

Oitava, 33 31 bytes

Economizou 2 bytes graças a Thomas Kwa.

@(n)mod(sum(dec2bin(0:n-1)'),2)

Perl 5, 62 49 bytes

Sim, não é o melhor idioma para este, mas ainda gosto do jeito que ele saiu. Requer 5.14+ para /re say.

sub{$_=0;$_.=y/01/10/r while$_[0]>length;say substr$_,0,$_[0]}

O uso da definição de paridade requer 5,12+ para say:

sub{say map{sprintf("%b",$_)=~y/1//%2}0..$_[0]-1}

Prolog (SWI), 115 bytes

Código:

N*X:-N>1,R is N//2,R*Y,X is(N mod 2)xor Y;X=N.
p(N):-M is N-1,findall(E,between(0,M,E),L),maplist(*,L,K),write(K).

Explicado:

N*X:-                                 % Calculate Thue-Morse number at index N
     N>1,                             % Input is bigger than 1
     R is N//2,R*Y,X is(N mod 2)xor Y % Thue-Morse digit at index N is binary digits of N xor'ed
     ;X=N.                            % OR set X to N (end of recursion)
p(N):-
      M is N-1,                       % Get index of Nth number
      findall(E,between(0,M,E),L),    % Make a list of number 0->N-1
      maplist(*,L,K),                 % Map * on list L producing K
      write(K).                       % Print K

Exemplo:

p(20).
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

Experimente online aqui

Retina , 70 69 bytes

Usando a definição como um sistema L com palavras 0e produções iniciais 0 --> 01e 1 --> 10.

^
0;
(T`d`ab`^(.)+;(?!(?<-1>.)+$)
a
01
)`b
10
!`^(?=.*;(.)+)(?<-1>.)+

A entrada é recebida em unário .

Você pode executar o código de um único arquivo com o -ssinalizador. Ou apenas tente online.

Explicação

^
0;

Anexa 0;à entrada, onde 0está a palavra inicial e ;é apenas um separador.

(T`d`ab`^(.)+;(?!(?<-1>.)+$)

A (indica que este é o início de um laço (que se repete até que o circuito deixa de alterar a cadeia). Esse estágio se transforma 0e se transforma 1em ae brespectivamente (porque se dexpande para 0-9). Ele faz isso desde que a palavra atual (cujo comprimento é medido com (.)+seja menor que a entrada (ou seja, desde que não possamos ler o final da string combinando tantos 1s quanto temos na palavra).

a
01

Substitua a( substitua 0) por 01.

)`b
10

Substitua b( substitua 1) por 10. Este também é o fim do loop. Os termina laço assim que as condições na fase transliteração falhar, porque então todas as 0s e 1s permanecerá inalterada e as outras duas fases não vai encontrar nada para corresponder.

!`^(?=.*;(.)+)(?<-1>.)+

O último passo é truncar a palavra para o comprimento da entrada. Desta vez, medimos o comprimento da entrada (.)+em um lookahead. Em seguida, combinamos muitos caracteres desde o início da string.

Ruby, 33

->n{n.times{|i|p ("%b"%i).sum%2}}

Ligue assim:

f=->n{n.times{|i|p ("%b"%i).sum%2}}
f[16]

Usa o fato de que a paridade de números binários forma a sequência de três-morse.

O caractere separador é nova linha. Converte o número iem uma string binária e calcula a soma de todos os códigos ASCII, módulo 2.

Se a nova linha não for um separador aceitável, o seguinte não terá separador para 2 bytes adicionais:

->n{n.times{|i|$><<("%b"%i).sum%2}}

MATL , 9 bytes

Essa linguagem foi projetada após o desafio .

Abordagem 1: 13 bytes

Isso cria a sequência concatenando cópias negadas de blocos de tamanho crescente.

itBFw"t~h]w:)

Exemplo

>> matl itBFw"t~h]w:)
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Explicação

i           % input number, say "N"
tB          % duplicate and convert to binary. Produces a vector
F           % initialize sequence to "false"
w           % swap to bring vector to top
"           % for loop. There will be at least log2(N) iterations
  t~h       % duplicate, negate, concatenate
]           % end for
w           % swap
:)          % index with vector 1, 2, ..., N

Abordagem 2: 9 bytes

Isso usa a mesma abordagem que a resposta de Alefalpha .

i:1-B!s2\

Exemplo

>> matl i:1-B!s2\
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Explicação

i           % input "N" 
:1-         % create vector 0, 1, ..., N-1
B           % convert to binary
!           % tranpose
s           % sum
2\          % modulo 2

C, 88 83 bytes

Calcula a paridade para cada posição individual.

i,j;main(int c,char**a){for(;i<atoi(a[1]);putchar(c))for(c=48,j=i++;j;j&=j-1)c^=1;}

Fiddle: http://goo.gl/znxmOk

Gelatina , 4 bytes

ḶB§Ḃ

Observe que esse desafio é mais antigo que o Jelly.

Experimente online!

Como funciona

ḶB§Ḃ  Main link. Argument: n (integer)

Ḷ     Unlength; yield [0, ..., n-1].
 B    Compute the binary representation of each integer in the range.
  §   Take the sum of each binary representation.
   Ḃ  Take the LSB of each sum.

Matlab, 42

Estou usando o fato de que é o mesmo que começar 0e depois repetir o passo de acrescentar o complemento da série atual, nvezes.

t=0;for k=1:input('');t=[t;~t];end;disp(t)

, 11 caracteres / 23 bytes (não competitivo)

Ⓐïⓜ_ⓑⓢĊ⇀$^_

Try it here (Firefox only).

Os círculos são fortes com este.

Bash, 71 66 bytes

Com base na definição de que os primeiros 2 ⁿ dígitos são seguidos pela mesma sequência de dígitos invertidos.

x=0;y=1;while((${#x}<$1));do z=$x;x=$x$y;y=$y$z;done;echo ${x::$1}

$1 como parâmetro é o número desejado de dígitos.

Fiddle: http://goo.gl/RkDZIC

Lote, 115 + 2 = 117 bytes

Com base na resposta do Bash.

@echo off
set x=0
set y=1
set z=0
:a
set x=!x!!y!
set y=!y!!z!
set z=!x:~0,%1!
if !z!==!x! goto a
echo !z!

Precisa de um extra /Vna invocação para permitir o uso de !s.

ES6, 53 bytes

f=(i,x="0",y=1)=>x.length<i?f(i,x+y,y+x):x.slice(0,i)

A recursão parecia mais simples que um loop.

Par , 8 bytes

✶u[Σ_✶¨^

Explicação:

✶          parse implicit input number
 u         range [0..n-1]
  [        map:
   Σ           convert to binary
    _✶         get digit list
      ¨^       fold with xor

Produz algo como:

(0 1 1 0 1 0 0 1)

Matemática ++ , 86 bytes

Usa 0.0\npara 0 e 1.0\npara 1

?>n
3*!!(n-m)>$
m>a
0>k
6+6*!a>$
9-2*!(a%2)>$
a/2>a
5>$
(a-1)/2>a
!k>k
5>$
k
m+1>m
2>$

Arcyóu , 50 55 bytes

Eu tive que adicionar 5 bytes para fazê-lo funcionar corretamente :(

(f i(_(#(l)))(r b^(@(> i 0)(pg 0(% i 2)(: i(#/ i 2))))0

Explicação (com pseudocódigo Pythonesque ao lado:

(f i (_ (# (l)))       ; For i in range(int(input())):
  (r b^                ; Reduce with binary xor
    (@ (> i 0)         ; While i > 0:
      (pg 0            ; Return first of its arguments
        (% i 2)        ; i mod 2
        (: i (#/ i 2)) ; i //= 2
      )
    )
    0                  ; Default reduce argument of 0 for the first bit in the sequence

Lisp comum , 50 bytes

(lambda(n)(dotimes(i n)(princ(mod(logcount i)2))))

Experimente online!