Write out the Thue-Morse sequence
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
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 1
s 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
.)
LabVIEW, 15 LabVIEW Primitives
now as super fancy gif with a probe