Here is another way of studying these processes. In the sequel $k=3$ but it is clear how to generalize.

The idea is to look at the matrices formed by three consecutive triples used in the insertion process.
To this end we write the triples produced by the process into an infinite matrix $S$ with $3$ columns (indexed by 0,1,2), and rows
indexed $1,2,,\ldots$.
The $i$-th row of $S$ consists of the triple (in order) which sums to $x_i$.

So the top of $S$ is

\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{matrix}\end{align*}

We let $M(n)$ be the $3\times 3$ submatrix of $S$ which consists of the rows $3n-1,3n,3n+1$ of $S$,
and let $T_0(n),T_1(n),T_2(n)$ be the $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*}

Our aim is to show:

**Lemma**: for all $n$ $$M(n)\in\{T_0(n),T_1(n),T_2(n)\}$$

Auxiliary considerations:

(1) Insertion of $x_n$.
$x_n$ is inserted after the first appearance of its value. Since $n-1+x_n$ elements of $S$ are less or equal than $x_n$
$x_n$ will be inserted in row $\lceil{n+x_n \over 3}\rceil$ and in column $(n+x_n-1)\bmod 3$.

(2) Succession rules. Assume that $M(j)=T_i(n)$. Where will the produced $x$s be inserted?
Application of the insertion rule gives:

for $i=0$ :

$x_{3j-1}$ goes to row $8n-3+j$ , colummn $1$.
$x_{3j}$ goes to row $8n-1+j$ , colummn $2$.

$x_{3j+1}$ goes to row $8n+3+j$ , colummn $0$.

for $i=1$

$x_{3j-1}$ goes to row $8n-3+j$ , colummn $1$.
$x_{3j}$ goes to row $8n-1+j$ , colummn $0$.
$x_{3j+1}$ goes to row $8n+3+j$ , colummn $0$.

for $i=2$

$x_{3j-1}$ goes to row $8n-3+j$ , colummn $0$.
$x_{3j}$ goes to row $8n-1+j$ , colummn $2$.
$x_{3j+1}$ goes to row $8n+3+j$ , colummn $0$.

In other words: if $S(j)$ is of type $T_0$ it generates a type sequence $120$ later, type $T_1$ generates $100$, type $T_2$ generates $020$.
.

**Proof** of the lemma:(sketch) comparison shows that $M(1)=T_0(1)$. Iterated use of the succession rules
now shows that $(M(2),M(3),M(4))=(T_1(2),T_2(3),T_0(4))$, the next block of nine matrices has
indices $100, 020, 120$, and in general the indices of a following $3^{k+1}$ block are generated by substituting
$120$ for $0$, $100$ for $1$ and and $020$ for $2$ in the previous $3^k$ block. **End** of proof.

Some corollaries:

(1) for all n $$x_n\in \{8n-1,8n-2,8n-3\}$$
Thus $$1+\lfloor{n+x_n \over 3}\rfloor=3n\;\;.$$

(2) the row $3n+1$ is $8n+1,8n+2,8n+3$ and $x_{3n+1}=24n+6$

Open question: has the replicative sequence above a simple ternary description?

ADDED: the general case.

Slightly reformulating, we found above for $k=3$:

(1) the behaviour of $(x_n)$ is governed by the type sequence $(t_n)$, $x_n=8n-2$ if $t_n=0$, $x_n=8n-1$ if $t_n=1$, and $x_n=8n-3$ if $t_n=2$
(in the description above $t_n$ can be visualized as the column index of $x_n$)

(2) the sequence $(t_n)$ is the fixed point starting from $0$ of the $3$-uniform morphism $\phi$ of the free monoid $\{0,1,2\}^*$
given by $0\rightarrow 012,\;1\rightarrow 010,\;2\rightarrow 002$

The general case can be treated in the same way, giving:

(1) the behaviour of $(x_n)$ is governed by its type sequence $(t_n)$.

in case $k$ is odd:

$t_n\in\{-\tfrac{(k-1)}{2},\ldots,\tfrac{k-1}{2}\}$ (the representatives of the residues $\bmod \,k$ in $\{-\tfrac{(k-1)}{2},\ldots, \tfrac{k-1}{2}\}$)
and for all $n$
$$x_n=(k^2-1)n-\tfrac{k(k-1)}{2} + 1 +t_n$$

(2a) let $b(0)=(0,1,2\ldots,k-1)$. For $p=1,..,\tfrac{k-1}{2}$ construct the word $b(p)$ from $b(0)$ by adding $p$ ($\bmod\,k$) to the value $\tfrac{k+1}{2}$ (leaving the rest unchanged). For $p=-\tfrac{(k-1)}{2},\ldots,-1$
construct the word $b(p)$ by adding $p$ ($\bmod k$) to the value ${k-1 \over 2}$ (leaving the rest unchanged).

Then the sequence $(t_n)$ (with representatives $0,1,\ldots,k-1$ $\bmod k$) is the fixed point starting from $0$ of the $k$-uniform morphism $\phi$ of the free monoid $\{0,1,\ldots,k-1\}^*$
given by $p\rightarrow b(p)$.

in case $k$ is even:

$t_n\in\{1,\ldots,k-1\}$ (i.e. $t_n=0$ does not happen), and for all $n$

$$x_n=(k^2-1)n-\tfrac{k^2}{2} + 1 +t_n$$

(2b)
for $p\in \{0,\ldots k-1\}$ let $b(p)= (\tfrac{k}{2},\tfrac{k}{2}+1,\ldots k-1,p,1\ldots,\tfrac{k}{2}-1)$ (with $p$ at position $\tfrac{k}{2}+1$).

Then the sequence $(t_n)$ is the fixed point starting from $\tfrac{k}{2}$ of the $k$-uniform morphism $\phi$ of the free monoid $\{0,1,\ldots,k-1\}^*$
given by $p\rightarrow b(p)$.

By Cobham's theorem ("a sequence arising as (image under a coding of) a fixed point of a $k$-uniform morphism is $k$-automatic") the sequence $(t_n)$ is therefore $k$-automatic.

By the closure properties of the set of $k-$automatic sequences (under shifts, parallel generation and taking functions of output elements) then also the sequence $(\Delta_n)$ with
$$\Delta_n=(k^2-1)+t_{n+1}-t_n=x_{n+1}-x_n$$
is $k$-automatic. (That is, $\Delta_n$ can be computed from the base-$k$
digits of $n$ with a finite state machine of the type desribed above.)

Seconddifferences might be simpler... $\endgroup$ – მამუკა ჯიბლაძე Oct 16 '18 at 5:403more comments