How to Generate the Thue Morse Sequence
Three Methods:Using the Direct DefinitionUsing the Recurrence RelationUsing Bitwise Negation
The Thue-Morse sequence, or Prouhet-Thue-Morse sequence, is a binary sequence whose initial segments alternate. It is used in generating Koch snowflakes, a fractal curve of infinite length containing a finite area. It has other applications in mathematics and computer science^{[1]}. This article will guide you through the different methods by which you can generate this sequence.
Steps
Method 1 Using the Direct Definition
- 1Start with 0 as the first element of the sequence (element t_{})
- 2Calculate each subsequent element one at a time, starting from t_{1}. To calculate the n^{th} element:
- Convert n to the binary format. For example, 5 becomes 101
- Count the number of 1s in the binary format of n. For example, 5 has 2 "1"s in its binary representation
- Determine the digit at position n by setting it to 1 if the number of "1"s is odd and 0 if the number of "1"s is even.
- 3Repeat step 2 to determine as many digits of the sequence as you like.
Method 2 Using the Recurrence Relation
- 1Start with t_{} = 0
- 2Continue calculating next elements from n=1 increasing n by 1 each time. Use the following equations alternatively to calculate the values:
- t_{2n+1} = 1 - t_{2n} (Eq. 1)
- t_{2n} = t_{n} (Eq. 2)
- For example:
- n = 0, substituting in Eq. 1: t_{1} = 1 - t_{0} = 1 (t_{0} is 0)
- n = 1, substituting in Eq. 2: t_{2} = t_{1} = 1
- n = 1, substituting in Eq. 1: t_{3} = 1 - t_{2} = 1 - 1 = 0
- n = 2, substituting in Eq. 2: t_{4} = t_{2} = 1
- n = 2, substituting in Eq. 1: t_{5} = 1 - t_{4} = 1 - 1 = 0
- n = 3, substituting in Eq. 2: t_{6} = t_{3} = 0
- n = 3, substituting in Eq. 1: t_{7} = 1 - t_{6} = 1 - 0 = 1
Method 3 Using Bitwise Negation
- 1Start with 0
- 2The bitwise negation of 0 is 1 so the second element is 1, forming the string "01"
- 3The bitwise negation of "01" is "10", so the third element is 1 and the fourth is 0, forming the string "0110" so far.
- 4The first 4 elements are "0110". The bitwise negation of 0110 is 1001. Combining these, the first 8 elements are "01101001"
- 5Repeat this procedure for the next 8 elements, then 16 then 32 ... etc.
- 6In short and mathematical form, once the first 2^{n} elements have been specified, forming a string s, then the next 2^{n} elements must form the bitwise negation of s, which defines the first 2^{n+1} elements and so forth.
- For Example:
- T_{0} =0.
- T_{1} = 01.
- T_{2} = 0110.
- T_{3} = 01101001.
- T_{4} = 0110100110010110.
- T_{5} = 01101001100101101001011001101001.
- T_{6} = 0110100110010110100101100110100110010110011010010110100110010110.
- And so on.
- For Example:
Sources and Citations
Article Info
Featured Article
Categories: Featured Articles | Mathematics | Algebra