Aquí hay otra manera de estudiar estos procesos. En la secuela $k=3$ pero está claro cómo generalizar.
La idea es buscar en las matrices formadas por tres triples consecutivos utilizados en el proceso de inserción.
Para ello escribimos los triples producido por el proceso en un infinito matriz $S$ con $3$ columnas (indexados por 0,1,2), y las filas
indizada $1,2,,\ldots$.
El $i$-ésima fila de $S$ consiste en el triple (en orden) que las sumas a $x_i$.
De modo que la parte superior de $S$ es
\begin{align*}
\begin{matrix}
c0&c1&c2&\;\;x\\
1&2&3&\;\;6\\
4&5&6&\;\;15\\
6&7&8&\;\;21\\
9&10&11&\;\;30\\
12&13&14&\;\;39\\
\ldots
\end{de la matriz}\end{align*}
Dejamos $M(n)$ ser $3\times 3$ submatriz de $S$ que consta de filas $3n-1,3n,3n+1$ de $S$,
y deje $T_0(n),T_1(n),T_2(n)$ ser $3 \times 3$matrices
\begin{align*}
T_0(n):=\begin{pmatrix}
8n-4 & 8n-3 & 8n-2\\
8n-2 & 8n-1 & 8n\\
8n+1 & 8n+2 & 8n+3\\
\end{pmatrix},\;\;
T_2(n):=\begin{pmatrix}
8n-4 & 8n-3 & 8n-3\\
8n-2 & 8n-1 & 8n\\
8n+1 & 8n+2 & 8n+3\\
\end{pmatrix}\,\;\end{align*}
\begin{align*}
T_1(n):=\begin{pmatrix}
8n-4 & 8n-3 & 8n-2\\
8n-1 & 8n-1 & 8n\\
8n+1 & 8n+2 & 8n+3\\
\end{pmatrix}\;\;.
\end{align*}
Nuestro objetivo es mostrar que:
Lema: para todos los $n$ $$M(n)\in\{T_0(n),T_1(n),T_2(n)\}$$
Auxiliar consideraciones:
(1) la Inserción de $x_n$.
$x_n$ se inserta después de la primera aparición de su valor. Desde $n-1+x_n$ elementos de $S$ son menores o iguales que $x_n$
$x_n$ se inserta en la fila $\lceil{n+x_n \over 3}\rceil$ y en la columna $(n+x_n-1)\bmod 3$.
(2) la Sucesión de las reglas. Suponga que $M(j)=T_i(n)$. Donde se la produjo $x$s ser insertado?
Aplicación de la inserción de la regla da:
para $i=0$ :
$x_{3j-1}$ va a la fila $8n-3+j$ , colummn $1$.
$x_{3j}$ va a la fila $8n-1+j$ , colummn $2$.
$x_{3j+1}$ va a la fila $8n+3+j$ , colummn $0$.
para $i=1$
$x_{3j-1}$ va a la fila $8n-3+j$ , colummn $1$.
$x_{3j}$ va a la fila $8n-1+j$ , colummn $0$.
$x_{3j+1}$ va a la fila $8n+3+j$ , colummn $0$.
para $i=2$
$x_{3j-1}$ va a la fila $8n-3+j$ , colummn $0$.
$x_{3j}$ va a la fila $8n-1+j$ , colummn $2$.
$x_{3j+1}$ va a la fila $8n+3+j$ , colummn $0$.
En otras palabras: si $S(j)$ es de tipo $T_0$ genera un tipo de secuencia $120$ más tarde, escriba $T_1$ genera $100$, el tipo de $T_2$ genera $020$.
.
La prueba del lema:(croquis) comparación muestra que $M(1)=T_0(1)$. Reiterado uso de las reglas de la sucesión
ahora demuestra que la $(M(2),M(3),M(4))=(T_1(2),T_2(3),T_0(4))$, el siguiente bloque de nueve matrices tiene
los índices de $100, 020, 120$, y, en general, los índices de un $3^{k+1}$ bloque son generados por la sustitución de
$120$ para $0$, $100$ para $1$ e e $020$ para $2$ en la anterior $3^k$ bloque. Final de la prueba.
Algunos corolarios:
(1) para todo n $$x_n\in \{8n-1,8n-2,8n-3\}$$
Por lo tanto $$1+\lfloor{n+x_n \over 3}\rfloor=3n\;\;.$$
(2) la fila $3n+1$ es $8n+1,8n+2,8n+3$ e $x_{3n+1}=24n+6$
Pregunta abierta: tiene la replicación de la secuencia por encima de una simple ternario descripción?
AÑADIDO: el caso general.
Ligeramente la reformulación, se encuentra por encima de la de $k=3$:
(1) el comportamiento de $(x_n)$ se rige por el tipo de secuencia $(t_n)$, $x_n=8n-2$ si $t_n=0$, $x_n=8n-1$ si $t_n=1$, e $x_n=8n-3$ si $t_n=2$
(en la descripción anterior $t_n$ puede ser visualizado como el índice de columna de $x_n$)
(2) la secuencia de $(t_n)$ es el punto fijo de partida de $0$ de la $3$-uniforme de morfismos $\phi$ de la libre monoid $\{0,1,2\}^*$
dado por $0\rightarrow 012,\;1\rightarrow 010,\;2\rightarrow 002$
El caso general puede ser tratada de la misma manera, dando:
(1) el comportamiento de $(x_n)$ se rige por su tipo de secuencia $(t_n)$.
en el caso de $k$ es impar:
$t_n\in\{-\tfrac{(k-1)}{2},\ldots,\tfrac{k-1}{2}\}$ (los representantes de los residuos de $\bmod \,k$ en $\{-\tfrac{(k-1)}{2},\ldots, \tfrac{k-1}{2}\}$)
y para todos los $n$
$$x_n=(k^2-1)n-\tfrac{k(k-1)}{2} + 1 +t_n$$
(2a) deje $b(0)=(0,1,2\ldots,k-1)$. Para $p=1,..,\tfrac{k-1}{2}$ construcción de la palabra $b(p)$ de $b(0)$ mediante la adición de $p$ ($\bmod\,k$) para el valor de $\tfrac{k+1}{2}$ (dejando el resto sin cambios). Para $p=-\tfrac{(k-1)}{2},\ldots,-1$
construcción de la palabra $b(p)$ mediante la adición de $p$ ($\bmod k$) para el valor de ${k-1 \over 2}$ (dejando el resto sin cambios).
A continuación, la secuencia $(t_n)$ (con representantes de la $0,1,\ldots,k-1$ $\bmod k$) es el punto fijo de partida de $0$ de la $k$-uniforme de morfismos $\phi$ de la libre monoid $\{0,1,\ldots,k-1\}^*$
dado por $p\rightarrow b(p)$.
en el caso de $k$ incluso:
$t_n\in\{1,\ldots,k-1\}$ (es decir, $t_n=0$ no suceda), y para todos los $n$
$$x_n=(k^2-1)n-\tfrac{k^2}{2} + 1 +t_n$$
(2b)
para $p\in \{0,\ldots k-1\}$ deje $b(p)= (\tfrac{k}{2},\tfrac{k}{2}+1,\ldots k-1,p,1\ldots,\tfrac{k}{2}-1)$ (con $p$ en la posición $\tfrac{k}{2}+1$).
A continuación, la secuencia $(t_n)$ es el punto fijo de partida de $\tfrac{k}{2}$ de la $k$-uniforme de morfismos $\phi$ de la libre monoid $\{0,1,\ldots,k-1\}^*$
dado por $p\rightarrow b(p)$.
Por Cobham del teorema ("una secuencia que surjan como (imagen bajo una codificación) de un punto fijo de un $k$-uniforme de morfismos es $k$-automático") la secuencia de $(t_n)$ es, por tanto, $k$-automático.
Por el cierre de las propiedades del conjunto de $k-$automática de secuencias (en turnos, en paralelo generación y tomar las funciones de los elementos de salida), a continuación, también la secuencia de $(\Delta_n)$ con
$$\Delta_n=(k^2-1)+t_{n+1}-t_n=x_{n+1}-x_n$$
es $k$-automático. (Es decir, $\Delta_n$ puede ser calculada a partir de la base-$k$
dígitos de $n$ con una máquina de estados finitos del tipo desribed que la anterior).
