Thue-Morse sequence
Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is an infinite binary sequence of 0s and 1s. The sequence is obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained so far.
First few steps :
Start with 0
Append complement of 0, we get 01
Append complement of 01, we get 0110
Append complement of 0110, we get 01101001
Given a whole number n. The task is to find the nth string formed of by Thue–Morse sequence i.e prefix of length 2n-1 of Thue–Morse sequence.
Examples:
Input : n = 4 Output : 01101001 We get 0, 01, 0110 and 01101001 in fourth iteration. Input : n = 3 Output : 0110
The idea is to initialize the output string with 0, then run a loop n – 1 times and for each iteration find the complement of the string and append it to the string.
Below is implementation of this approach:
C++
// CPP Program to find nth term of Thue-Morse sequence.#include <bits/stdc++.h>using namespace std;// Return the complement of the binary string.string complement(string s){ string comps; // finding the complement of the string. for (int i = 0; i < s.length(); i++) { // if character is 0, append 1 if (s.at(i) == '0') comps += '1'; // if character is 1, append 0. else comps += '0'; } return comps;}// Return the nth term of Thue-Morse sequence.string nthTerm(int n){ // Initializing the string to 0 string s = "0"; // Running the loop for n - 1 time. for (int i = 1; i < n; i++) // appending the complement of // the string to the string. s += complement(s); return s;}// Driven Programint main(){ int n = 4; cout << nthTerm(n) << endl; return 0;} |
Java
// Java Program to find nth // term of Thue-Morse sequence.class GFG{ // Return the complement // of the binary String. static String complement(String s) { String comps = ""; // finding the complement // of the String. for (int i = 0; i < s.length(); i++) { // if character is 0, // append 1 if (s.charAt(i) == '0') comps += '1'; // if character is 1, // append 0. else comps += '0'; } return comps; } // Return the nth term // of Thue-Morse sequence. static String nthTerm(int n) { // Initializing the // String to 0 String s = "0"; // Running the loop // for n - 1 time. for (int i = 1; i < n; i++) // appending the complement of // the String to the String. s += complement(s); return s; } // Driven Codepublic static void main(String[] args) { int n = 4; System.out.print(nthTerm(n)); }}// This code is contributed by // mits |
Python3
# Python3 Program to find nth term of# Thue-Morse sequence.# Return the complement of the# binary string.def complement(s): comps = ""; # finding the complement # of the string. for i in range(len(s)): # if character is 0, append 1 if (s[i] == '0'): comps += '1'; # if character is 1, append 0. else: comps += '0'; return comps;# Return the nth term of # Thue-Morse sequence.def nthTerm(n): # Initializing the string to 0 s = "0"; # Running the loop for n - 1 time. for i in range(1, n): # appending the complement of # the string to the string. s += complement(s); return s;# Driver Coden = 4;print(nthTerm(n));# This code is contributed # by mits |
C#
// C# Program to find nth // term of Thue-Morse sequence.using System;class GFG{ // Return the complement // of the binary string. static string complement(string s) { string comps = ""; // finding the complement // of the string. for (int i = 0; i < s.Length; i++) { // if character is 0, // append 1 if (s[i] == '0') comps += '1'; // if character is 1, // append 0. else comps += '0'; } return comps; } // Return the nth term // of Thue-Morse sequence. static string nthTerm(int n) { // Initializing the // string to 0 string s = "0"; // Running the loop // for n - 1 time. for (int i = 1; i < n; i++) // appending the complement of // the string to the string. s += complement(s); return s; } // Driven Code static void Main() { int n = 4; Console.Write(nthTerm(n)); }}// This code is contributed by // Manish Shaw(manishshaw1) |
PHP
<?php// PHP Program to find nth // term of Thue-Morse sequence.// Return the complement // of the binary string.function complement($s){ $comps = ""; // finding the complement // of the string. for ($i = 0; $i < strlen($s); $i++) { // if character is // 0, append 1 if ($s[$i] == '0') $comps .= '1'; // if character is // 1, append 0. else $comps .= '0'; } return $comps;}// Return the nth term // of Thue-Morse sequence.function nthTerm($n){ // Initializing the // string to 0 $s = "0"; // Running the loop // for n - 1 time. for ($i = 1; $i < $n; $i++) // appending the complement of // the string to the string. $s .= complement($s); return $s;}// Driven Code$n = 4;echo nthTerm($n);// This code is contributed // by mits?> |
Javascript
<script>// JavaScript Program to find nth // term of Thue-Morse sequence. // Return the complement // of the binary string. function complement(s) { let comps = ""; // finding the complement // of the string. for (let i = 0; i < s.length; i++) { // if character is 0, // append 1 if (s[i] == '0') comps += '1'; // if character is 1, // append 0. else comps += '0'; } return comps; } // Return the nth term // of Thue-Morse sequence. function nthTerm(n) { // Initializing the // string to 0 let s = "0"; // Running the loop // for n - 1 time. for (let i = 1; i < n; i++) // appending the complement of // the string to the string. s += complement(s); return s; }// Driver program let n = 4; document.write(nthTerm(n)); // This code is contributed by susmitakundugoaldanga.</script> |
Output
01101001
Time Complexity: O(n*log(n))
Auxiliary Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
