Japt -mP, 4 bytes

¢¬r^

Try it here

¢¬r^     :Implicit map of range [0,input)
ç        :Convert to binary string
 ¬       :Split
  r      :Reduce by
   ^     :  Bitwise XOR
         :Implicitly join & output

Uiua, 7 bytes

◿2/+⍉⋯⇡

Returns an array; port of Dennis's Jelly answer. Try it online!

Explanation

◿2/+⍉⋯⇡ # main function
      ⇡ # generate array of all natural numbers less than the input
     ⋯  # encode each number in the array as bits, LSB-first
    ⍉   # rotate the shape of the array
  /+    # sum each column of bits
◿2      # modulo each sum by 2

Vyxal, 4 bytes

ʁbṠ∷

Try it Online! Port of Dennis's Jelly answer.

ʁ    # 0...n-1
   ∷ # parity of
  Ṡ  # number of
 b   # 1s in binary representation

Python, 43 bytes

def f(n):n>0==f(n-1);print(n.bit_count()%2)

Attempt This Online!

V (vim), ³⁵ 29 bytes

C0<esc>qqy$V!tr 01 10
P|q@-@q@-lD

Try it online!

-6 bytes from Leo.

Prints the first \$n\$ elements.

The sequence is basically a string replacement and append, so it does that \$n\$ times using tr and then truncates the sequence to \$n\$ digits.

Husk, 6 bytes

moF≠ḋŀ

Try it online!

Using infinite list:

↑¹!¡S+m¬;0

Try it online!

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.

Pari/GP, 33 bytes

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

Try it online!

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.

Common Lisp, 50 bytes

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

Try it online!

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.

K (ngn/k), 16 bytes

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

Try it online!

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]

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

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

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

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

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)

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

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

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

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.

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.

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

𝔼𝕊𝕄𝕚𝕟, 11 chars / 23 bytes (non-competitive)

Ⓐïⓜ_ⓑⓢĊ⇀$^_

Try it here (Firefox only).

The circles are strong with this one.

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.

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

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}

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&

Octave, 33 31 bytes

Saved 2 bytes thanks to Thomas Kwa.

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

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.

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^

LabVIEW, 15 LabVIEW Primitives

now as super fancy gif with a probe

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.

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)

Pyth, 11 10 bytes

m%ssM.Bd2Q

Outputs as a Python-style list.

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.

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

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.