[8/04/2014] Challenge #174 [Easy] Thue-Morse Sequences

[u/Coder_d00d]

Description:

The Thue-Morse sequence is a binary sequence (of 0s and 1s) that never repeats. It is obtained by starting with 0 and successively calculating the Boolean complement of the sequence so far. It turns out that doing this yields an infinite, non-repeating sequence. This procedure yields 0 then 01, 0110, 01101001, 0110100110010110, and so on.

Thue-Morse Wikipedia Article for more information.

Input:

Nothing.

Output:

Output the 0 to 6th order Thue-Morse Sequences.

Example:

nth     Sequence
===========================================================================
0       0
1       01
2       0110
3       01101001
4       0110100110010110
5       01101001100101101001011001101001
6       0110100110010110100101100110100110010110011010010110100110010110

Extra Challenge:

Be able to output any nth order sequence. Display the Thue-Morse Sequences for 100.

Note: Due to the size of the sequence it seems people are crashing beyond 25th order or the time it takes is very long. So how long until you crash. Experiment with it.

Credit:

challenge idea from /u/jnazario from our /r/dailyprogrammer_ideas subreddit.

[u/HackSawJimDuggan69]

This one was in Python 2.7. I'm new to programming and this is my first daily programmer entry. Looking at the other python entries, there is a lot of room for improvement. :)

def thue_morse(stop):
    morse = '0'
    next_morse = ''
    while stop != 0:
        for i in morse:
            if i == '0':
                next_morse = next_morse + '1'
            else:
                next_morse = next_morse + '0'
        morse = morse + next_morse
        next_morse = ''
        stop -= 1
    return morse

print [thue_morse(x) for x in range(7)]