Secuencia de Gijswijt

La secuencia de Gijswijt es una secuencia autodescriptiva en la que el valor de cada término es igual al número máximo de bloques repetidos de números en la secuencia que precede al número.
Tomemos el i ^-ésimo término de la sucesión a(i), luego para esta sucesión de Gijswijt: 
 

donde k es el número natural más grande tal que la palabra a(1)a(2)..a(n) puede representarse como x*(y^k) donde la longitud de y no es cero.
La secuencia de Gijswijt es la siguiente: 

1, 1, 2, 1, 1, 2, 2, 2, 3, 1, ...

Se puede probar que cada número natural ocurre en esta secuencia al menos una vez, pero la secuencia tiene un crecimiento muy lento. ^{El término} 220 es 4 mientras que el término 5 aparece en la secuencia cerca del término 10 ^{^} 10^23 .
Ejemplos: 

Entrada: n = 10 
Salida: 1, 1, 2, 1, 1, 2, 2, 2, 3, 1
Entrada: n = 220 
Salida: 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,  

Planteamiento: Tenemos que imprimir los primeros n términos de la serie. Mantendremos un vector que almacenará todo el elemento anterior de la secuencia, el siguiente término será el recuento máximo de bloques repetidos de cualquier longitud. Entonces, variaremos la longitud de 1 a n-1 y luego encontraremos el conteo usando un bucle.
Ejemplo:  

• Sea la secuencia 1, 1, 2, 1, 1, 2
• Tome valores de i de 0 a 5, el primer patrón contiene «2».
• 2 se repite solo una vez desde el final de la array, el siguiente patrón es «1, 2».
• 1, 2 se repite solo una vez desde el final de la array, el siguiente patrón es «1, 1, 2».
• 1, 1, 2 se repite dos veces desde el final de la array, por lo que la cuenta es 2.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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

<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>

Producción:  

1, 1, 2, 1, 1, 2, 2, 2, 3, 1,