Print the difference in the Thue-Morse sequence

Question

Note, when I say "negate", I mean replace all ones with zeroes (i.e. a bitwise negation)

The Thue-Morse sequence goes like 01101001

The way you generate it is:

Start by taking 0. Negate what is left and append it to the end.

So, take 0. Negate it and add that to the end - 01

Then take that and negate it and add that to the end - 0110

And so on.

Another interesting property of this is that distance between zeros creates an "irrational" and non-repeating string.

So:

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

Can you write a program that, when input n, will output the first n digits of the string to printed?

This is code golf, so shortest number of bytes wins!

Answer 1

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]

Answer 2

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!

Answer 3

PowerShell, 102 bytes

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

A little bit of a different way of computing. PowerShell doesn't have an easy way to "get all indices in this array where the value at that index equals such-and-such", so we need to get slightly creative.

Here we're using A001969, the "numbers with an even number of 1s in their binary expansion", which completely coincidentally gives the indices of the 0s in the Thue-Morse sequence. ;-)

The filter calculates that number. For example, x 4 would give 9. We then simply loop from 0 to our input $args[0], subtracting 1 because we're zero-indexed, and each iteration of the loop print out the difference between the next number and the current number. Output is added onto the pipeline and implicitly output with newlines.

Example

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

Answer 4

Haskell, 42 bytes

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

Usage example: (`take`l) 7 -> [2,1,0,2,0,1,2].

It's an implementation of a036585_list from A036585 shifted down to 0, 1 and 2. Golfing: concat (map f l) is f =<< l and f 0=[0,1,2]; f 1=[0,2]; f 2=[1] is ([[0..2],[0,2],[1]]!!).

Note: l is the infinite sequence. It takes 10 bytes or about 25% to implement the take-first-n-elements feature.

Answer 5

Mathematica, 79 68 70 bytes

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

Answer 6

MATL, 14 11 bytes

Q:qB!Xs2\dQ

Try it online!

As pointed out by @TimmyD in his answer, the desired sequence is given by the consecutive differences of A001969. The latter can in turn be obtained as the Thue-Morse sequence plus 2*n. Therefore the desired sequence is given by the (consecutive differences of the Thue-Morse sequence) plus one.

On the other hand, the Thue-Morse sequence can be obtained as the number of ones in the binary representation of n, starting from 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

Answer 7

Jelly, 9 bytes

;¬$‘¡TI’ḣ

Try it online!

How it works

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

Answer 8

05AB1E, 14 13 bytes

Code:

ÎFDSÈJJ}¥1+¹£

Explanation:

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

Try it online!

Answer 9

Python, 69 bytes

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

The ith term of this sequence is 1+t(i+1)-t(i), where t is the Thue-Morse function. The code implements it recursively, which is shorter than

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

Answer 10

Mathematica, 65 bytes

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

Beats my other answer, but doesn't beat the extra-spicygolfed version. Now normally I stick my code in quotes, then pull it out because Mathematica loves adding spaces to your code (which do nothing) but it never messes with strings, but that doesn't work for code that itself has quotes...

Whatever, I'm just using the magic builtin for this. Output is a string.

Answer 11

Mathematica, 58 bytes

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

Answer 12

Perl, 45 + 2 = 47 bytes

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

Requires the -p and -a flag:

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

Port of @Sherlock9 answer

Saved 9 bytes thanks to Ton

Answer 13

JavaScript (ES6), 73 67 bytes

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

Port of @Sherlock9's answer.

edit: Saved 6 bytes thanks to @WashingtonGuedes.

Answer 14

CJam (19 bytes)

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

Online demo

This uses the approach of incrementing the successive differences between elements of the Thue-Morse sequence.

---

My shortest approach using rewriting rules is 21 bytes:

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

(Warning: slow). This encodes the rewriting rules

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

as

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

Answer 15

Ruby, 57 bytes

A port of xnor's Python answer. The changes mostly lie in the ternary statement in t in place of the and due to 0 being truthy in Ruby, and using (1..n).map and 1+t[i]-t[i-1] to save bytes vs. importing the list comprehension directly.

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

Answer 16

Mathematica (almost nonverbal), 107 110 bytes

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

The sequence is generated by repeatedly applying a replacement rule. Another rule transforms it to the desired output. If enough people are interested, I'll explain in detail.

non-alphanumeric version

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

as suggested by CatsAreFluffy.