Secuencia de mirar y decir

En matemáticas, la secuencia de mirar y decir es la secuencia de números enteros que comienza de la siguiente manera:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221,... (secuencia) A005150 en el OEIS).

Para generar un miembro de la secuencia a partir del miembro anterior, lea los dígitos del miembro anterior, contando el número de dígitos en grupos del mismo dígito. Por ejemplo:

• 1 se lee como "uno 1" o 11.
• 11 se lee como "dos 1s" o 21.
• 21 se lee como "uno, uno 1" o 1211.
• 1211 se lee como "uno 1, uno, dos 1s" o 111221.
• 111221 se lee como "tres 1s, dos 2s, uno 1" o 312211.

La secuencia de mirar y decir fue analizada por John Conway después de que uno de sus alumnos se lo presentara en una fiesta.

La idea de la secuencia de mirar y decir es similar a la de la codificación de longitud de ejecución.

Si comienza con cualquier dígito d del 0 al 9, entonces d permanecerá indefinidamente como el último dígito de la secuencia. Para cualquier d distinto de 1, la secuencia comienza de la siguiente manera:

d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d,...

Ilan Vardi ha llamado a esta secuencia, comenzando con d = 3, la secuencia de Conway (secuencia A006715 en la OEIS). (para d = 2, consulte OEIS: A006751)

Propiedades básicas

Crecimiento

La secuencia crece indefinidamente. De hecho, cualquier variante definida comenzando con un número semilla entero diferente (eventualmente) también crecerá indefinidamente, excepto la secuencia degenerada: 22, 22, 22, 22,... (sequence A010861 en la OEIS)

Limitación de presencia de dígitos

No aparecen dígitos distintos de 1, 2 y 3 en la secuencia, a menos que el número inicial contenga dicho dígito o una serie de más de tres del mismo dígito.

Decadencia cosmológica

El teorema cosmológico de Conway afirma que toda secuencia eventualmente se divide ("se desintegra") en una secuencia de "elementos atómicos", que son finitos. subsecuencias que nunca más interactúan con sus vecinos. Hay 92 elementos que contienen únicamente los dígitos 1, 2 y 3, a los que John Conway nombró en honor a los 92 elementos químicos naturales hasta el uranio, llamando a la secuencia audioactiva. También hay dos "transuránicos" elementos (Np y Pu) para cada dígito distinto de 1, 2 y 3. A continuación se muestra una tabla de todos esos elementos:

Crecimiento en longitud

Los términos eventualmente crecen en longitud alrededor del 30% por generación. En particular, si L_n denota el número de dígitos del n-el miembro de la secuencia, luego el límite de la relación ${displaystyle {frac {fn+1}{L_{n}}} {fn}} {fn}}} {fn}}} {fn}}}} {fn}}}}} {fn}}}}}}} {fn}}}}}}} {fn}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {$ existe y se da por

$${displaystyle lim _{nto infty}{frac {L_{n+1}{L_{n}=lambda }$$

donde λ = 1.303577269034... (secuencia A014715 en el OEIS) es un número algebraico de grado 71. Este hecho fue demostrado por Conway, y la constante λ es conocida como constante de Conway. El mismo resultado también es válido para cada variante de la secuencia que comienza con cualquier semilla distinta de 22.

La constante de Conway como raíz polinómica

La constante de Conway es la única raíz real positiva del siguiente polinomio (secuencia A137275 en el OEIS):

$${x}$$

Este polinomio se dio correctamente en el original de Conway Eureka artículo, pero en la versión reimprimida en el libro editado por Cover y Gopinath el término ${displaystyle x^{35}$ estaba incorrectamente impreso con un signo menos en el frente.

Divulgación

La secuencia de mirar y decir también se conoce popularmente como secuencia numérica de Morris, en honor al criptógrafo Robert Morris, y el rompecabezas "¿Cuál es el siguiente número en la secuencia 1, 11?"., 21, 1211, 111221?" a veces se le conoce como el huevo del cuco, según una descripción de Morris en el libro de Clifford Stoll El huevo del cuco.

Variaciones

Existen muchas variaciones posibles de la regla utilizada para generar la secuencia de mirar y decir. Por ejemplo, para formar el "patrón de guisantes" uno lee el término anterior y cuenta todas las instancias de cada dígito, enumeradas en orden de primera aparición, no solo las que ocurren en un bloque consecutivo. Entonces, comenzando con la semilla 1, el patrón de guisantes continúa 1, 11 ("un 1"), 21 ("dos 1"), 1211 ("un 2 y un 1& #34;), 3112 ("tres 1 y un 2"), 132112 ("un 3, dos 1 y un 2"), 311322 ("tres 1, uno 3 y dos 2s"), etc. Esta versión del patrón de guisante eventualmente forma un ciclo con los dos "atómicos" términos 23322114 y 32232114.

También son posibles otras versiones del patrón de guisantes; por ejemplo, en lugar de leer los dígitos como aparecen por primera vez, se podrían leer en orden ascendente. En este caso, el término que sigue a 21 sería 1112 ("un 1, un 2") y el término que sigue a 3112 sería 211213 ("dos 1, un 2 y un 3").

Estas secuencias difieren en varios aspectos notables de la secuencia de mirar y decir. En particular, a diferencia de las secuencias de Conway, un término dado del patrón de guisante no define de forma única el término anterior. Además, para cualquier semilla, el patrón de guisante produce términos de longitud limitada: este límite normalmente no excederá 2 × Radix + 2 dígitos (22 dígitos para decimales).: radix = 10) y solo puede exceder 3 × radix dígitos (30 dígitos para la base decimal) de longitud para semillas iniciales largas, degeneradas (secuencia de "100 unos", etc.). Para estos casos extremos, los elementos individuales de secuencias decimales se asientan inmediatamente en una permutación de la forma a0 b1 c2 d3 e4 f5 g6 h7 i8 j9 donde aquí las letras a–j son marcadores de posición para los recuentos de dígitos del elemento de secuencia anterior.

Dado que la secuencia es infinita y la longitud de cada elemento está limitada, debe eventualmente repetirse, debido al principio del casillero. Como consecuencia, las secuencias del patrón de guisante siempre son eventualmente periódicas.