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 del3er término. [1]
Definición
El proceso para generar términos en la secuencia se puede definir observando la secuencia como una serie de letras en el alfabeto de números naturales :
- , y
- , dónde es el número natural más grande tal que la palabra se puede escribir en la forma por algunas palabras y , con que tiene una longitud distinta de cero.
La secuencia es de base- agnóstica. Es decir, si se encuentra una serie de 10 bloques repetidos, el siguiente término de la secuencia sería un solo número 10, no un 1 seguido de un 0.
Explicación
La secuencia comienza con 1 por definición. El 1 en el segundo término representa la longitud 1 del bloque de 1 que se encuentra inmediatamente antes en el primer término. El 2 en el tercer término representa la longitud 2 del bloque de unos 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 secuencia repetida inmediatamente antes del cuarto término que sea más largo que 1. El bloque de dos 1 en el primer y segundo término no se puede considerar para el cuarto término porque están separados por un número diferente en el tercer término. .
El 1 en el 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 en el sexto término representa la longitud del bloque repetido de 1 que conduce inmediatamente al sexto término, es decir, los del cuarto y quinto término. El 2 en el séptimo término representa las 2 repeticiones del bloque "1, 1, 2" que abarcan los términos 1-3 y luego 4-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 en el octavo término representa la longitud del bloque repetido de 2 que conduce inmediatamente al octavo término, es decir, los dos en el sexto y séptimo términos. El 3 en el noveno término representa el bloque tres veces repetido de 2 individuales que conducen inmediatamente al noveno término, es decir, los dos en el sexto, séptimo y octavo términos.
Propiedades
Solo una investigación limitada se ha centrado en la secuencia de Gijswijt. Como tal, se ha probado muy poco sobre la secuencia y muchas preguntas abiertas siguen sin resolverse.
Tasa de crecimiento
Dado que el 5 no aparece hasta alrededor , las técnicas de búsqueda de fuerza bruta nunca encontrarían la primera aparición de un término mayor que 4. Sin embargo, se ha demostrado que la secuencia contiene todos los números naturales. [2] Se desconoce la tasa exacta de crecimiento, pero se conjetura que crecerá superlogarítmicamente , con la primera aparición de cualquier colocado cerca . [3]
Valor promedio
Aunque se sabe que cada número natural ocurre en una posición finita dentro de la secuencia, se ha conjeturado que la secuencia puede tener una media finita . Para definir esto formalmente en una secuencia infinita, donde el reordenamiento de los términos puede ser importante, la conjetura es que:
Asimismo, se desconoce la densidad de cualquier número natural dado dentro de la secuencia. [1]
Estructura recursiva
La secuencia se puede dividir en secuencias discretas de "bloque" y "pegamento", que se pueden utilizar para construir de forma recursiva la secuencia. Por ejemplo, en el nivel base, podemos definir y como el primer bloque y secuencias de pegado, respectivamente. Juntos, podemos ver cómo forman el comienzo de la secuencia:
El siguiente paso es construir de forma recursiva la secuencia. Definir. Observando que la secuencia comienza con, podemos definir una cuerda de pegamento lo que da:
Asignamos a una secuencia particular que da la propiedad que también ocurre en la parte superior de la secuencia.
Este proceso se puede continuar indefinidamente con . Resulta que podemos descubrir una cuerda de pegamento. notando que nunca tendrá un 1, y que se detiene una vez que alcanza el primer 1 siguiente . [3] También se ha demostrado que la secuencia de Gijswijt se puede construir de esta manera indefinidamente, es decir, y son siempre finitos en longitud para cualquier . [2]
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.
Ver también
Referencias
- ^ a b c Sloane, N. J. A. (ed.). "Secuencia A090822 (secuencia de Gijswijt: a (1) = 1; para n> 1, a (n) = entero más grande k tal que la palabra a (1) a (2) ... a (n-1) es de la forma xy ^ k para las palabras xey (donde y tiene una longitud positiva), es decir, el número máximo de bloques repetidos al final de la secuencia hasta ahora) " . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ a b Gijswijt, DC (2006). "Una secuencia de crecimiento lento definida por una recurrencia inusual". arXiv : matemáticas / 0602498 .
- ^ a b Sloane, Neil . "Siete secuencias asombrosas" (PDF) . Laboratorio AT&T Shannon. pag. 3.
enlaces externos
- Primeros 50 millones de términos
- Secuencia OEIS A091579 (longitudes de los bloques de sufijo asociados con A090822) - (las longitudes de las secuencias de pegamento)