¿Cómo puedo saber si este algoritmo converge?

Question

Este es un algoritmo desarrollado como una broma que me ha llevado a un problema que no puedo resolver.

En $,$ el operador de concatenación, dado $$x_0 = a_{(0,0)},a_{(0,1)},a_{(0,2)},\dots,a_{(0,n)}$$ definimos $$x_{i+1}=(a_{(i,0)}+a_{(i,1)}),(a_{(i,1)}+a_{(i,2)}),\dots,(a_{(i,n-1)}+a_{(i,n)})$$

Por ejemplo: $$ \begin{split} 1234\\ 357\\ 812\\ 93\\ 12\\ 3 \end{split} $$

Ahora, esto no siempre converge, pero no puedo entender por qué en general. Por ejemplo, en base 10, $99a$ bucles, $8888$ bucles...

Estoy tratando de desarrollar una función que, dado un número, dé como resultado si el algoritmo converge (sin comprobar toda la historia de los bucles for).

Aquí un frasco que hice que calcula el algoritmo dado un número inicial.

Aquí la misma pregunta en Quora, con algunas otras ideas útiles.

Answer 1

Estos son mis resultados:

Números de 2 dígitos

El número de 2 dígitos no genera bucles.

Prueba

En $,$ el operador de concatenación, para números de 2 dígitos, definimos $x_0=a_{(0,0)},a_{(0,1)}$ . Así que: $$x_1=c_{(1,0)},a_{(1,0)}$$ donde $$a_{(1,0)}=a_{(0,0)}+a_{(0,1)} \pmod{base}$$ Dónde $c_{(i,j)}$ es el dígito de arrastre del $j^{th}$ operación en el $i^{th}$ iteración, que supondremos que es una (de lo contrario sería trivial). Entonces, como $$x_2=c_{(2,0)},(c_{(1,0)}+a_{(1,0)} \bmod{base})$$ y, como $$\left( a_{(0,0)} \lt base \land a_{(0,1)} \lt base \right) \implies a_{(1,0)} \lt base-1 \implies c_{(2,0)}=0$$ (es decir, en base 10, no hay dos números de un solo dígito que sumen 19). Así que en la tercera iteración este es un número de un solo dígito y por lo tanto converge.

Números de 3 dígitos

Para encontrar ciclos para un número de 3 dígitos repetimos el mismo razonamiento para cada par de dígitos y elegimos que cada dígito en la segunda iteración sea igual al correspondiente en la $0^{th}$ iteración. Obtenemos que dado $$x_0=a_{(0,0)},a_{(0,1)},a_{(0,2)}$$ tenemos un ciclo $iff$ $$a_0=a_1 \equiv -1 \pmod{base}, \forall a_2$$

Prueba

Calculamos $x_1$ como $$x_1=c_{(1,0)},a_{(1,0)},c_{(1,1)},a_{(1,1)}$$ donde elegimos $c_{(1,i)}=1$ De lo contrario, sería trivial. $$ \begin{align} a_{(1,0)}&=a_{(0,0)}+a_{(0,1)} \pmod{base}\\ a_{(1,1)}&=a_{(0,1)}+a_{(0,2)} \pmod{base} \end{align} $$

Caso $c_{(1,0)}=c_{(1,1)}=0$

Este es el caso de 2 dígitos, analizado anteriormente.

Caso $c_{(1,0)}=1 \land c_{(1,1)}=0$

En este caso, $$ \begin{align} x_0&=a_{(0,0)},a_{(0,1)},a_{(0,2)}\\ x_1&=c_{(1,0)},a_{(1,0)},a_{(1,1)}\\ x_2&=a_{(2,0)},c_{(2,1)},a_{(2,1)} \end{align} $$

donde elegimos $c_{(2,1)}=1$ De lo contrario, sería trivial

$$ \begin{align} a_{(2,0)}&=c_{(1,0)}+a_{(1,0)}\\ a_{(2,1)}&=a_{(1,1)}+a_{(1,2)} \end{align} $$

Elegimos $x_2=x_0$ Así que $$ \begin{align} a_{(2,0)}&=a_{(0,0)}\\ c_{(2,1)}&=a_{(0,1)}\\ a_{(2,2)}&=a_{(0,2)} \end{align} $$

De la primera ecuación: $$ \begin{align} a_{(0,0)} = a_{(2,0)} &= c_{(1,0)}+\left(a_{(0,0)}+a_{(0,1)} \pmod{base}\right)\\ a_{(0,0)}-1 &= a_{(0,0)} + a_{(0,1)} \pmod{base}\\ \end{align} $$ Tenemos que $-1 \leq a_{(2,1)} -1 \lt base$ por lo que podemos escribir $a_{(0,0)}-1 \equiv a_{(0,0)}+a_{(0,1)} \pmod{base}$ . Entonces $$ -1 \equiv a_{(0,1)} \pmod{base} $$ Pero elegimos $c_{(2,1)}=a_{(0,1)}$ , por lo que tenemos $1 \equiv -1 \pmod{base}$ , lo cual es falso.

Caso $c_{(1,0)}=c_{(1,1)}=1$

Ya que, por la misma razón que antes, $\left( a_{(1,0)} \lt base-1 \land a_{(1,0)} \lt base-1 \right) \implies c_{(2,i)}=0$

$$ x_0=a_{(0,0)},a_{(0,1)},a_{(0,2)}\\ x_1=c_{(1,0)},a_{(1,0)},c_{(1,1)},a_{(1,1)}\\ x_2=a_{(2,0)},a_{(2,1)},a_{(2,2)} $$ donde $$ \begin{align} a_{(2,0)}&=c_{(1,0)}+a_{(1,0)}\\ a_{(2,1)}&=a_{(1,0)}+c_{(1,1)}\\ a_{(2,2)}&=c_{(1,1)}+a_{(1,1)} \end{align} $$

$c_{(1,0)}=c_{(1,1)}=1$ implica $a_{(0,0)}+a_{(0,1)} \geq base \land a_{(0,1)}+a_{(0,2)} \geq base $ . También, $a_{(2,0)}=a_{(2,1)}$ Esto significa que podemos tener un bucle $iff$ $a_{(0,0)}=a_{(0,1)}$ .

Elegimos $x_2=x_0$ Así que $a_{(2,i)}=a_{(0,i)}$ . $$ \begin{align} a_{(0,0)} = a_{(2,0)} &= c_{(1,0)}+\left(a_{(0,0)}+a_{(0,1)} \pmod{base}\right)\\ &= 1+\left(a_{(0,0)}+a_{(0,0)} \pmod{base}\right)\\ a_{(0,0)}-1 &= 2a_{(0,0)} \bmod{base}\\ \end{align} $$ lo mismo que antes, $$a_{(0,0)} \equiv -1 \pmod{base}$$ Para $a_{(0,2)}$ que tenemos: $$ \begin{align} a_{(0,2)}=a_{(2,2)}&=1+(a_{(0,1)}+a_{(0,2)}) \pmod{base}\\ a_{(0,2)}-1&=a_{(0,1)}+a_{(0,2)} \pmod{base} \end{align} $$

por la misma razón que antes,

$$ a_{(0,2)}-1 \equiv a_{(0,1)}+a_{(0,2)} \pmod{base} $$

$a_{(0,2)}$ borra, por lo que esto es válido para cada valor de $a_{(0,2)}$ . En base 10, esto significa que cada secuencia del tipo $99a$ bucles.

Caso $c_{(1,0)}=0 \land c_{(1,1)}=1$

En este caso, ya que $x_1$ es de 3 dígitos y todavía se mantiene $c_{(2,i)}=0$ por la misma razón que antes, seguimos cayendo en el caso de los 2 dígitos anteriores.

Más de 3 dígitos

Sin embargo, hay secuencias más largas que 3 que hacen un bucle, sin pasar por secuencias de bucle de 3 longitudes conocidas. Por ejemplo, en base 10, 8888 hace un bucle en 9 iteraciones. No encuentro la forma de generalizar esto a todas las longitudes.

Answer 2

Esto no es una respuesta, sino un intento de obtener alguna idea sobre el problema. Hice el código en Mathematica para generar una lista longitud $(t)$ , de tal manera que longitud $(t)$ es el número de iteraciones necesarias para que $t$ es menor que $10$ . Vale la pena señalar que el código considera divergencia si tarda más de 30 iteraciones en hacer $t$ más pequeño que $10$ (esto puede deberse a que las iteraciones están aumentando infinitamente, o están atascadas en algún ciclo, o la convergencia es simplemente demasiado lenta).

Después de esto, podemos hacer un gráfico con los puntos $(t,\ length(t))$ . En primer lugar, la parcela para $1\leq t\leq 1000$ .

Ahora la trama para $1\leq t\leq 10000$ .

Está claro que hay un patrón. Por ejemplo, podemos observar que en los casos de convergencia, normalmente el número de iteraciones es cercano a $10$ (la mayoría están entre $5$ y $20$ ). Además, este número parece aumentar muy lentamente. Estas observaciones pueden hacerse más precisas si se considera la evolución de los medios de $length(t)$ que se indican a continuación.

Se pueden hacer algunas otras observaciones a partir de estas parcelas. Espero que esto sea útil, en el sentido de que alguien pueda convertir alguna observación en un argumento matemático.

Answer 3

Esta es una respuesta al problema más fácil en base $2$ .

Se ve fácilmente que $0_{10}$ a través de $6_{10}$ y $8_{10}$ y $9_{10}$ convergen, pero $7_{10} = 111_2$ forma un ciclo de 2 con $10_{10} = 1010_2$ y $11_{10}$ a través de $15_{10}$ divergir.

Reclamación

Los valores iniciales convergentes se enumeran por: $$ \left\{ 0, 6, 2^n, 2^n+1 : n \in \mathbb{N}\right\}$$

Los valores de inicio de bucle se enumeran por: $$ \left\{ 7, 10 \right\} $$

Todos los demás valores de partida son divergentes.

Lema 1.1

Valores de la forma $2^n = 100\ldots0_2$ convergen.

Prueba

La cadena $1_2$ no puede reducirse más, y $$ 1 0\ldots\text{($ n $ times)}\ldots0 \to 1 0\ldots\text{($ n-1 $ times)}\ldots0 $$ por lo que se deduce por inducción.

Lema 1.2

Valores de la forma $2^n+1 = 100\ldots01_2$ convergen.

Prueba

$11 \to 10 \to 1$ y luego no se puede reducir más, y $$ 1 0\ldots\text{($ n $ times)}\ldots01 \to 1 0\ldots\text{($ n-1 $ times)}\ldots01 $$ por lo que se deduce por inducción.

Lema 2.1

Si la expansión binaria incluye la subcadena $111a$ (es decir, la subcadena $111$ no está al final de la cadena), el proceso se desviará.

Prueba

$$ \begin{aligned} & \ldots 111a \ldots & \\ \to & & \text{step} \\ & \ldots 1010(1 + a) \ldots &\\ \to & & (1 + a) \text{ starts with $1$ whatever $a$ is} \\ & \ldots 10101 \ldots & \\ \to & & \text{step} \\ & \ldots 1111 \ldots & \\ \to & & \text{step} \\ & \ldots 101010 \ldots & \\ \to & & \text{step} \\ & \ldots 11111 \ldots & \\ \to & & \text{step} \\ & \ldots 10101010 \ldots & \\ \to & & \text{step} \\ & \ldots 1111111 \ldots & \\ \end{aligned} $$ Ahora, una subcadena de $1 \ldots \text{($ n $ times)} \ldots 1$ se convierte en una subcadena de $10 \ldots \text{($ n-1 $ times)} \ldots 10$ se convierte en una subcadena de $1 \ldots \text{($ 2n-3 $ times)} \ldots 1$ y $2n - 3 > n$ cuando $n > 3$ por lo que el proceso divergirá con una subcadena de longitud creciente.

Lema 2.2

Si la expansión binaria termina en la subcadena $0111$ el proceso será divergente.

Prueba

$\ldots 0111 \to \ldots 11010 \to \ldots 10111 \to \ldots 111010$ y el resultado se deduce por el lema 2.1.

Lema 2.3

Si la expansión binaria incluye (pero no es igual) la subcadena $1010$ el proceso será divergente.

Prueba

$\ldots 1010 \ldots \to \ldots 111 \ldots$ y el resultado se deduce por los lemas 2.1 y 2.2.

Lema 3

Si la expansión binaria contiene $3$ $1$ s, posiblemente separados por $0$ s, el proceso diverge (o hace un bucle para el valor inicial $7$ ).

Prueba

Para el caso de que no haya separación $0$ s, véanse los lemas 2.1 y 2.2. Los demás casos se resuelven con el lema 2.3:

$\ldots10^{n+1}11\ldots \to \ldots10^n1010\ldots$ que contiene $1010$ .

$\ldots110^{n+1}1\ldots \to \ldots1010^n1\ldots$ o bien contiene $1010$ o cuando $n = 0$ es igual a $1011$ que acaba de ser tratada.

$\ldots10^{m+1}10^{n+1}1\ldots \to \ldots10^m110^n1\ldots$ contiene $111$ cuando $m = 0$ o $n = 0$ . Cuando $m > 0$ contiene $10^{(m-1)+1}11$ y cuando $n > 0$ contiene $110^{(n-1)+1}1$ , que acaban de ser tratadas.

Lema 4

Si la expansión binaria contiene $010$ entonces el proceso diverge.

Prueba

Debe haber un líder adicional $1$ (como líder $0$ nunca se generan, ni están presentes en el valor inicial) por lo que $1\dots 010 \ldots \to 1\ldots 11 \ldots$ que contiene 3 $1$ s por lo que es divergente por el lema 3.

Prueba de la reclamación

El valor inicial es 0, o tiene al menos un $1$ en su expansión binaria. Si tiene exactamente una $1$ entonces es de la forma $2^n$ que se demuestra que converge por el Lemma 1.1. Si tiene exactamente dos $1$ entonces el no líder $1$ está al final, en cuyo caso es de la forma $2^n+1$ que se demuestra que converge por el Lemma 1.2, o bien el $1$ forma una subcadena $010$ * que se demuestra que es divergente por el Lemma 4 (* aparte del único caso especial $6_{10}=110_2$ ). Si hay tres o más $1$ diverge por el lema 3.