En matemáticas , la secuencia Kolakoski , a veces también conocida como secuencia Oldenburger-Kolakoski , [1] es una secuencia infinita de símbolos {1,2} que es la secuencia de longitudes de ejecución en su propia codificación de longitud de ejecución . [2] Lleva el nombre del matemático recreativo William Kolakoski (1944-1997) que lo describió en 1965, [3] pero fue discutido previamente por Rufus Oldenburger en 1939. [1] [4]
Definición
Los términos iniciales de la secuencia de Kolakoski son:
Cada símbolo ocurre en una "secuencia" (una secuencia de elementos iguales) de uno o dos términos consecutivos, y escribir las longitudes de estas corridas da exactamente la misma secuencia:
- 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 , 2, 1,1 , 2,1, 2,2 , 1, 2,2 , 1,1 , 2,1, 2,2 , ...
- 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, 2, ...
Por tanto, la descripción de la secuencia de Kolakoski es reversible. Si K significa "la secuencia de Kolakoski", la descripción n. ° 1 implica lógicamente la descripción n. ° 2 (y viceversa):
- 1. Los términos de K son generados por las corridas (es decir, longitudes de corrida) de K
- 2. Las corridas de K son generadas por los términos de K
En consecuencia, se puede decir que cada término de la secuencia de Kolakoski genera una serie de uno o dos términos futuros. El primer 1 de la secuencia genera una serie de "1", es decir, él mismo; los primeros 2 generan una serie de "22", que se incluye a sí mismo; el segundo 2 genera una serie de "11"; y así. Cada número de la secuencia es la duración de la siguiente ejecución que se generará, y el elemento que se generará alterna entre 1 y 2:
- 1,2 (longitud de la secuencia l = 2; suma de términos s = 3)
- 1,2,2 ( l = 3, s = 5)
- 1,2,2,1,1 ( l = 5, s = 7)
- 1,2,2,1,1,2,1 ( l = 7, s = 10)
- 1,2,2,1,1,2,1,2,2,1 ( l = 10, s = 15)
- 1,2,2,1,1,2,1,2,2,1,2,2,1,1,2 ( l = 15, s = 23)
Como puede verse, la longitud de la secuencia en cada etapa es igual a la suma de términos en la etapa anterior. Esta animación ilustra el proceso:
Estas propiedades autogeneradoras, que permanecen si la secuencia se escribe sin el 1 inicial, significan que la secuencia de Kolakoski puede describirse como un fractal , o un objeto matemático que codifica su propia representación en otras escalas. [1] Bertran Steinsky ha creado una fórmula recursiva para el i -ésimo término de la secuencia [5] pero se conjetura que la secuencia es aperiódica , [6] es decir, sus términos no tienen un patrón general de repetición (cf. irracional números como π y √ 2 ).
Investigar
Densidad
Parece plausible que la densidad de 1s en la secuencia {1,2} de Kolakoski sea 1/2, pero esta conjetura sigue sin demostrarse. [6] Václav Chvátal ha demostrado que la densidad superior de 1s es inferior a 0,50084. [7] Nilsson ha utilizado el mismo método con un poder computacional mucho mayor para obtener el límite 0.500080. [8]
Aunque los cálculos de los primeros 3 × 10 8 valores de la secuencia parecían mostrar su densidad convergiendo a un valor ligeramente diferente de 1/2, [5] cálculos posteriores que extendieron la secuencia a sus primeros 10 13 valores muestran la desviación de una densidad de 1/2 cada vez más pequeño, como cabría esperar si la densidad límite en realidad es 1/2. [9]
Conexión con sistemas de etiquetas
La secuencia de Kolakoski también se puede describir como el resultado de un sistema de etiqueta cíclico simple . Sin embargo, como este sistema es un sistema de 2 etiquetas en lugar de un sistema de 1 etiqueta (es decir, reemplaza pares de símbolos por otras secuencias de símbolos, en lugar de operar en un solo símbolo a la vez), se encuentra en la región de parámetros para los cuales los sistemas de etiquetas están completos en Turing , lo que dificulta el uso de esta representación para razonar sobre la secuencia. [10]
Unicidad
Algunas discusiones sobre la secuencia clásica de Kolakoski afirman que, escrita con o sin el 1 inicial, es la "única secuencia" que tiene su propia codificación de longitud de ejecución o la única secuencia de este tipo que comienza con 1. [11] [6 ] Como se puede ver arriba, esto no es cierto: un número infinito de secuencias adicionales poseen estas propiedades. Sin embargo, las secuencias {1,2} y {2,1} de Kolakoski son las únicas secuencias que utilizan únicamente los números enteros 1 y 2.
Algoritmos
La secuencia de Kolakoski puede ser generada por un algoritmo que, en la i -ésima iteración, lee el valor x i que ya se ha emitido como el i -ésimo valor de la secuencia (o, si aún no se ha emitido dicho valor, establece x yo = yo ). Entonces, si i es impar, genera x i copias del número 1, mientras que si i es par, genera x i copias del número 2. Por lo tanto, los primeros pasos del algoritmo son:
- El primer valor aún no se ha emitido, por lo tanto, establezca x 1 = 1 y envíe 1 copia del número 1
- El segundo valor aún no se ha emitido, por lo tanto, establezca x 2 = 2 y envíe 2 copias del número 2
- El tercer valor x 3 se generó como 2 en el segundo paso, por lo que se generan 2 copias del número 1.
- El cuarto valor x 4 se imprimió como 1 en el tercer paso, por lo que se imprime 1 copia del número 2. Etc.
Este algoritmo toma un tiempo lineal , pero debido a que necesita hacer referencia a posiciones anteriores en la secuencia, necesita almacenar la secuencia completa, ocupando un espacio lineal. Un algoritmo alternativo que genera múltiples copias de la secuencia a diferentes velocidades, con cada copia de la secuencia usando la salida de la copia anterior para determinar qué hacer en cada paso, se puede usar para generar la secuencia en tiempo lineal y solo en espacio logarítmico. . [9]
Ver también
- Secuencia de Golomb : otra secuencia autogenerada basada en la duración de la ejecución
- Secuencia de Gijswijt
- Secuencia de mirar y decir
Notas
- ^ a b c Sloane, N. J. A. (ed.). "Secuencia A000002 (secuencia de Kolakoski: a (n) es la longitud de la enésima ejecución; a (1) = 1; la secuencia consta sólo de unos y dos)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de clase en matemáticas. 1794 . Berlín: Springer-Verlag . pag. 93. ISBN 3-540-44141-7. Zbl 1014.11015 .
- ^ Kolakoski, William (1965). "Problema 5304". American Mathematical Monthly . 72 : 674. doi : 10.2307 / 2313883 . Para obtener una solución parcial, consulte Üçoluk, Necdet (1966). "Carreras autogeneradoras". American Mathematical Monthly . 73 : 681–682. doi : 10.2307 / 2314839 .
- ^ Oldenburger, Rufus (1939). "Trayectorias de exponentes en dinámica simbólica". Transacciones de la American Mathematical Society . 46 : 453–466. doi : 10.2307 / 1989933 . Señor 0000352 .
- ^ a b Steinsky, Bertran (2006). "Una fórmula recursiva para la secuencia de Kolakoski A000002" (PDF) . Diario de secuencias de enteros . 9 (3). Artículo 06.3.7. Señor 2240857 . Zbl 1104.11012 .
- ^ a b c Kimberling, Clark . "Secuencias de enteros y matrices" . Universidad de Evansville . Consultado el 13 de octubre de 2016 .
- ^ Chvátal, Vašek (diciembre de 1993). Notas sobre la secuencia Kolakoski . Informe técnico 93-84. DIMACS.
- ^ Nilsson, J. "Frecuencias de letras en la secuencia Kolakoski" (PDF) . Acta Física Polonica A . Consultado el 24 de abril de 2014 .
- ^ a b Nilsson, Johan (2012). "Un algoritmo de espacio eficiente para calcular la distribución de dígitos en la secuencia de Kolakoski" (PDF) . Diario de secuencias de enteros . 15 (6): Artículo 12.6.7, 13. MR 2954662 .
- ^ van der Poorten, AJ (1981). "Autómatas de sustitución, ecuaciones funcionales y" funciones algebraicas sobre un campo finito " ". Artículos de álgebra, análisis y estadística (Hobart, 1981) . Matemáticas contemporáneas. 9 . Providence, Rhode Island: Sociedad Matemática Estadounidense. págs. 307–312. Señor 0655988 .Ver en particular la p. 308 .
- ^ Bellos, Alex (7 de octubre de 2014). "Neil Sloane: el hombre que amaba sólo secuencias enteras" . The Guardian . Consultado el 13 de junio de 2017 .
Otras lecturas
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Prensa de la Universidad de Cambridge . pag. 337 . ISBN 978-0-521-82332-6. Zbl 1086.11015 .
- Dekking, FM (1997). "¿Qué es el orden de largo alcance en la secuencia de Kolakoski?". En Moody, RV (ed.). Actas del Instituto de Estudios Avanzados de la OTAN, Waterloo, ON, del 21 de agosto al 1 de septiembre de 1995 . Dordrecht, Países Bajos: Kluwer. págs. 115-125.
- Fedou, JM; Fici, G. (2010). "Algunas observaciones sobre secuencias diferenciables y recursividad" (PDF) . Diario de secuencias de enteros . 13 (3). Artículo 10.3.2.
- Keane, MS (1991). "Teoría ergódica y subdesplazamientos de tipo finito". En Bedford, T .; Keane, M. (eds.). Teoría ergódica, dinámica simbólica y espacios hiperbólicos . Oxford, Inglaterra: Oxford University Press. págs. 35–70.
- Lagarias, JC (1992). "Teoría de números y sistemas dinámicos" . En Burr, SA (ed.). La efectividad irrazonable de la teoría de números . Providence, RI: Sociedad Matemática Estadounidense. págs. 35–72.
- Păun, Gheorghe; Salomaa, Arto (1996). "Secuencias de autolectura". American Mathematical Monthly . 103 : 166-168. doi : 10.2307 / 2975113 . Zbl 0854.68082 .
- Shallit, Jeffrey (1999). "Teoría de números y lenguajes formales". En Hejhal, Dennis A .; Friedman, Joel; Gutzwiller, Martin C .; Odlyzko, Andrew M. (eds.). Aplicaciones emergentes de la teoría de números. Basado en las actas del programa de verano de IMA, Minneapolis, MN, EE. UU., 15 al 26 de julio de 1996 . Los volúmenes IMA en matemáticas y sus aplicaciones. 109 . Springer-Verlag . págs. 547–570. ISBN 0-387-98824-6. Zbl 0919.00047 .
enlaces externos
- Weisstein, Eric W. "Secuencia Kolakoski" . MathWorld .
- Constante de Kolakoski a 25000 dígitos calculada por Olivier Gerard en abril de 1998
- Bellos, Alex . "La secuencia de Kolakoski" (video) . Brady Haran . Consultado el 24 de julio de 2017 .