La secuencia de Kolakoski , también conocida como secuencia de Oldenburger-Kolakoski , es una secuencia infinita de números 1 y 2 que es una codificación de longitud de ejecución [1] y un prototipo para una familia infinita de secuencias relacionadas. Originalmente recibió su nombre del matemático William Kolakoski , quien lo propuso en 1965 [2] , pero investigaciones posteriores han demostrado que aparece por primera vez en un artículo de Rufus Oldenburger ) en 1939 [3] .
Comienzo de la secuencia de Kolakoski:
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, ... (secuencia A000002 en OEIS ).
La secuencia, compuesta por el número de dígitos que aparecen en una secuencia en una fila, coincide exactamente con la secuencia original:
1, 2, 2 , 1, 1 , 2, 1, 2, 2 , 1, 2, 2 , 1, 1 , 2, 1, 1 , 2, 2 , 1, 2, 1, 1 , 2, 1, 2, 2 , 1, 1 , … 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, …Por el contrario, cada número en la secuencia de Kolakoski genera uno o dos números siguientes, alternando unos y dos.
Esta propiedad de autogeneración muestra que la secuencia de Kolakoski puede describirse como un fractal, es decir, un objeto matemático que codifica su representación en otras escalas.
La secuencia de Kolakoski se considera aperiódica [4] , es decir, no tiene un patrón repetitivo.
La secuencia de Kolakoski es el prototipo de una familia infinita de otras secuencias, cada una con su propia codificación de longitud de ejecución. Algunas de las secuencias de Kolakoski enumeradas en la OEIS son:
Para el conjunto {1, 3}
1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, … (secuencia A064353 en OEIS )
Para el conjunto {2, 3}
2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, … (secuencia A071820 en OEIS )
Para el conjunto {1, 2, 3}
1, 2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, … (secuencia A079729 en OEIS )
Al igual que la secuencia de Kolakoski para {1,2}, escribir las longitudes de ejecución devuelve la misma secuencia. En general, cualquier conjunto de enteros {n 1 , n 2 , n 3 , …, n i } puede generar una sucesión de Kolakoski si el mismo entero no aparece dos o más veces seguidas y/o al principio y al final de la secuencia. establecer. Por ejemplo, para el conjunto {3,1,2}:
3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, 1, 1, …
Y para el conjunto {2, 1, 3, 1}:
2, 2, 1, 1, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 2, 1, 3, 3, 3, 1, 1, 1, 2, 1, 3, 3, 1, 1, 2, 1, 1, 1, 3, 3, 3, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 3, 3, 3, 1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 3, 3, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 3, 1, 2, 2, 2, 1, 1, 1, 3, 3, 3, 1, 2, 2, 1, 3, 1, 1, 1, …
Nuevamente, escribir las longitudes de ejecución devuelve la misma secuencia.
Las secuencias de Kolakoski también se pueden crear a partir de conjuntos infinitos de enteros.
Por ejemplo, para el conjunto {1, 2, 1, 3, 1, 4, 1, 5, ...}:
1, 2, 2, 1, 1, 3, 1, 4, 4, 4, 1, 5, 5, 5, 5, 1, 1, 1, 1, 6, 6, 6, 6, 1, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 9, 1, 10, 1, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 14, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, …
El conjunto infinito {1,2,3,4,5,…} genera la sucesión de Golomb:
1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12,… ( secuencia OEIS A001462 )
La secuencia de Kolakoski también se puede crear a partir de números enteros elegidos al azar de un conjunto finito, con la restricción de que el mismo número no se puede elegir dos veces seguidas. Para un conjunto finito {1,2,3}, una de las sucesiones posibles es:
2, 2, 1, 1, 3, 1, 3, 3, 3, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 3, 3, 2, 1, 3, 2, 2, 3, 3, 2, 2, 3, 1, 3, 1, 1, 1, 3, 3, 3, 1, 1, 3, 2, 2, 2, 3, 3, 1, 1, 3, 3, 3, 1, 1, 1, 3, 3, 1, 1, 2, 2, 2, 3, 1, 1, 1, 3, 1, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 2, 1, 1, 2, 2, 3, 3, 3, 2, 2, 2, 1, 2, 1, 1, 1, …
Esencialmente, la secuencia se basa en el conjunto infinito {2,1,3,1,3,2,1,2,1,3,2,...}, que es una secuencia aleatoria de 1, 2 y 3 de la cual Se han eliminado las repeticiones.
Así como la secuencia clásica de Kolakoski se genera a sí misma, estas dos secuencias se generan entre sí:
1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2, 1,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2, 2,… (secuencia A025142 en OEIS )
2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,1,2,1,2,2,1,1,2, 1,1,2,2,1,2,1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,1,2,2,… ( secuencia A025143 en OEIS )
En otras palabras, si escribe las longitudes de ejecución de la primera secuencia, se creará la segunda, y si escribe las longitudes de ejecución de la segunda secuencia, se creará la primera.
En la siguiente cadena de tres secuencias de longitud de ejecución, cada una genera lo siguiente:
1,1,2,2,3,3,1,1,1,2,3,1,1,2,2,3,3,3,1,1,1,2,2,2,3, 1,2,3,3,1,1,1,2,3,3,… (secuencia A288723 en OEIS )
2,2,2,3,1,1,2,2,3,3,3,1,1,1,2,3,1,2,2,3,3,1,1,2,2, 2,3,1,1,2,2,2,3,3,3,… (secuencia A288724 en OEIS )
3,1,2,2,3,3,1,1,1,2,2,2,3,1,2,3,3,1,1,1,2,3,1,1,2, 2,3,3,3,1,1,1,2,2,2,… (secuencia A288725 en OEIS )
Las secuencias usan el conjunto entero {1,2,3}, pero cada secuencia comienza con un elemento diferente del conjunto.
Las siguientes cinco secuencias forman una cadena similar usando el conjunto {1,2,3,4,5}:
1,1,2,2,3,3,4,4,4,5,5,5,1,1,1,2,2,2,2,3,3,3,3,4,4, 4,4,5,5,5,5,5,…
2,2,2,3,3,3,4,4,4,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,4, 4,4,4,5,5,5,5,5,…
3,3,3,3,4,4,4,4,5,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,3, 4,5,1,1,2,2,3,3,3,…
4,4,4,4,4,5,1,1,2,2,3,3,3,4,4,4,5,5,5,5,1,1,1,1,2, 2,2,2,3,3,3,3,3,…
5,1,2,2,3,3,4,4,4,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,4, 4,4,4,4,…
Sin embargo, para crear una cadena de n elementos, no es necesario tener un conjunto de n elementos. Por ejemplo, la siguiente cadena de cinco secuencias usa el conjunto {1, 2}:
2,1,1,2,2,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2, 1,1,2,1,1,2,2,1,…
1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,1,2,1,1, 2,1,1,2,2,1,2,2,…
1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1, 2,1,1,2,2,1,2,1,…
1,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1, 2,2,1,2,1,1,2,1,…
1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2, 1,2,1,1,2,1,2,2,…
Cada secuencia es única y las longitudes de ejecución de cada una generan los miembros de la siguiente secuencia en la cadena. Los conjuntos de enteros utilizados para crear la cadena también pueden ser de diferentes tamaños. A partir de los conjuntos {1,2} y {1,2,3,4,5} se generan las siguientes secuencias:
1,2,2,1,1,2,2,2,1,1,1,2,2,2,2,1,1,1,1,1,2,1,2,2,1, 1,2,2,2,…
1,2,2,3,3,4,5,1,1,2,2,3,3,4,5,1,2,2,3,3,4,4,5,5,1, 2,3,4,5,…
Parece plausible que la fracción de unos en la secuencia clásica de Kolakoski sea 1/2, pero esta conjetura sigue sin probarse. [4] Václav Chvátal demostró que el límite superior de la fracción de unidades es inferior a 0,50084 [5] . John Nilson usó el mismo método con mucho más poder computacional para obtener un límite de 0.500080 [6] .
Aunque en los cálculos se usaron los primeros 3×10 8 valores de la secuencia, aparentemente su densidad converge a un valor ligeramente diferente de 1/2, pero cálculos posteriores mostraron que la expansión de la secuencia en los primeros 10 13 valores se desvía de la fracción de unidades 1/2 cada vez menos, por lo que podemos esperar que la fracción límite de unidades sea en realidad 1/2 [7] .
En la secuencia antikolakoski, las longitudes de las series de unos y dos nunca coinciden con los miembros de la secuencia original:
2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, … (secuencia A049705 en el OEIS ).
2, 1, 1 , 2, 2 , 1, 2, 1, 1 , 2, 1, 1 , 2, 2 , 1, 2, 2 , 1, 1 , 2, 1, 2, 2 , 1, 2, 1, 1 , 2, 2 , 1, … 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, …Como puede ver, los unos en la secuencia antikolakoski están en las posiciones donde los dos están en la secuencia clásica de Kolakoski, y viceversa.
La constante de Kolakoski se define en notación binaria de la siguiente manera. En cada posición binaria después del punto decimal hay un 1 si la posición correspondiente de la secuencia clásica de Kolakoski es un dos y un 0 si es una unidad [8] . La primera unidad de la secuencia se ignora. De este modo,
0.11001011011001001101001011001001011… 2 = 0.7945071927794792762403624156360456462… 10 .