Write out the Thue-Morse sequence

Question 1

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>

Question 2

Related.

Question 3

in simpler words you could say: the function is recursive, negate the input and append it.

Question 4

Borderline dupe

Question 5

@PeterTaylor In what way? One possible answer to the linked question is the Thue-Morse sequence, but this question is to generate the Thue-Morse and nothing else.

Question 6

Because some of the answers to the previous question can be used to answer this question with trivial changes, and all answers to this question can be used to answer the previous question with trivial changes.

Question 7

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

Question 8

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

Question 9

The memory-wasteful solution was my first thought as well, but I figured using over half a terabyte of memory to compute the output for 42 (assuming a bitset) would be pretty unreasonable.

Question 10

@JohnE Problem solved. ;)

Question 11

:^ makes me happy. On another note, holy crap, that's a cool algorithm.

Question 12

@QPaysTaxes not :^}?

Question 13

@TheLethalCoder That makes me happy too

Question 14

LabVIEW, 15 LabVIEW Primitives

now as super fancy gif with a probe

enter image description here

Question 15

Could you explain how this would be tested?

Question 16

option 1: get labview test version and rebuild it, Option: suggest a way how i can send this to you as .exe or .vi (for the latter you have to get labview as well)

Question 17

Really I would just like to see how this behaves when it runs. Would recording a GIF be illustrative?

Question 18

that a great idea i just did that and will up it in a sec

Question 19

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.

Question 20

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&

Question 21

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.

Question 22

{.(,-)^:] works for 9 bytes with some rule stretching (which has been allowed). E.g. for 5 it outputs 5 _5 _5 5 _5. (Added only as a comment because of the rule stretching.)

Question 23

Pyth, (削除) 11 (削除ここまで) 10 bytes

m%ssM.Bd2Q

Outputs as a Python-style list.

Question 24

I tried using XOR over the binary string, but I don't know nearly enough about Pyth to do that. This is much shorter anyway. +1

Question 25

@FryAmTheEggman Ah, I didn't know about F because I searched for 'reduce'. You could post as CW...

Question 26

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^

Question 27

you might want to update your explanation

Question 28

@Eumel I already did...?

Question 29

the code you explain and the code above look different

Question 30

@Eumel There, is that better?

Question 31

thats perfect :)

Question 32

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.

Question 33

(\x->x++map(1-)x) can be shortened to ([id,(1-)]<*>) or (id<>map(1-)) with GHC 8.4.

Question 34

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

Question 35

Pari/GP, 33 bytes

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

Try it online!

Question 36

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.

Question 37

Octave, (削除) 33 (削除ここまで) 31 bytes

Saved 2 bytes thanks to Thomas Kwa.

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

Question 38

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://www.tutorialspoint.com/viewproject.php?URL=compile_haskell_online.php&PID=0Bw_CjBb95KQMMXFrVjBnZ01Yc3M

Question 39

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

Question 40

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

Question 41

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.

Question 42

Nice. Similar to my Haskell solution. However, I repeat only 99 times to save one byte.

Question 43

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}

Question 44

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

Question 45

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.

Question 46

ESMin, 11 chars / 23 bytes (non-competitive)

Aïm_bsĊ⇀$^_

Try it here (Firefox only).

The circles are strong with this one.

Question 47

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://www.tutorialspoint.com/viewproject.php?URL=compile_c_online.php&PID=0Bw_CjBb95KQMRXRuVUFwaWYxWmc

Question 48

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.

Question 49

Common Lisp, 50 bytes

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

Try it online!

Question 50

V (vim), ^{(削除) 35 (削除ここまで)} 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.

Question 51

Nice one, here's how to get it shorter :) Try it online! Main trick is the use of @- (from this tip), then C is equivalent to Di, the : in V:! is superfluous, and I've played around with the copy-paste-move to avoid the need for gJ

Question 52

@Leo nice golfs.

Question 53

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)

Question 54

You can replace the disp(t) by t I think...

Question 55

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://www.tutorialspoint.com/viewproject.php?URL=execute_bash_online.php&PID=0Bw_CjBb95KQMTEp2UTJZdlhPZkk

Question 56

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.

Question 57

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.

Question 58

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)

Question 59

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

score 14 · Accepted Answer · 2015-12-02 18:54:28Z

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

Write out the Thue-Morse sequence

Catalogue

39 Answers 39

Pyth, 6 bytes

Explanation:

CJam, (削除) 17 (削除ここまで) 9 bytes

Explanation

Bonus Solutions

LabVIEW, 15 LabVIEW Primitives

Dyalog APL, (削除) 8 (削除ここまで) 7 bytes

Mathematica, (削除) 35 (削除ここまで) 21 bytes

J, (削除) 12 (削除ここまで) 11 bytes

Explanation

Pyth, (削除) 11 (削除ここまで) 10 bytes

Japt, (削除) 29 (削除ここまで) 11 bytes

Ungolfed and explanation

Haskell, (削除) 39 (削除ここまで) (削除) 36 (削除ここまで) 35 bytes

Pari/GP, 33 bytes

K5, (削除) 27 (削除ここまで) 13 bytes

Edit:

Octave, (削除) 33 (削除ここまで) 31 bytes

Haskell, 54 bytes

Ruby, 33

MATL, 9 bytes

Approach 1: 13 bytes

Example

Explanation

Approach 2: 9 bytes

Example

Explanation

Burlesque, 21 bytes

Perl 5, (削除) 62 (削除ここまで) 49 bytes

Prolog (SWI), 115 bytes

Retina, (削除) 70 (削除ここまで) 69 bytes

Explanation

ESMin, 11 chars / 23 bytes (non-competitive)

C, (削除) 88 (削除ここまで) 83 bytes

Jelly, 4 bytes

How it works

Common Lisp, 50 bytes

V (vim), (削除) 35 (削除ここまで) 29 bytes

Matlab, 42

Bash, (削除) 71 (削除ここまで) 66 bytes

Batch, 115 + 2 = 117 bytes

ES6, 53 bytes

Par, 8 bytes

Math++, 86 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Linked

Related

Hot Network Questions

V (vim), ^{(削除) 35 (削除ここまで)} 29 bytes