[Shebang]

What is code golf?

Code golfing is an activity where a bunch of people compete to complete a specific programming task, using as few bytes of code as possible to complete the task.

Now, onto the challenge!

---

Thue-Morse Sequence

In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. The first few steps of this procedure yield the strings 0 then 01, 0110, 01101001, 0110100110010110, and so on, which are prefixes of the Thue–Morse sequence. The full sequence begins:

Code:

01101001100101101001011001101001100101100110100101101001100101101001011001101001

This is sequence A010060 in OEIS.

The Challenge

You should create a program or function which takes input via some method (standard input, function parameters, etc) which will produce the first n characters in the Thue-Morse sequence. You are not allowed to hardcode the sequence into your program, as it should theoretically work for any value of n. You cannot use any external sources to obtain the digits, all of them must be calculated one the program is run. You should not plagiarize existing programs. Breaking any of these rules disqualifies your program.

Once you have written your program, it would be extremely helpful if you could post a link to http://repl.it or http://ideone.com , which are online code compilers for a bunch of languages. This is so I can test and make sure that it functions as it should.

Also, you must start out your post saying which language and version you are using, and the byte count, which can be obtained from here. If you are missing this, I will not count your score until you add it!

The challenge will run for 1 week, while I can still edit the main post. After that, the shortest answer that has not been disqualified will be crowned the winner, and the user will receive 84 NSP.

Example Input/Output

Output can be in the format of a list/array, string or binary sequence.

Code:

n = 6 --> [0,1,1,0,1,0] n = 20 --> '01101001100101101001' n = 1 --> 0 n = 0 --> n = 99 --> 011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010110011

Leaderboard

Code:

User | Language | Bytes ----------------------------------------------- Stocking | Python 2 | 79 Stocking | Node.js | 100 eclipse | Python 2 | 119

Donate

If you'd like to increase the size of the prize pool, donate and I'll increase the size!

Thanks to @Eclipse for donating 25 NSP, and @Panty for donating 39 NSP!

[OversouL]

This is an interesting challenge. I would've liked to try this out with C++, but I'm still just trying to learn it. I hope a lot will do this challenge.

[Eclipse]

I'll donate 25 NSP to the pot.

[Eclipse]

http://repl.it/BBso
119 bytes

Example outputs:

Code:

T0 --> 0 T1 --> 01 T2 --> 0110 T3 --> 01101001 T4 --> 0110100110010110 T5 --> 01101001100101101001011001101001 T6 --> 0110100110010110100101100110100110010110011010010110100110010110 T7 --> 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

EDIT: I may try golfing this further.

[Shebang]

This is an interesting challenge. I would've liked to try this out with C++, but I'm still just trying to learn it. I hope a lot will do this challenge.

I'd love to see your answer!

I'll donate 25 NSP to the pot.

Thanks!

I'll donate 15 NSP to the pot.

Thanks!

http://repl.it/BBs9
138 bytes

Example outputs:

Code:

T0 --> 0 T1 --> 01 T2 --> 0110 T3 --> 01101001 T4 --> 0110100110010110 T5 --> 01101001100101101001011001101001 T6 --> 0110100110010110100101100110100110010110011010010110100110010110 T7 --> 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

Nice work! Just so you know, while you are printing out each iteration, the question is asking for the sequence up to the nth digit. So you should be producing 011010 for n=6. This shouldn't be a difficult change, you can fix it with just a few bytes . Once you do I can help shorten it more

[Eclipse]

Nice work! Just so you know, while you are printing out each iteration, the question is asking for the sequence up to the nth digit. So you should be producing 011010 for n=6. This shouldn't be a difficult change, you can fix it with just a few bytes . Once you do I can help shorten it more

Ahh. I've golfed that down to 118 bytes btw. I'll make the edits.

[Shebang]

Ahh. I've golfed that down to 118 bytes btw. I'll make the edits.

It has good potential! I've golfed yours down to 86 bytes so far Quick tip, you don't need to put anything in the input prompt, plus input() works here instead of int(raw_input()).

[Eclipse]

Nice work! Just so you know, while you are printing out each iteration, the question is asking for the sequence up to the nth digit. So you should be producing 011010 for n=6. This shouldn't be a difficult change, you can fix it with just a few bytes . Once you do I can help shorten it more

Ahh. I've golfed that down to 118 bytes btw. I'll make the edits.

Edited my entry.

---

It has good potential! I've golfed yours down to 86 bytes so far Quick tip, you don't need to put anything in the input prompt, plus input() works here instead of int(raw_input()).

Ahh, sorry. It's instinctive. I guess security isn't much of an issue.

EDIT: 86?! How?

[Shebang]

Edited my entry.

---

Ahh, sorry. It's instinctive. I guess security isn't much of an issue.

No worries

I'll give you a few more hints

• If you make that for into a while, you can make that loop a one-liner (think list comprehension). The while will not make it shorter, just ensure it actually finishes timely.
  
• String slicing doesn't need a 0 placeholder.
  

---

Edited my entry.

---

Ahh, sorry. It's instinctive. I guess security isn't much of an issue.

EDIT: 86?! How?

It's actually down to 75 now To be fair, I have practice golfing, you don't A few of the tricks I'm using aren't stuff that would be common knowledge/practice to a lot of people.

[Eclipse]

It's actually down to 75 now To be fair, I have practice golfing, you don't A few of the tricks I'm using aren't stuff that would be common knowledge/practice to a lot of people.

Fucking hell.. I didn't know golfing was a thing.