Обратите внимание: когда я говорю «отрицание», я имею в виду замену всех единиц нулями (то есть побитовое отрицание)

Последовательность Туэ-Морса имеет вид 01101001

То, как вы генерируете это:

Начните с получения 0. Отрицайте то, что осталось, и добавьте его до конца.

Итак, бери 0. Отрицайте это и добавьте это к концу -01

Затем возьмите это и отрицайте это и добавьте это к концу - 0110

И так далее.

Еще одним интересным свойством этого является то, что расстояние между нулями создает «иррациональную» и неповторяющуюся строку.

Так:

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

Можете ли вы написать программу, которая при вводе n будет выводить первые n цифр строки для печати?

Это код гольф, поэтому выигрывает самое короткое количество байтов!

Желе, 9 байт

;¬$‘¡TI’ḣ

Попробуйте онлайн!

Как это работает

;¬$‘¡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 байта

Это довольно элементарное решение, основанное на построении троичной последовательности Туэ-Морса с нуля. Эта последовательность идентична запрашиваемой, хотя кому-то еще придется написать более подробное объяснение, почему это так. Во всяком случае, эта последовательность является лишь тривиальной модификацией этой последовательности, A036580 .

Редактировать: Изменил цикл for в понимание списка, изменил функцию на программу и изменил все это на Python 2. Спасибо Деннису за помощь в игре в гольф.

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

Юлия, 56 50 байт

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

Это анонимная функция, которая принимает целое число и возвращает массив целых чисел. Чтобы вызвать его, присвойте его переменной.

Мы генерируем последовательность Туэ-Морса с перестановкой битов, начиная с целого числа m = 1, а затем добавляем 1-mк mмассиву n+1времена, где nнаходится вход. Это создает больше терминов, чем нам нужно. Затем мы находим те, которые используют find(m), получаем разницу между последовательными значениями, используя diff, и вычитаем 1 поэлементно. Взятие первых nчленов полученного массива дает нам то, что мы хотим.

Сохранено 6 байт и исправлена ​​ошибка благодаря Деннису!

PowerShell, 102 байта

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

Немного другой способ вычисления. В PowerShell нет простого способа «получить все индексы в этом массиве, где значение этого индекса равно и тому подобное », поэтому нам нужно проявить немного творчества.

Здесь мы используем A001969 , «числа с четным числом 1 в их двоичном разложении», что полностью совпадает с индексами 0 в последовательности Туэ-Морса. ;-)

filterВычисляет это число. Например, x 4дал бы 9. Затем мы просто возвращаемся 0к нашему вводу $args[0], вычитая, 1потому что мы проиндексированы нулями, и каждая итерация цикла выводит разницу между следующим числом и текущим числом. Вывод добавляется в конвейер и неявно выводится с символами новой строки.

пример

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

Haskell, 42 байта

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

Пример использования: (`take`l) 7-> [2,1,0,2,0,1,2].

Это реализация a036585_listот A036585 смещена вниз 0, 1и 2. Гольф: concat (map f l)есть f =<< lи f 0=[0,1,2]; f 1=[0,2]; f 2=[1]есть ([[0..2],[0,2],[1]]!!).

Примечание: lэто бесконечная последовательность. Для реализации функции take-first n-elements требуется 10 байтов или около 25% .

Mathematica, 79 68 70 байт

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

MATL , 14 11 байт

Q:qB!Xs2\dQ

Попробуйте онлайн!

Как указал @TimmyD в своем ответе , желаемая последовательность определяется последовательными отличиями A001969 . Последнее, в свою очередь, может быть получено как последовательность Туэ-Морса плюс 2 * n . Следовательно, желаемая последовательность задается (последовательные различия последовательности Туэ-Морса) плюс один .

С другой стороны, последовательность Туэ-Морса может быть получена как число единиц в двоичном представлении n , начиная с 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 байт

Код:

ÎFDSÈJJ}¥1+¹£

Объяснение:

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

Попробуйте онлайн!

Python, 69 байт

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

iЙ член этой последовательности 1+t(i+1)-t(i), где tфункция Туэ-Морса. Код реализует его рекурсивно, что короче

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

Mathematica, 65 байт

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

Бьет мой другой ответ, но не бьет пряных golfed версии. Теперь обычно я вставляю свой код в кавычки, затем вытаскиваю его, потому что Mathematica любит добавлять пробелы в ваш код (которые ничего не делают), но он никогда не путается со строками, но это не работает для кода, который сам имеет кавычки ...

Как бы то ни было, я просто использую магию, встроенную для этого. Выход - это строка.

Mathematica, 58 байт

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

Perl, 45 + 2 = 47 байт

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

Требуется -pи -aфлаг:

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

Порт @ Sherlock9 ответа

Сохранено 9 байтов благодаря Тон

JavaScript (ES6), 73 67 байт

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

Порт ответа @ Sherlock9.

редактирование: сохранено 6 байтов благодаря @WashingtonGuedes.

CJam (19 байт)

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

Онлайн демо

При этом используется подход увеличения последовательных различий между элементами последовательности Туэ-Морса.

Мой кратчайший подход с использованием правил перезаписи составляет 21 байт:

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

(Предупреждение: медленно). Это кодирует правила переписывания

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

в виде

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

Рубин, 57 байт

Порт ответа xnor на Python. Изменения в основном лежат в тройном заявлении в tместе из - andза 0тот truthy в Ruby, и использовать (1..n).mapи 1+t[i]-t[i-1]для сохранения байт против импорта списка понимания непосредственно.

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

Mathematica ( почти невербальный), 107 110 байтов

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

Последовательность генерируется путем многократного применения правила замены. Другое правило преобразует его в желаемый результат. Если будет достаточно людей, я объясню подробно.

не буквенно-цифровая версия

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

как предложено CatsAreFluffy.