Write out the Thue-Morse sequence

Question

There's quite a few challenges on this site that ask you to print out a sequence, and this is no exception.

(The following explanation of the sequence for this challenge assumes the symbols in the sequence are 0 and 1.)

The recursive definition of the Thue-Morse sequence is that

T_0 = 0
T_2n = T_n
T_2n+1 = 1 - T_n

A more direct definition is that the sequence from 0 to 2**m-1 and 2**m to 2**(m+1)-1 are binary complements. So 0 is followed by 1, 01 is followed by 10, 0110 is followed by 1001, and, skipping ahead a bit, 0110100110010110 is followed by 1001011001101001.

The challenge is to write a program or a function that prints out the Thue-Morse sequence for the first n elements, where n is any non-negative integer. The output can use any two symbols, as shown in the examples below.

Examples

>>> tm_01(20)
01101001100101101001
>>> tm_ab(42)
abbabaabbaababbabaababbaabbabaabbaababbaab
>>> tm_paren(37)
())()(())(()())()(()())(())()(())(()(
>>> tm_space_star(12)
 ** *  **  *
>>> tm_01(0)
                # to show that this is a valid input

Rules

• The input will be any non-negative integer. You can assume all inputs are valid.

• The output must be the first n elements of the Thue-Morse sequence, using any symbols that are convenient. If you like, you can also add a separator. In my examples, I have not. Note: This rule allows lists (like those of Python), as , is a valid separator and I don't mind leading or trailing characters, such as [ and ] in the output.

• This is code golf, so the smallest number of bytes wins.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

Catalogue

var QUESTION_ID=65549;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}

body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>

Answer 1

Pyth, 6 bytes

xMjR2Q

Try it online: Demonstration

Based on the solution from @ThomasKwa and a variation of @FryAmTheEggman.

It uses the following formular: the i-th digit in the Thue-Morse sequence is: xor(digits of i in base 2).

Explanation:

xMjR2Q   implicit: Q = input number
  jR2Q   convert each number in [0, 1, ..., Q-1] to its binary digits
xM       xor each binary list

Answer 2

CJam, 17 9 bytes

ri{2b:^}/

or

ri,2fb::^

Test it here.

Explanation

This uses the alternative definition given on Wikipedia, based on the parity of the number of 1s in the binary representation of the n.

ri   e# Read input and convert to integer n.
{    e# For each i from 0 to n-1...
  2b e#   Convert i to base 2.
  :^ e#   Fold XOR over the bits to compute the parity of the number of 1s.
}/

The alternative solution uses , to turn n explicitly into a range [0 ... n-1] before using infix operators to compute the binary representations and the XOR without needing a block.

Bonus Solutions

Here are some solutions based on other definitions. If there are two solutions, the shorter one will blow up memory very quickly (because the precomputation generates 2^n bits before truncating to n).

As an L-system with 0 --> 01 and 1 --> 10:

ri_2mL2,\{2,aA+f=s:~}*<
ri_2,\{2,aA+f=s:~}*<

By negating and appending the previous part:

ri_2mL2,\{_:!+}*<
ri_2,\{_:!+}*<

Using the recurrence relation given in the challenge, using divmod and XOR to distinguish between the two recursive definitions:

ri{Ta{2md\j^}j}/

(Although, of course, this recurrence relation is just a different way to express the Thue-Morse sequence as the parity of the 1-bits in the binary representation of n.)

Answer 3

Dyalog APL, 8 7 bytes

≠⌿⍴∘2⊤⍳

This is a monadic train that expects an index origin of 0 (⎕IO←0). The equivalent non-train function is {≠⌿(⍵⍴2)⊤⍳⍵}.

Explanation:

      ⍳      List of numbers from 0 to (input-1)
  ⍴∘2        (input) copies of 2
     ⊤       Convert all the elements in ⍳ to base 2 to (input) digits
≠⌿           Reduce over the first axis by not-equal

Output is a space-separated list of 0 and 1. Try it here.

Answer 4

Mathematica, 35 21 bytes

Mathematica has a built-in for the Thue-Morse sequence!

Array[ThueMorse,#,0]&

---

Original answer:

#&@@@DigitCount[Range@#-1,2]~Mod~2&

Answer 5

LabVIEW, 15 LabVIEW Primitives

now as super fancy gif with a probe

Answer 6

J, 12 11 bytes

@MartinBüttner saved a byte.

~:/@#:"0@i.

This is a monadic (meaning unary) function, used as follows:

   f =: ~:/@#:"0@i.
   f 10
0 1 1 0 1 0 0 1 1 0

Explanation

I'm using the alternative definition that T_n is the parity of the number of 1-bits in the binary representation of n.

~:/@#:"0@i.  Input is n.
~:/          Output is XOR folded over
   @#:       the binary representations of
      "0     each element of
        @i.  integers from 0 to n-1.

Answer 7

Japt, 29 11 bytes

Uo ®¤¬r@X^Y

Try it online!

Outputs directly as an array, which saves about 4 bytes.

Ungolfed and explanation

Uo ®   ¤  ¬ r@  X^Y
Uo mZ{Zs2 q rXY{X^Y}}
        // Implicit: U = input number
Uo      // Create an array of integers in the range `[0, U)`. 
mZ{Zs2  // Map each item Z in this range to Z.toString(2),
q rXY{  //  split into chars, and reduced by
X^Y}}   //   XORing.
        //  This returns (number of 1s in the binary string) % 2.
        // Implicit: output last expression

Edit: You can now use the following 8-byte code (not valid; feature published after this challenge):

Uo ®¤¬r^

Answer 8

Pyth, 11 10 bytes

m%ssM.Bd2Q

Outputs as a Python-style list.

Answer 9

Haskell, 39 36 35 bytes

take<*>(iterate([id,(1-)]<*>)[0]!!)

Try it online!

How it works: start with [0] and apply the x ++ invert x-function n times. Take the first n elements from the resulting list. Thanks to Haskell's laziness only the first n elements are actually calculated. Note: the first <*> is in function context, the second in list context.

With GHC v8.4 (which wasn't available at the the time of the challenge) there's a 34 byte solution:

take<*>(iterate(id<>map(1-))[0]!!)

Edit: -3 resp. -4 bytes thanks to @Laikoni. -1 byte thanks to @Ørjan Johansen.

Answer 10

Pari/GP, 33 bytes

n->[sumdigits(x,2)%2|x<-[0..n-1]]

Try it online!

Answer 11

Haskell, 54 bytes

Less compact than nimi's solution, but I did not want to deny you this piece of functional code obfuscation. Works for any pair of objects; e.g. you can replace (f 0.f 1) by (f 'A'.f 'B').

Based on the definition that the first 2ⁿ digits are followed by the same sequence of digits inverted. What we do is build up two lists side-by-side; one for the sequence, one for the inverse. Continuously we append increasingly long parts of one list to the other.

The implementation consists of three definitions:

t=(f 0.f 1)t
f c=flip take.(c:).g 1
g n l=l n++g(n+n)l

Function t accepts any number and returns the Thue-Morse sequence of that length. The other two functions are helpers.

• Function f represents either list; f 0 is for the sequence, f 1 for the inverse.
• Function g takes care of appending increasingly long repetitions of one list to the other.

Fiddle: http://goo.gl/wjk9S0

Answer 12

Jelly, 4 bytes

ḶB§Ḃ

Note that this challenge is older than Jelly.

Try it online!

How it works

ḶB§Ḃ  Main link. Argument: n (integer)

Ḷ     Unlength; yield [0, ..., n-1].
 B    Compute the binary representation of each integer in the range.
  §   Take the sum of each binary representation.
   Ḃ  Take the LSB of each sum.

Answer 13

K5, 27 13 bytes

{x#((log x)%log 2){x,~x}/0}

Calculating the sequence is pretty easy, the problem is avoiding computing too much. We can recognize that the easy expansion of the sequence gives us a sequence of strings which are successive powers of two in length. Taking the log base 2 of the input and rounding up will give us enough to work with and then we can cut it down to the appropriate size:

  {x#((log x)%log 2){x,~x}/0}'(20 42 37 12 0)
(0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0
 0 1 1 0 1 0 0 1 1 0 0 1
 ())

Edit:

A parity-based solution:

~=/'(64#2)\'!

In action:

  ~=/'(64#2)\'!20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Note that since K5 doesn't have an arbitrary convert-to-binary primitive I have to specify, for example, a 64-bit decoding. K5 doesn't use arbitrary precision math, so there will be a limit to the size of inputs we can deal with in any case.

Answer 14

Burlesque, 21 bytes

{0}{J)n!_+}400E!jri.+

Examples:

blsq ) "20"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1}
blsq ) "42"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1}

Explanation:

{0}      -- setup
{J)n!_+} -- duplicate, map invert, concatenate
400E!    -- do 400 times (this will eventually run
            out of memory).
jri.+    -- take n elements

Without the jri.+ part you will run out of memory (because it will compute the morse sequence of length incredibly huge number). But since Burlesque is lazy just asking for the first n-element will work anyway.

Answer 15

Octave, 33 31 bytes

Saved 2 bytes thanks to Thomas Kwa.

@(n)mod(sum(dec2bin(0:n-1)'),2)

Answer 16

Perl 5, 62 49 bytes

Yeah, not the best language for this one, but I still like the way it came out. Requires 5.14+ for /r and say.

sub{$_=0;$_.=y/01/10/r while$_[0]>length;say substr$_,0,$_[0]}

Using the parity definition, requires 5.12+ for say:

sub{say map{sprintf("%b",$_)=~y/1//%2}0..$_[0]-1}

Answer 17

C, 88 83 bytes

Calculates the parity for each individual position.

i,j;main(int c,char**a){for(;i<atoi(a[1]);putchar(c))for(c=48,j=i++;j;j&=j-1)c^=1;}

Fiddle: http://goo.gl/znxmOk

Answer 18

Retina, 70 69 bytes

Using the definition as an L-system with initial word 0 and productions 0 --> 01 and 1 --> 10.

^
0;
(T`d`ab`^(.)+;(?!(?<-1>.)+$)
a
01
)`b
10
!`^(?=.*;(.)+)(?<-1>.)+

Input is taken in unary.

You can run the code from a single file with the -s flag. Or just try it online.

Explanation

^
0;

Prepends 0; to the input, where 0 is the initial word and ; is just a separator.

(T`d`ab`^(.)+;(?!(?<-1>.)+$)

The ( indicates that this is the beginning of a loop (which repeats until the loop stops changing the string). This stage itself turns 0 and 1 into a and b respectively (because d expands to 0-9). It does this as long as current word (whose length is measured with (.)+ is shorter than the input (i.e. as long as we can't read the end of the string by matching as many 1s as we have in the word).

a
01

Replace a (stand-in for 0) with 01.

)`b
10

Replace b (stand-in for 1) with 10. This is also the end of the loop. The loop terminates once the condition in the transliteration stage fails, because then all 0s and 1s will remain unchanged and the other two stages won't find anything to match.

!`^(?=.*;(.)+)(?<-1>.)+

The last step is to truncate the word to the length of the input. This time we measure the length of the input with (.)+ in a lookahead. Then we match that many characters from the beginning of the string.

Answer 19

Prolog (SWI), 115 bytes

Code:

N*X:-N>1,R is N//2,R*Y,X is(N mod 2)xor Y;X=N.
p(N):-M is N-1,findall(E,between(0,M,E),L),maplist(*,L,K),write(K).

Explained:

N*X:-                                 % Calculate Thue-Morse number at index N
     N>1,                             % Input is bigger than 1
     R is N//2,R*Y,X is(N mod 2)xor Y % Thue-Morse digit at index N is binary digits of N xor'ed
     ;X=N.                            % OR set X to N (end of recursion)
p(N):-
      M is N-1,                       % Get index of Nth number
      findall(E,between(0,M,E),L),    % Make a list of number 0->N-1
      maplist(*,L,K),                 % Map * on list L producing K
      write(K).                       % Print K

Example:

p(20).
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

Try it online here

Answer 20

Ruby, 33

->n{n.times{|i|p ("%b"%i).sum%2}}

Call like this:

f=->n{n.times{|i|p ("%b"%i).sum%2}}
f[16]

Uses the fact that the parity of binary numbers forms the thue-morse sequence.

Separator character is newline. Converts number i to a binary string, then calculates the sum of all ASCII codes, modulo 2.

If newline is not an acceptable separator, the following has no separator for an additional 2 bytes:

->n{n.times{|i|$><<("%b"%i).sum%2}}

Answer 21

MATL, 9 bytes

This language was designed after the challenge.

Approach 1: 13 bytes

This builds the sequence by concatenating negated copies of increasing-size blocks.

itBFw"t~h]w:)

Example

>> matl itBFw"t~h]w:)
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Explanation

i           % input number, say "N"
tB          % duplicate and convert to binary. Produces a vector
F           % initialize sequence to "false"
w           % swap to bring vector to top
"           % for loop. There will be at least log2(N) iterations
  t~h       % duplicate, negate, concatenate
]           % end for
w           % swap
:)          % index with vector 1, 2, ..., N

Approach 2: 9 bytes

This uses the same approach as Alephalpha's answer.

i:1-B!s2\

Example

>> matl i:1-B!s2\
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

Explanation

i           % input "N" 
:1-         % create vector 0, 1, ..., N-1
B           % convert to binary
!           % tranpose
s           % sum
2\          % modulo 2

Answer 22

Common Lisp, 50 bytes

(lambda(n)(dotimes(i n)(princ(mod(logcount i)2))))

Try it online!

Answer 23

Matlab, 42

I am using the fact that it is the same as beginning with 0 and then repeating the step of appending the complement of the current series, n times.

t=0;for k=1:input('');t=[t;~t];end;disp(t)

Answer 24

Arcyóu, 50 55 bytes

I had to add 5 bytes to get it to work correctly :(

(f i(_(#(l)))(r b^(@(> i 0)(pg 0(% i 2)(: i(#/ i 2))))0

Explanation (with Pythonesque pseudocode along the side:

(f i (_ (# (l)))       ; For i in range(int(input())):
  (r b^                ; Reduce with binary xor
    (@ (> i 0)         ; While i > 0:
      (pg 0            ; Return first of its arguments
        (% i 2)        ; i mod 2
        (: i (#/ i 2)) ; i //= 2
      )
    )
    0                  ; Default reduce argument of 0 for the first bit in the sequence

Answer 25

Bash, 71 66 bytes

Based on the definition that the first 2ⁿ digits are followed by the same sequence of digits inverted.

x=0;y=1;while((${#x}<$1));do z=$x;x=$x$y;y=$y$z;done;echo ${x::$1}

$1 as a parameter is the desired number of digits.

Fiddle: http://goo.gl/RkDZIC

Answer 26

, 11 chars / 23 bytes (non-competitive)

Ⓐïⓜ_ⓑⓢĊ⇀$^_

Try it here (Firefox only).

The circles are strong with this one.

Answer 27

Batch, 115 + 2 = 117 bytes

Based on the Bash answer.

@echo off
set x=0
set y=1
set z=0
:a
set x=!x!!y!
set y=!y!!z!
set z=!x:~0,%1!
if !z!==!x! goto a
echo !z!

Needs an extra /V in the invocation to allow the use of !s.

Answer 28

ES6, 53 bytes

f=(i,x="0",y=1)=>x.length<i?f(i,x+y,y+x):x.slice(0,i)

Recursion seemed simpler than a loop.

Answer 29

Par, 8 bytes

✶u[Σ_✶¨^

Explanation:

✶          parse implicit input number
 u         range [0..n-1]
  [        map:
   Σ           convert to binary
    _✶         get digit list
      ¨^       fold with xor

Outputs something like:

(0 1 1 0 1 0 0 1)

Answer 30

Math++, 86 bytes

Uses 0.0\n for 0 and 1.0\n for 1

?>n
3*!!(n-m)>$
m>a
0>k
6+6*!a>$
9-2*!(a%2)>$
a/2>a
5>$
(a-1)/2>a
!k>k
5>$
k
m+1>m
2>$

Answer 31

K (ngn/k), 16 bytes

{2!+/'(x#2)\'!x}

Try it online!

Answer 32

Stax, 5 bytes

╩0ΔΔ(

Run and debug it at staxlang.xyz!

Unpacked (6 bytes) and explanation:

mv:11I
mv        Map block over range [0,n):
  :1        Popcount
    1I      Is odd?
            Implicit print with newline

1I is bitwise and with 1. 2% would work just as well, also packing to 5 bytes.

Answer 33

Python 3, 84 80 60 bytes

Since nobody else was using characters other than 0 and 1, I decided to write my own answer. Here, I use the characters o and t, but I was quite tempted to use b and o, or p and o :P

This is a parity checker in 60 bytes.

lambda n:''.join("ot"[bin(i).count("1")%2]for i in range(n))

This is a string rewriting algorithm in 109 bytes.

def t(n):
 r="o";s=""
 for i in range(len(bin(n))):
  for c in r:s+="otto"[c>"o"::2]
  r=s;s=""
 return r[:n]