Why does this pattern repeat after 14 cycles instead of 256, can you give a proof?

The main reason is that the values of the 1st, 3rd, 5th and 7th number in your array before an iteration completely determine the values of the 2nd, 4th, 6th and 8th number after the iteration. Similiarly, the valuse of the 2nd, 4th, 6th and 8th number before an iteration completely determine the values of the 1st, 3rd, 5th and 7th number after the iteration.

To see this, take as example the 5th number (odd). After an iteration its value will depend only on the before-iteration value of the 4th and 6th number (even).

As you correctly noted, after one iteration the 1st and 8th number are $0$ and stay that way. So after one iteration, your array looks like

$$0x?y?z?0.$$

After one more iteration the values of $x,y$ and $z$ (2nd, 4th and 6th array element) completely determine the non-$?$ values given here ($r,s$ and $t$):

$$0?r?s?t0.$$

After one more iteration, those values ($r,s$ and $t$) determine again the new (2nd, 4th and 6th array element):

$$0x'?y'?z'?0.$$

That means the original $x,y$ and $z$ values, determine, after 2 iterations completely the values of $x',y'$ and $z'$.

The same can be said of course for the remaining 3 values (above shown as $?$,).

So from your original 8-bit data set, 2 bits immediately become and stay $0$, and then 2 sets of 3 bits of data remain that, after 2 iterations, determine the "next" value of the exact same 3 bits of data.

So those 2 sets of 3 bit data have a maximal cycle length of 8. Because we need two of our iterations for one step in the 3-bit cycle, that makes a maximal iteration count of 16.

Now to get to your 14 iterations, what's needed is to actually write down those cycles of the 3bit data. It turns out that it's one cycle of 7 steps and one 1 cyle of 1 step.

You get the 1 step cycle if you start with

$$00?0?1?0,$$

then the next iteration will be

$$0?1?0?00$$

and the next one will be (again)

$$00?0?1?0.$$

If you start with any other configuration, you will find the 7-step cycle. As 1 step is two iterations, this explains your max 14 iterations.


As you observe, the first and last bit will always be 0 after the first iteration. A second key observation is that, the even bits only affect the odd bits in the next round, and vice versa, so every 2 rounds, the even bits determine themselves and the odd bits determine themselves. Let us find a formula for how things evolve after the first iteration.

Let $x_n(i)$ denote the $i$th bit at time $n$. Then modulo $2$, we have $x_{n+1}(i)=x_n(i-1)+x_n(i+1)+1$ if $1< i< 8$ and we define $x_n(i)=0$ if $i<2$ or $i>7$. From this, we have $$x_{n+2}(i)=1+(x_{n}(i-2)+x_{n}(i)+1)+(x_{n}(i)+x_{n}(i+2)+1)=1+x_n(i+2)+x_n(i-2)$$ assuming $3\leq i \leq 6$.

We also have that $x_{n+2}(2)=1+x_{n+1}(3)=x_n(2)+x_n(4)$ and similarly $x_{n+2}(7)=x_n(7)+x_n(5)$. But essentially, the even bits and the odd bits are following the same pattern, and understanding one allows us to understand the other. If we can find the length of cycles of the even bits going 2 time steps at a time, we can do the same for the odd bits, and that information can be used to find possible cycle lengths going one step at a time.

Since $x_n(8)=0$, the even bits are determined by $x(2), x(4)$, and $x(6)$, and since we only have 8 possible combinations, a cycle must be of length at most 8.

Working mod 2, we see that map going two time periods is afine (linear plus a constant). For the even indices, if we let

$$A=\begin{pmatrix}1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1\end{pmatrix}$$

and set $v_n = (x_n(2), x_n(4),x_n(6), 1)^T)$, $v_{n+1}=Av_n$. Computing powers of $A$, we see that $A^7=I$, so every cycle has length dividing $7$, namely $1$ or $7$. We have that $v=(0,0,1,1)^T$ gives a cycle of length 1, and so everything else must be in a cycle of length 7.

Exactly the same thing happens for the odd indices. A little bit of extra work then shows that we either have a cycle of length 2 or a cycle of length 14 in our original problem.