Remarquez que lorsque je dis "nier", je veux dire remplacer tous les zéros (c'est-à-dire une négation au niveau du bit)

La séquence Thue-Morse va comme 01101001

La façon dont vous le générez est:

Commencez par prendre 0. Niez ce qui reste et ajoutez-le à la fin.

Alors, prends 0. Niez-le et ajoutez-le à la fin -01

Ensuite, prenez cela et niez-le et ajoutez cela à la fin - 0110

Etc.

Une autre propriété intéressante de ceci est que la distance entre les zéros crée une chaîne "irrationnelle" et non répétitive.

Donc:

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

Pouvez-vous écrire un programme qui, lors de la saisie de n, produira les n premiers chiffres de la chaîne à imprimer?

C'est le golf de code, donc le plus petit nombre d'octets gagne!

Gelée, 9 octets

;¬$‘¡TI’ḣ

Essayez-le en ligne!

Comment ça fonctionne

;¬$‘¡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 octets

Il s'agit d'une solution assez rudimentaire basée sur la construction d'une séquence ternaire Thue-Morse à partir de zéro. Cette séquence est identique à celle demandée, bien que quelqu'un d'autre devra écrire une explication plus approfondie de la raison. En tout cas, cette séquence n'est qu'une modification triviale de celle-ci, A036580 .

Edit: changé la boucle for en une compréhension de liste, changé d'une fonction en un programme, et changé le tout en Python 2. Merci à Dennis pour son aide au golf.

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 octets

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

Il s'agit d'une fonction anonyme qui accepte un entier et renvoie un tableau d'entiers. Pour l'appeler, affectez-le à une variable.

Nous générons la séquence Thue-Morse permutée en bits en commençant par un entier m = 1, puis nous ajoutons 1-mà mun tableau des n+1heures, où nest l'entrée. Cela génère plus de termes que nous n'en avons besoin. Nous localisons ensuite celles qui utilisent find(m), obtenons la différence entre les valeurs consécutives en utilisant diffet soustrayons 1 élément par élément. Prendre les premiers ntermes du tableau résultant nous donne ce que nous voulons.

Enregistré 6 octets et résolu un problème grâce à Dennis!

PowerShell, 102 octets

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

Un peu d'une manière différente de calculer. PowerShell ne dispose pas d'un moyen simple pour "obtenir tous les indices de ce tableau où la valeur à cet index est telle ou telle ", nous devons donc être légèrement créatifs.

Ici, nous utilisons A001969 , les "nombres avec un nombre pair de 1 dans leur expansion binaire", qui donne complètement par coïncidence les indices des 0 dans la séquence Thue-Morse. ;-)

Le filtercalcule ce nombre. Par exemple, x 4donnerait 9. Nous bouclons ensuite simplement à partir 0de notre entrée $args[0], en soustrayant 1car nous sommes indexés sur zéro, et chaque itération de la boucle affiche la différence entre le nombre suivant et le nombre actuel. La sortie est ajoutée au pipeline et sortie implicitement avec des retours à la ligne.

Exemple

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

Haskell, 42 octets

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

Exemple d'utilisation: (`take`l) 7-> [2,1,0,2,0,1,2].

Il est une mise en œuvre de a036585_listpartir A036585 décalée vers le bas à 0, 1et 2. Golf: concat (map f l)c'est f =<< let f 0=[0,1,2]; f 1=[0,2]; f 2=[1]c'est ([[0..2],[0,2],[1]]!!).

Remarque: lest la séquence infinie. Il faut 10 octets, soit environ 25% pour implémenter la fonction de prise en premier des néléments.

Mathematica, 79 68 70 octets

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

MATL , 14 11 octets

Q:qB!Xs2\dQ

Essayez-le en ligne!

Comme l'a souligné @TimmyD dans sa réponse , la séquence souhaitée est donnée par les différences consécutives de A001969 . Cette dernière peut à son tour être obtenue sous la forme de la séquence de Thue-Morse plus 2 * n . Par conséquent, la séquence souhaitée est donnée par les (différences consécutives de la séquence de Thue-Morse) plus un .

En revanche, la séquence Thue-Morse peut être obtenue comme le nombre de uns dans la représentation binaire de n , à partir de 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 octets

Code:

ÎFDSÈJJ}¥1+¹£

Explication:

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

Essayez-le en ligne!

Python, 69 octets

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

Le iterme e de cette séquence est 1+t(i+1)-t(i), où test la fonction Thue-Morse. Le code l'implémente récursivement, ce qui est plus court que

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

Mathematica, 65 octets

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

Beats mon autre réponse, mais ne bat pas l'extra- version golfée épicée . Maintenant, normalement, je colle mon code entre guillemets, puis je le retire car Mathematica aime ajouter des espaces à votre code (qui ne font rien) mais il ne dérange jamais les chaînes, mais cela ne fonctionne pas pour le code qui a lui-même des guillemets ...

Quoi qu'il en soit, j'utilise simplement la magie intégrée pour cela. La sortie est une chaîne.

Mathematica, 58 octets

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

Perl, 45 + 2 = 47 octets

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

Nécessite le drapeau -pet -a:

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

Port de @ Sherlock9 réponse

9 octets enregistrés grâce à Ton

JavaScript (ES6), 73 67 octets

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

Port de @ Sherlock9's answer.

edit: 6 octets enregistrés grâce à @WashingtonGuedes.

CJam (19 octets)

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

Démo en ligne

Cela utilise l'approche consistant à incrémenter les différences successives entre les éléments de la séquence de Thue-Morse.

Mon approche la plus courte utilisant des règles de réécriture est de 21 octets:

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

(Attention: lent). Cela code les règles de réécriture

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

comme

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

Rubis, 57 octets

Un port de réponse Python de xnor. Les changements se situent principalement dans la déclaration ternaire tà la place de la andraison d' 0être véridique dans Ruby, et d'utiliser (1..n).mapet 1+t[i]-t[i-1]d'économiser des octets par rapport à l'importation directe de la compréhension de la liste.

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

Mathematica ( presque non verbal), 107 110 octets

({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)[[;;#]]&

La séquence est générée par l'application répétée d'une règle de remplacement. Une autre règle le transforme en sortie souhaitée. Si suffisamment de personnes sont intéressées, je vais vous expliquer en détail.

version non alphanumérique

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

comme suggéré par CatsAreFluffy.