Gijswijt’s sequence is a self-describing sequence where the value of each term is equal to the maximum number of repeated blocks of numbers in the sequence preceding the number.
Let us take the ith term of the sequence a(i), Then for this Gijswijt’s Sequence:
where k is the largest natural number such that the word a(1)a(2)..a(n) can be represented as x*(y^k) where the length of y is non zero.
The Gijswijt’s sequence is as follows:
1, 1, 2, 1, 1, 2, 2, 2, 3, 1, ...
It can be proved that every natural number occurs in this sequence at least once but the sequence has very slow growth. The 220th term is 4 whereas the term 5 occurs in the sequence near 10^10^23th term.
Examples:
Input: n = 10
Output: 1, 1, 2, 1, 1, 2, 2, 2, 3, 1
Input: n = 220
Output: 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, …, 3, 2, 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 3, 3, 4,
Approach: We have to print the first n terms of the series. We will keep a vector which will store all the previous element of the sequence the next term will be maximum count of repeated blocks of any length. So we will vary the length from 1 to n-1 and then find out the count using a loop.
Example:
- let the sequence be 1, 1, 2, 1, 1, 2
- Take values of i from 0 to 5 first pattern contains “2”.
- 2 is repeated only once from the end of array, next pattern is “1, 2”.
- 1, 2 is repeated only once from the end of array, the next pattern is “1, 1, 2”.
- 1, 1, 2 is repeated twice from the end of array so the count is 2.
Below is the implementation of the above approach:
C++
// C++ program to demonstrate // Gijswijt's sequence #include <bits/stdc++.h> using namespace std; // if the sequence is a(1)a(2)a(3)..a(n-1) // check if the sequence can be represented as // x*(y^k) find the largest value of k int find_count(vector< int > ele) { // count int count = 0; for ( int i = 0; i < ele.size(); i++) { // pattern of elements of size // i from the end of sequence vector< int > p; // count int c = 0; // extract the pattern in a reverse order for ( int j = ele.size() - 1; j >= (ele.size() - 1 - i) && j >= 0; j--) p.push_back(ele[j]); int j = ele.size() - 1, k = 0; // check how many times // the pattern is repeated while (j >= 0) { // if the element doesn't match if (ele[j] != p[k]) break ; j--; k++; // if the end of pattern is reached // set value of k=0 and // increase the count if (k == p.size()) { c++; k = 0; } } count = max(count, c); } // return the max count return count; } // print first n terms of // Gijswijt's sequence void solve( int n) { // set the count int count = 1; // stores the element vector< int > ele; // print the first n terms of // the sequence for ( int i = 0; i < n; i++) { cout << count << ", " ; // push the element ele.push_back(count); // find the count for next number count = find_count(ele); } } // Driver code int main() { int n = 10; solve(n); return 0; } |
Java
// Java program to demonstrate // Gijswijt's sequence import java.util.*; class GFG { // if the sequence is a(1)a(2)a(3)..a(n-1) // check if the sequence can be represented as // x*(y^k) find the largest value of k static int find_count(Vector<Integer> ele) { // count int count = 0 ; for ( int i = 0 ; i < ele.size(); i++) { // pattern of elements of size // i from the end of sequence Vector<Integer> p = new Vector<Integer>(); // count int c = 0 ; // extract the pattern in a reverse order for ( int j = ele.size() - 1 ; j >= (ele.size() - 1 - i) && j >= 0 ; j--) { p.add(ele.get(j)); } int j = ele.size() - 1 , k = 0 ; // check how many times // the pattern is repeated while (j >= 0 ) { // if the element doesn't match if (ele.get(j) != p.get(k)) { break ; } j--; k++; // if the end of pattern is reached // set value of k=0 and // increase the count if (k == p.size()) { c++; k = 0 ; } } count = Math.max(count, c); } // return the max count return count; } // print first n terms of // Gijswijt's sequence static void solve( int n) { // set the count int count = 1 ; // stores the element Vector<Integer> ele = new Vector<Integer>(); // print the first n terms of // the sequence for ( int i = 0 ; i < n; i++) { System.out.print(count + ", " ); // push the element ele.add(count); // find the count for next number count = find_count(ele); } } // Driver code public static void main(String[] args) { int n = 10 ; solve(n); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to demonstrate # Gijswijt's sequence # if the sequence is a(1)a(2)a(3)..a(n-1) # check if the sequence can be represented as # x*(y^k) find the largest value of k def find_count(ele): # count count = 0 for i in range ( len (ele)): # pattern of elements of size # i from the end of sequence p = [] # count c = 0 j = len (ele) - 1 # extract the pattern in a reverse order while j > = ( len (ele) - 1 - i) and j > = 0 : p.append(ele[j]) j - = 1 j = len (ele) - 1 k = 0 # check how many times # the pattern is repeated while j > = 0 : # if the element doesn't match if ele[j] ! = p[k]: break j - = 1 k + = 1 # if the end of pattern is reached # set value of k=0 and # increase the count if k = = len (p): c + = 1 k = 0 count = max (count, c) # return the max count return count # print first n terms of # Gijswijt's sequence def solve(n): # set the count count = 1 # stores the element ele = [] # print the first n terms of # the sequence for i in range (n): print (count, end = " " ) # push the element ele.append(count) # find the count for next number count = find_count(ele) # Driver Code if __name__ = = "__main__" : n = 10 solve(n) # This code is contributed by # sanjeev2552 |
C#
// C# program to demonstrate // Gijswijt's sequence using System; using System.Collections.Generic; class GFG { // if the sequence is a(1)a(2)a(3)..a(n-1) // check if the sequence can be represented as // x*(y^k) find the largest value of k static int find_count(List< int > ele) { // count int count = 0; for ( int i = 0; i < ele.Count; i++) { // pattern of elements of size // i from the end of sequence List< int > p = new List< int >(); // count int c = 0, j; // extract the pattern in a reverse order for (j = ele.Count - 1; j >= (ele.Count - 1 - i) && j >= 0; j--) { p.Add(ele[j]); } j = ele.Count - 1; int k = 0; // check how many times // the pattern is repeated while (j >= 0) { // if the element doesn't match if (ele[j] != p[k]) { break ; } j--; k++; // if the end of pattern is reached // set value of k=0 and // increase the count if (k == p.Count) { c++; k = 0; } } count = Math.Max(count, c); } // return the max count return count; } // print first n terms of // Gijswijt's sequence static void solve( int n) { // set the count int count = 1; // stores the element List< int > ele = new List< int >(); // print the first n terms of // the sequence for ( int i = 0; i < n; i++) { Console.Write(count + ", " ); // push the element ele.Add(count); // find the count for next number count = find_count(ele); } } // Driver code public static void Main(String[] args) { int n = 10; solve(n); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to demonstrate // Gijswijt's sequence // if the sequence is a(1)a(2)a(3)..a(n-1) // check if the sequence can be represented as // x*(y^k) find the largest value of k function find_count(ele) { // count let count = 0; for (let i = 0; i < ele.length; i++) { // pattern of elements of size // i from the end of sequence let p = []; // count let c = 0; // extract the pattern in a reverse order for (let j = ele.length - 1; j >= (ele.length - 1 - i) && j >= 0; j--) p.push(ele[j]); let j = ele.length - 1, k = 0; // check how many times // the pattern is repeated while (j >= 0) { // if the element doesn't match if (ele[j] != p[k]) break ; j--; k++; // if the end of pattern is reached // set value of k=0 and // increase the count if (k == p.length) { c++; k = 0; } } count = Math.max(count, c); } // return the max count return count; } // print first n terms of // Gijswijt's sequence function solve(n) { // set the count let count = 1; // stores the element let ele = []; // print the first n terms of // the sequence for (let i = 0; i < n; i++) { document.write(count + ", " ); // push the element ele.push(count); // find the count for next number count = find_count(ele); } } // Driver code let n = 10; solve(n); </script> |
Output:
1, 1, 2, 1, 1, 2, 2, 2, 3, 1,
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!