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

Question

I have 8 numbers in an array: the numbers are either 1 or 0 and are initially random.

example: [0,1,0,1,1,0,0,1]

every cycle, the array changes as follows:

• If a cell has two adjacent values that are both equal, then the value becomes 1.

• Otherwise it becomes 0.

Example after 1 iteration:

[0, 1, 1, 0, 0, 0, 0, 0]

after 2:

[0, 0, 0, 0, 1, 1, 1, 0]

etc...

I simulated different starting conditions, and the cycle always repeats within 14 cycles. My intuition says it should repeat after 256 cycles (2^ArrayLength) or maybe even 64 (2^6 since the two edges will always be 0 after the first iteration).

I have a feeling it has to do with how the 2nd value and the 7th value in the array are really only dependent on the 3rd and 6th value, since the other two next to these indexes never change after iteration 1, but I can't figure it out.

Could anyone explain to me why this is 14?

Answer 1

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.

Answer 2

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.