Print the difference in the Thue-Morse sequence
Python 3 2, 104 92 88 84 bytes
This is a pretty rudimentary solution based on building a ternary Thue-Morse sequence from scratch. This sequence is identical to the one being asked, though someone else will have to write a more thorough explanation of why that is. At any rate, this sequence is only a trivial modification of this one, A036580.
Edit: Changed the for loop into a list comprehension, changed from a function to a program, and changed the whole thing to Python 2. Thanks to Dennis for golfing help.
n=input()
s="2"
while len(s)<n:s="".join(`[1,20,210][int(i)]`for i in s)
print s[:n]
Mathematica, 79 68 70 bytes
(Differences[Join@@Position[Nest[#~Join~(1-#)&,{0},#+2],0]]-1)[[;;#]]&
Julia, 56 50 bytes
n->(m=1;[m=[m;1-m]for _=0:n];diff(find(m))[1:n]-1)
This is an anonymous function that accepts an integer and returns an integer array. To call it, assign it to a variable.
We generate the bit-swapped Thue-Morse sequence by starting with an integer m = 1
, then we append 1-m
to m
as an array n+1
times, where n
is the input. This generates more terms than we need. We then locate the ones using find(m)
, get the difference between consecutive values using diff
, and subtract 1 elementwise. Taking the first n
terms of the resulting array gives us what we want.
Saved 6 bytes and fixed an issue thanks to Dennis!