Morse Thue Number

Interface

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

n	the desired order

Returns

the Morse-Thue number of order n

Authors

Lucian Bentea (August 2005)

Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.