22
\$\begingroup\$

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>

\$\endgroup\$
  • 1
    \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Dec 2 '15 at 16:23
  • 1
    \$\begingroup\$ in simpler words you could say: the function is recursive, negate the input and append it. \$\endgroup\$ – Eumel Dec 2 '15 at 16:43
  • 2
    \$\begingroup\$ Borderline dupe \$\endgroup\$ – Peter Taylor Dec 2 '15 at 16:59
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Sherlock9 Dec 2 '15 at 17:03
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Dec 2 '15 at 19:22

33 Answers 33

14
\$\begingroup\$

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
\$\endgroup\$
9
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – JohnE Dec 2 '15 at 16:34
  • \$\begingroup\$ @JohnE Problem solved. ;) \$\endgroup\$ – Martin Ender Dec 2 '15 at 16:40
  • \$\begingroup\$ :^ makes me happy. On another note, holy crap, that's a cool algorithm. \$\endgroup\$ – Nic Hartley Dec 2 '15 at 19:47
  • \$\begingroup\$ @QPaysTaxes not :^}? \$\endgroup\$ – TheLethalCoder Dec 4 '15 at 15:52
  • 1
    \$\begingroup\$ @TheLethalCoder That makes me happy too \$\endgroup\$ – Nic Hartley Dec 4 '15 at 16:18
8
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

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&
\$\endgroup\$
7
\$\begingroup\$

LabVIEW, 15 LabVIEW Primitives

now as super fancy gif with a probe

enter image description here

\$\endgroup\$
  • 3
    \$\begingroup\$ Could you explain how this would be tested? \$\endgroup\$ – JohnE Dec 2 '15 at 16:30
  • \$\begingroup\$ 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) \$\endgroup\$ – Eumel Dec 2 '15 at 16:34
  • 1
    \$\begingroup\$ Really I would just like to see how this behaves when it runs. Would recording a GIF be illustrative? \$\endgroup\$ – JohnE Dec 2 '15 at 17:41
  • \$\begingroup\$ that a great idea i just did that and will up it in a sec \$\endgroup\$ – Eumel Dec 2 '15 at 18:07
6
\$\begingroup\$

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 Tn 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.
\$\endgroup\$
  • \$\begingroup\$ {.(,-)^:] 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.) \$\endgroup\$ – randomra Dec 20 '15 at 11:14
4
\$\begingroup\$

Pyth, 11 10 bytes

m%ssM.Bd2Q

Outputs as a Python-style list.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – ETHproductions Dec 2 '15 at 17:17
  • \$\begingroup\$ @FryAmTheEggman Ah, I didn't know about F because I searched for 'reduce'. You could post as CW... \$\endgroup\$ – lirtosiast Dec 2 '15 at 17:34
4
\$\begingroup\$

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^
\$\endgroup\$
  • \$\begingroup\$ you might want to update your explanation \$\endgroup\$ – Eumel Dec 2 '15 at 17:56
  • \$\begingroup\$ @Eumel I already did...? \$\endgroup\$ – ETHproductions Dec 2 '15 at 18:21
  • \$\begingroup\$ the code you explain and the code above look different \$\endgroup\$ – Eumel Dec 2 '15 at 18:33
  • \$\begingroup\$ @Eumel There, is that better? \$\endgroup\$ – ETHproductions Dec 2 '15 at 18:36
  • \$\begingroup\$ thats perfect :) \$\endgroup\$ – Eumel Dec 2 '15 at 19:14
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ (\x->x++map(1-)x) can be shortened to ([id,(1-)]<*>) or (id<>map(1-)) with GHC 8.4. \$\endgroup\$ – Laikoni May 12 '18 at 7:28
  • \$\begingroup\$ take<*>(iterate([id,(1-)]<*>)[0]!!) \$\endgroup\$ – Ørjan Johansen May 13 '18 at 1:04
3
\$\begingroup\$

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 2n 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

\$\endgroup\$
3
\$\begingroup\$

Pari/GP, 33 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice. Similar to my Haskell solution. However, I repeat only 99 times to save one byte. \$\endgroup\$ – nimi Dec 2 '15 at 17:17
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Octave, 33 31 bytes

Saved 2 bytes thanks to Thomas Kwa.

@(n)mod(sum(dec2bin(0:n-1)'),2)
\$\endgroup\$
2
\$\begingroup\$

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}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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}}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ You can replace the disp(t) by t I think... \$\endgroup\$ – AlexR Dec 3 '15 at 0:07
1
\$\begingroup\$

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

Ⓐïⓜ_ⓑⓢĊ⇀$^_

Try it here (Firefox only).

The circles are strong with this one.

\$\endgroup\$
1
\$\begingroup\$

Bash, 71 66 bytes

Based on the definition that the first 2n 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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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>$
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Common Lisp, 50 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.