Morse_Thue_Number

The Morse-Thue sequence can be defined in a number of ways.

1) Start with the string containing the single letter '0'; then repeatedly apply the replacement rules '0' -> '01' and '1' -> '10' to the letters of the string. The Morse-Thue sequence is the resulting letter sequence.

2) Starting with the string containing the single letter '0', repeatedly append the binary complement of the string to itself. Thus, '0' becomes '0' + '1' or '01', then '01' becomes '01' + '10', which becomes '0110' + '1001', and so on.

3) Starting with n equal to zero, the n-th Morse-Thue number is determined by taking the binary representation of n, adding the digits, and computing the remainder modulo 2. This is also the formula used with this algorithm.

Example:

#include <codecogs/maths/combinatorics/sequences/morse_thue_number.h>
#include <iostream>
int main()
{
  std::cout << "The first 10 terms of the Morse-Thue sequence" << std::endl;
  for (int i = 0; i < 10; i++)
    std::cout << Maths::Combinatorics::Sequences::morse_thue_number(i) << "  ";
  std::cout << std::endl;
  return 0;
}

Output:

The first 10 terms of the Morse-Thue sequence
0  1  1  0  1  0  0  1  1  0

References

SUBSET, a C++ library of combinatorial routines, http://www.csit.fsu.edu/~burkardt/cpp_src/subset/subset.html

Parameters

Returns