# Print the difference in the Thue-Morse sequence

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!

• Not requiring a specific base for the output seems loopholey. The Thue-Morse sequence itself is the desired output, in unary and with 0 as separator. Mar 14, 2016 at 19:04
• oeis.org/A036577
– xnor
Mar 14, 2016 at 21:40

# Python 3 2, 1049288 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]


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

## 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  • The relation with A001969 is a great finding! Mar 14, 2016 at 22:53 ## Haskell, 42 bytes l=2:(([[0..2],[0,2],[1]]!!)=<<l) (takel)  Usage example: (takel) 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. # Mathematica, 7968 70 bytes (Differences[Join@@Position[Nest[#~Join~(1-#)&,{0},#+2],0]]-1)[[;;#]]&  • Fails for n<3. Mar 14, 2016 at 20:54 # 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  • May I request parenthesization in (consecutive differences of the Thue-Morse sequence) plus 1? Mar 15, 2016 at 2:37 • @CatsAreFluffy You are totally right. Done Mar 15, 2016 at 9:50 # 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.


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

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


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

• We now have 4 Mathematica answers: My original, the nonverbal one (it's 5 if the symbolonly one counts), the extra-golfed one, and my magic builtin. Mar 15, 2016 at 16:06

# Mathematica, 58 bytes

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

• How do I know you didn't take my solution and golf it? Mar 15, 2016 at 0:14
• @catsarefluffy I did adapt your idea to generate the sequence (golfing it by cutting the infix operator), but felt that the method used here of transforming that into the intended output was very different and more suited to a new answer than a suggested edit. Mar 15, 2016 at 0:54
• @catsarefluffy I've just seen your edit. the last I'd seen it was in its original form when I did this. I'll remove this answer but you'll just have to trust me that it was independent :) Mar 15, 2016 at 0:56
• 1;;# can be replaced with simply ;;#. Mar 15, 2016 at 1:23
• Actually I got the output transform from TimmyD's answer. (Specifically, the first paragraph made me remember about Position.) Mar 15, 2016 at 2:32

# 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


• The -a option gives you a free copy of the input, so $_=2;s/./(1,20,210)[$&]/ge until/.{@F}/;$_=$& Mar 15, 2016 at 13:02
• @TonHospel Thats perfect, can't believe I didn't think of that :-) And I can save the -p with -E: say$& at the end if we assume that Perl > v5.18 Mar 15, 2016 at 13:17 ## 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. • Would !s[n] work in place of s.length<n ? Or maybe just s[n] with ?: inverted? Mar 15, 2016 at 11:49 ## 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  # 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]}}  • 0 is truthy? How does that work?? Mar 15, 2016 at 16:06 • @CatsAreFluffy In my experience, poorly Mar 15, 2016 at 16:47 # 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. • I think it's safe to assume that people are sufficiently interested in an explanation for just about any answer. Speaking only for myself, I don't upvote submissions without explanations (unless the approach is obvious). Mar 14, 2016 at 21:13 • And if you turn all letters into sequences of $ and replace 0 with x-x (where x is an unused sequence of $) (and use (x-x)! for 1 (ditto)), we be alphanumeric-free. Mar 15, 2016 at 0:12 • Bytesave: Use {x__} instead of _[x__] Mar 15, 2016 at 2:39 • I'm actually pretty sure that Mathematica is Turing-complete on symbols only or $[_]:=-/; (both by counter machine emulation) Mar 15, 2016 at 16:04