How do I know if this algorithm converges?

Question

This is an algorithm developed as a joke which has led me to a problem I can't solve.

Being $,$ the concatenation operator, given $$x_0 = a_{(0,0)},a_{(0,1)},a_{(0,2)},\dots,a_{(0,n)}$$ we define $$x_{i+1}=(a_{(i,0)}+a_{(i,1)}),(a_{(i,1)}+a_{(i,2)}),\dots,(a_{(i,n-1)}+a_{(i,n)})$$

For example: $$ \begin{split} 1234\\ 357\\ 812\\ 93\\ 12\\ 3 \end{split} $$

Now, this does not always converge, but I can't understand why in general. E.g., in base 10, $99a$ loops, $8888$ loops...

I'm trying to develop a function that, given a number, outputs if the algorithm converges (without checking all the history for loops).

Here a jar I made which computes the algorithm given a starting number.

Here the same question on Quora, with some other useful insights.

Answer 1

These are my results:

1 digit numbers

1 digit numbers are our base case.

2 digit numbers

2 digit numbers always converge.

Being $,$ the concatenation operator, for 2 digits numbers, we define $x_0=a_{(0,0)},a_{(0,1)}$. So: $$x_1=c_{(1,0)},a_{(1,0)}$$ where $$a_{(1,0)}=a_{(0,0)}+a_{(0,1)} \pmod{base}$$ Where $c_{(i,j)}$ is the carry digit of the $j^{th}$ operation at the $i^{th}$ iteration, which we will suppose to be one (otherwise it would be trivial). So, since $$ x_2=c_{(2,0)},(c_{(1,0)}+a_{(1,0)} \bmod{base}) $$ and, since $$ \begin{align} a_{(0,0)} + a_{(0,1)} & \geq base \\ a_{(0,0)} & \leq base-1 \\ a_{(0,1)} & \leq base-1 \\ 0 \leq a_{(0,0)} + a_{(0,1)} & \leq 2 \cdot base-2 \\ 0 \leq a_{(0,0)} + a_{(0,1)} & \leq base-2 \mod{base}\\ 0 \leq a_{(1,0)} & \leq base-2 \mod{base}\\ \end{align} $$ implies that $$ c_{(2,0)}=\emptyset $$ so, $$ x_2=a_{(2,0)} $$ which is a 1 digit number, which is the base case.

3 digit numbers

3 digit numbers like $$ x_0=a_{(0,0)},a_{(0,1)},a_{(0,2)}\\ $$ have $$ x_1=c_{(1,0)},a_{(1,0)},c_{(1,1)},a_{(1,1)}\\ $$

Case $\{c_{(1,0)}=\emptyset,c_{(1,1)}=\emptyset\}$

Trivial, 2 digit case.

Case $\{c_{(1,0)}=\emptyset,c_{(1,1)}=1\}$

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

$$ \begin{align} a_{(0,0)} + a_{(0,1)} & \lt base \\ a_{(0,1)} + a_{(0,2)} & \geq base \\ 0 \leq a_{(0,0)} & \leq base-2 \\ 1 \leq a_{(0,1)} & \leq base-1 \\ 1 \leq a_{(0,2)} & \leq base-1 \\ 1 \leq a_{(1,0)} & \leq base-1 \\ 0 \leq a_{(1,1)} & \leq base-2 \\ \end{align} $$

$x_2$ is either trivial, or $$ x_2 = c_{(2,0)},a_{(2,0)},a_{(2,1)}\\ $$ with $a_{(2,0)}=0$, which means $x_3$ is trivial.

Case $\{c_{(1,0)}=1,c_{(1,1)}=\emptyset\}$

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

$$ \begin{align} a_{(0,0)} + a_{(0,1)} & \geq base \\ a_{(0,1)} + a_{(0,2)} & \lt base \\ 1 \leq a_{(0,0)} & \leq base-1 \\ 1 \leq a_{(0,1)} & \leq base-1 \\ 0 \leq a_{(0,2)} & \leq base-2 \\ 0 \leq a_{(1,0)} & \leq base-2 \\ 1 \leq a_{(1,1)} & \leq base-1 \\ \end{align} $$

$x_2$ is either trivial, or $$ x_2 = a_{(2,0)},c_{(2,0)},a_{(2,1)}\\ $$

same as the case above.

Case $\{c_{(1,0)}=1,c_{(1,1)}=1\}$

$$ \begin{align} 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)} \end{align} $$

These conditions apply: $$ c_{(1,0)}=c_{(1,1)}=1 \implies a_{(2,0)} = a_{(2,1)}\\ $$

$$ \begin{align} 0 \leq a_{2,\{0,1,2\}} & \leq base-1\\ a_{(0,0)} + a_{(0,1)} & \geq base \\ a_{(0,1)} + a_{(0,2)} & \geq base \\ 1 \leq a_{(0,i)} & \leq base-1 \\ 0 \leq a_{(1,i)} & \leq base-2 \end{align} $$

$$ a_{(2,2)} = c_{(1,1)} + a_{(1,1)} = 1 + (a_{(0,1)} + a_{(0,2)} \pmod{base}) $$

Consider that if $$ a_{(1,0)}=base-2 \iff a_{(0,0)} = a_{(0,1)} = base-1 \\ $$

it follows that:

$$ \begin{align} a_{(1,0)}=base-2 & \implies a_{(2,2)} = 1 + base - 1 + a_{(0,2)} \pmod{base} = a_{(0,2)}\\ & \implies a_{(2,2)} = a_{(0,2)} \forall a_{(0,2)} \in \{1,base-1\} \\ & \implies a_{(2,0)} = a_{(2,1)} = a_{(0,0)} = a_{(0,1)} = base-1 \end{align} $$

In other words, for $a_{(0,0)}=a_{(0,1)}$ and $a_{(0,2)} \geq 1$ it loops with period 2.

Otherwise, it either maps to one of the cases above, or repeats this case, but since $$ \begin{align} a_{(1,0)} \neq base-2 & \implies a_{(1,0)} \lt base-2 \\ a_{(1,0)} \lt base-2 & \implies a_{(1,0)} \leq base-3 \\ & \implies a_{(0,0)} + a_{(0,1)} \leq base - 1 + base - 1 - 1 \pmod{base}\\ & \implies a_{(0,0)} + a_{(0,1)} \leq base-3 \end{align} $$ the upper bound shrinks and the series converges.

$\gt 2$ digit numbers

Bigger numbers can show loops of larger sizes, like $8888$.

Answer 2

This is not an answer, but an attempt to get some insight about the problem. I made the code in Mathematica to generate a list length$(t)$, such that length$(t)$ is the number of iterations necessary to make $t$ gets smaller than $10$. It's worth to point out that the code considers divergence if it takes more than 30 iterations to make $t$ smaller than $10$ (this can be because the iterations are increasing infinitely, or they are stuck in some cycle, or the convergence is just too slow).

After this, we can make a plot whit the points $(t,\ length(t))$. First the plot for $1\leq t\leq 1000$.

Now the plot for $1\leq t\leq 10000$.

Clearly there is a pattern. For instance, we can note that in the cases of convergence, usually the number of iterations is close to $10$ (most are between $5$ and $20$). Also, this number seems to be increasing really slow. These observations can be made more precise by considering the evolution of the means of $length(t)$, given below.

Some other observations can be made from this plots. I hope this will be helpful, in the sense someone can turn some observation in a mathematical argument.

Answer 3

This is an answer to the easier problem in base $2$.

It is readily seen that $0_{10}$ through $6_{10}$ and $8_{10}$ and $9_{10}$ converge, but $7_{10} = 111_2$ forms a 2-cycle with $10_{10} = 1010_2$, and $11_{10}$ through $15_{10}$ diverge.

Claim

Converging start values are enumerated by: $$ \left\{ 0, 6, 2^n, 2^n+1 : n \in \mathbb{N}\right\}$$

Looping start values are enumerated by: $$ \left\{ 7, 10 \right\} $$

All other start values diverge.

Lemma 1.1

Values of the form $2^n = 100\ldots0_2$ converge.

Proof

The string $1_2$ cannot be reduced further, and $$ 1 0\ldots\text{($n$ times)}\ldots0 \to 1 0\ldots\text{($n-1$ times)}\ldots0 $$ so it follows by induction.

Lemma 1.2

Values of the form $2^n+1 = 100\ldots01_2$ converge.

Proof

$11 \to 10 \to 1$ and then cannot be reduced further, and $$ 1 0\ldots\text{($n$ times)}\ldots01 \to 1 0\ldots\text{($n-1$ times)}\ldots01 $$ so it follows by induction.

Lemma 2.1

If the binary expansion includes the substring $111a$ (ie, the substring $111$ is not at the end of the string), the process will diverge.

Proof

$$ \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} $$ Now, a substring of $1 \ldots \text{($n$ times)} \ldots 1$ becomes a substring of $10 \ldots \text{($n-1$ times)} \ldots 10$ becomes a substring of $1 \ldots \text{($2n-3$ times)} \ldots 1$, and $2n - 3 > n$ when $n > 3$, so the process will diverge with an ever-increasing-length substring.

Lemma 2.2

If the binary expansion ends in the substring $0111$, the process will diverge.

Proof

$\ldots 0111 \to \ldots 11010 \to \ldots 10111 \to \ldots 111010$ and the result follows by Lemma 2.1.

Lemma 2.3

If the binary expansion includes (but is not equal to) the substring $1010$ the process will diverge.

Proof

$\ldots 1010 \ldots \to \ldots 111 \ldots$ and the result follows by Lemmas 2.1 and 2.2.

Lemma 3

If the binary expansion contains $3$ $1$s, possibly separated by $0$s, the process diverges (or loops for the start value $7$).

Proof

For the case without any separating $0$s, see Lemmas 2.1 and 2.2. The remaining cases are resolved by Lemma 2.3:

$\ldots10^{n+1}11\ldots \to \ldots10^n1010\ldots$ which contains $1010$.

$\ldots110^{n+1}1\ldots \to \ldots1010^n1\ldots$ either contains $1010$, or when $n = 0$ it is equal to $1011$ which has just been dealt with.

$\ldots10^{m+1}10^{n+1}1\ldots \to \ldots10^m110^n1\ldots$ contains $111$ when $m = 0$ or $n = 0$. When $m > 0$ it contains $10^{(m-1)+1}11$, and when $n > 0$ it contains $110^{(n-1)+1}1$, both of which have just been dealt with.

Lemma 4

If the binary expansion contains $010$ then the process diverges.

Proof

There must be an additional leading $1$ (as leading $0$s are never generated, nor present in the start value) so $1\dots 010 \ldots \to 1\ldots 11 \ldots$, which contains 3 $1$s so diverges by Lemma 3.

Proof of the claim

The starting value is either 0, or has at least one $1$ in its binary expansion. If it has exactly one $1$ then it is of the form $2^n$ which is shown to converge by Lemma 1.1. If it has exactly two $1$ then either the non-leading $1$ is at the end, in which case it is of the form $2^n+1$ which is shown to converge by Lemma 1.2, or else the non-leading $1$ forms a substring $010$ * which is shown to diverge by Lemma 4 (* apart from the unique special case $6_{10}=110_2$). If there are three or more $1$, it diverges by Lemma 3.