En matemáticas , la secuencia de Gijswijt (nombrada en honor a Dion Gijswijt por Neil Sloane [1] ) es una secuencia autodescriptiva donde cada término cuenta el número máximo de bloques repetidos de números en la secuencia inmediatamente anterior a ese término.
La secuencia comienza con:
La secuencia es similar en definición a la secuencia de Kolakoski , pero en lugar de contar la serie más larga de términos individuales, la secuencia cuenta la serie más larga de bloques de términos de cualquier longitud. La secuencia de Gijswijt es conocida por su tasa de crecimiento notablemente lenta. Por ejemplo, los primeros 4 aparecen en el término 220 y los primeros 5 aparecen cerca del tercer término. [1]
El proceso para generar términos en la secuencia se puede definir mirando la secuencia como una serie de letras en el alfabeto de números naturales :
La secuencia es independiente de la base . Es decir, si se encuentra una serie de 10 bloques repetidos, el siguiente término de la secuencia sería un único número 10, no un 1 seguido de un 0.
La secuencia comienza con 1 por definición. El 1 en el segundo término representa entonces la longitud 1 del bloque de 1 que se encuentra inmediatamente antes de él en el primer término. El 2 en el tercer término representa la longitud 2 del bloque de 1 que están en el primer y segundo término. En este punto, la secuencia disminuye por primera vez: el 1 en el cuarto término representa la longitud 1 del bloque de 2 en el tercer término, así como la longitud 1 del bloque "1, 2" que abarca el segundo y tercer término. No hay ningún bloque de ninguna secuencia repetida inmediatamente anterior al cuarto término que sea más largo que 1. El bloque de dos 1 en el primer y segundo término no puede considerarse para el cuarto término porque están separados por un número diferente en el tercer término.
El 1 del quinto término representa la longitud 1 de los bloques "repetidos" "1" y "2, 1" y "1, 2, 1" y "1, 1, 2, 1" que preceden inmediatamente al quinto término. Ninguno de estos bloques se repite más de una vez, por lo que el quinto término es 1. El 2 del sexto término representa la longitud del bloque repetido de 1 que precede inmediatamente al sexto término, es decir, los que están en los términos 4 y 5. El 2 del séptimo término representa las 2 repeticiones del bloque "1, 1, 2" que abarca los términos 1 a 3 y luego 4 a 6. Esta "palabra de 3 números" aparece dos veces inmediatamente antes del séptimo término, por lo que el valor del séptimo término es 2.
El 2 del octavo término representa la longitud del bloque repetido de 2 que conduce inmediatamente al octavo término, es decir, los dos del sexto y séptimo término. El 3 del noveno término representa el bloque repetido tres veces de 2 sencillos que conduce inmediatamente al noveno término, es decir, los dos del sexto, séptimo y octavo término.
La secuencia de Gijswijt ha sido objeto de una investigación limitada, por lo que se ha demostrado muy poco sobre ella y quedan muchas preguntas sin resolver.
Aunque se sabe que cada número natural aparece en una posición finita dentro de la secuencia, se ha demostrado que la secuencia tiene una media finita . Para definir esto formalmente en una secuencia infinita, donde la reordenación de los términos puede ser importante, se sabe que
De la misma manera, se sabe que la densidad de cualquier número natural dado dentro de la secuencia es finita. [2]
En 2006, Gijswijt demostró que la secuencia contiene todos los números naturales. [3] La secuencia crece aproximadamente de forma superlogarítmica , y la primera aparición de cualquier número natural se sitúa aproximadamente en . Levi van de Pol encontró una expresión en forma cerrada para el primer índice en el que aparece un entero positivo dado , en términos de una constante y una secuencia de constantes . [2]
Por ejemplo, la posición de los primeros 5 viene dada por
donde . Expandido, este número es aproximadamente
La primera instancia de dos 4 consecutivos comienza en la posición
Ambos números tienen 108 dígitos y fueron publicados por primera vez por van de Pol.
La secuencia se puede dividir en secuencias discretas de "bloques" y "pegamento", que se pueden utilizar para construir la secuencia de forma recursiva. Por ejemplo, en el nivel base, podemos definir y como las primeras secuencias de bloques y pegamento, respectivamente. Juntas, podemos ver cómo forman el comienzo de la secuencia:
El siguiente paso es construir la secuencia de forma recursiva. Defina . Observando que la secuencia comienza con , podemos definir una cadena de unión que da:
Asignamos a una secuencia particular que da la propiedad que también ocurre en la parte superior de la secuencia.
Este proceso puede continuar indefinidamente con . Resulta que podemos descubrir una cadena de pegamento al notar que nunca tendrá un 1, y que se detiene una vez que llega al primer 1 que sigue a . [4] También se ha demostrado que la secuencia de Gijswijt puede construirse de esta manera indefinidamente, es decir, y siempre tienen una longitud finita para cualquier . [3]
La manipulación inteligente de las secuencias de pegamento en esta estructura recursiva se puede utilizar para demostrar que la secuencia de Gijswijt contiene todos los números naturales, entre otras propiedades de la secuencia.
