stringtranslate.com

Secuencia de Kolakoski

Visualización de los términos 3.º a 50.º de la sucesión de Kolakoski como una espiral. Los términos comienzan en el punto que se encuentra en el medio de la espiral. En la siguiente revolución, cada arco se repite si el término es 1, o se divide en dos mitades iguales si es 2. Los dos primeros términos no se pueden mostrar porque son autorreferenciales. En la imagen SVG, pase el cursor sobre un arco o una etiqueta para resaltarlo y mostrar sus estadísticas.

En matemáticas , la secuencia de Kolakoski , a veces también conocida como secuencia de 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] Recibe su nombre del matemático recreativo William Kolakoski (1944-97), quien la describió en 1965, [3] pero fue discutida previamente por Rufus Oldenburger en 1939. [1] [4]

Definición

La secuencia de Kolakoski describe su propia longitud de ejecución.

Los términos iniciales de la secuencia de Kolakoski son:

1,2,2,1,1,2,1,2,1,2,2,1,2,1,2,1,2,1,1,2,2,1,1,2,1,2,1,2,1,... (secuencia A000002 en la OEIS )

Cada símbolo aparece en una "secuencia" (una secuencia de elementos iguales) de uno o dos términos consecutivos, y al escribir las longitudes de estas secuencias se obtiene 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 lo tanto, la descripción de la secuencia de Kolakoski es reversible. Si K representa "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 se generan a partir de las ejecuciones (es decir, longitudes de ejecución) de K
2. Las ejecuciones 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; el primer 2 genera una serie de "22", que lo incluye a él mismo; el segundo 2 genera una serie de "11"; y así sucesivamente. Cada número de la secuencia es la longitud de la siguiente serie 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,2,1,2 ( l = 15, s = 23)

Como se puede observar, la longitud de la secuencia en cada etapa es igual a la suma de los términos de la etapa anterior. Esta animación ilustra el proceso:

Un gif animado que ilustra cómo los términos posteriores de la secuencia de Kolakoski son generados por términos anteriores.

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 u objeto matemático que codifica su propia representación en otras escalas. [1] Bertran Steinsky ha creado una fórmula recursiva para el término i -ésimo de la secuencia [5] pero se conjetura que la secuencia es aperiódica [6], es decir, sus términos no tienen un patrón repetitivo general (cf. números irracionales como π y √ 2 ).

Investigación

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 menor que 0,50084. [7] Nilsson ha utilizado el mismo método con mucho mayor poder computacional 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 que su densidad convergía a un valor ligeramente diferente de 1/2, [5] cálculos posteriores que extendieron la secuencia a sus primeros 10 13 valores muestran que la desviación de una densidad de 1/2 se hace cada vez más pequeña, como se esperaría si la densidad límite en realidad fuera 1/2. [9]

Conexión con sistemas de etiquetas

La secuencia de Kolakoski también puede describirse como el resultado de un sistema de etiquetas 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 sobre un solo símbolo a la vez), se encuentra en la región de parámetros para los cuales los sistemas de etiquetas son Turing completos , lo que dificulta el uso de esta representación para razonar sobre la secuencia. [10]

Algoritmos

La secuencia de Kolakoski puede generarse mediante un algoritmo que, en la iteración i , lea el valor x i que ya se ha generado como el valor i de la secuencia (o, si aún no se ha generado dicho valor, establezca x i  =  i ). 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:

  1. El primer valor aún no se ha emitido, por lo tanto, establezca x 1  = 1 y emita 1 copia del número 1
  2. El segundo valor aún no se ha emitido, por lo tanto, establezca x 2  = 2 y emita 2 copias del número 2
  3. El tercer valor x 3 se generó como 2 en el segundo paso, por lo que se generan 2 copias del número 1.
  4. El cuarto valor x 4 se generó como 1 en el tercer paso, por lo que se genera 1 copia del número 2. Etc.

Este algoritmo requiere tiempo lineal , pero como necesita hacer referencia a posiciones anteriores en la secuencia, necesita almacenar toda la secuencia, lo que requiere espacio lineal. Se puede utilizar un algoritmo alternativo que genere múltiples copias de la secuencia a diferentes velocidades, en las que cada copia de la secuencia utilice la salida de la copia anterior para determinar qué hacer en cada paso, para generar la secuencia en tiempo lineal y solo en espacio logarítmico . [9]

Véase también

Notas

  1. ^ abc Sloane, N. J. A. (ed.). "Secuencia A000002 (secuencia de Kolakoski: a(n) es la longitud de la n-ésima serie; a(1) = 1; la secuencia consta sólo de 1 y 2)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
  2. ^ Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, cristiano; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de conferencias de matemáticas. vol. 1794. Berlín: Springer-Verlag . pag. 93.ISBN​ 3-540-44141-7.Zbl 1014.11015  .
  3. ^ Kolakoski, William (1965). "Problema 5304". American Mathematical Monthly . 72 : 674. doi :10.2307/2313883. JSTOR  2313883.Para una solución parcial, véase Üçoluk, Necdet (1966). "Self Generating Runs". American Mathematical Monthly . 73 : 681–682. doi :10.2307/2314839. JSTOR  2314839.
  4. ^ Oldenburger, Rufus (1939). "Trayectorias de exponentes en dinámicas simbólicas". Transactions of the American Mathematical Society . 46 (3): 453–466. doi :10.2307/1989933. JSTOR  1989933. MR  0000352.
  5. ^ ab Steinsky, Bertran (2006). "Una fórmula recursiva para la secuencia de Kolakoski A000002" (PDF) . Journal of Integer Sequences . 9 (3). Artículo 06.3.7. Bibcode :2006JIntS...9...37S. MR  2240857. Zbl  1104.11012.
  6. ^ ab Kimberling, Clark . "Secuencias y matrices de números enteros". Universidad de Evansville . Consultado el 13 de octubre de 2016 .
  7. ^ Chvátal, Vašek (diciembre de 1993). Notas sobre la secuencia de Kolakoski. Informe Técnico 93-84. DIMACS.
  8. ^ Nilsson, J. "Frecuencias de letras en la secuencia de Kolakoski" (PDF) . Acta Physics Polonica A . Consultado el 24 de abril de 2014 .
  9. ^ ab Nilsson, Johan (2012). "Un algoritmo eficiente en el uso del espacio para calcular la distribución de dígitos en la secuencia de Kolakoski" (PDF) . Journal of Integer Sequences . 15 (6): Artículo 12.6.7, 13. MR  2954662.
  10. ^ van der Poorten, AJ (1981). "Autómatas de sustitución, ecuaciones funcionales y "funciones algebraicas sobre un cuerpo finito"". Artículos sobre álgebra, análisis y estadística (Hobart, 1981) . Matemáticas contemporáneas. Vol. 9. Providence, Rhode Island: American Mathematical Society. págs. 307–312. MR  0655988.Véase en particular la pág. 308.

Lectura adicional

Enlaces externos