Flipping odd number array by two numbers in series.

Question

Suppose an array of length $n$(odd number) which is composed with only $0$.

We start to ‘flip’( or ‘change’) numbers with following rules.

1. [1, 1] → [0, 0]
2. [0, 0] → [1, 1]
3. [1, 0] or [0, 1] : do not change.
4. Change elements sequentially and rotationally(when you reach at the end of the array), and repeat until the array becomes its initial state.

For example, if the length of the array is 3,

0   [0 0 0] #start
1   [1 1 0] #first and second element is [0, 0], by rule 2, it became [1, 1]
2   [1 1 0] #third and first element = [0, 1], by rule 3, just pass.
3   [1 1 0] #second and third = [1, 0], pass
4   [0 0 0] #first and second = [1, 1], by rule 1, change it to [0, 0].

After 4 steps, the array repeats its configuration, so, the period is $4$.

Another example, $n = 5$

0   [0 0 0 0 0]
1   [1 1 0 0 0]
2   [1 1 1 1 0]
3   [1 1 1 1 0]
4   [1 0 0 1 0]
5   [1 0 0 1 0]
6   [1 0 0 1 0]
7   [1 0 0 1 0]
8   [1 0 0 1 0]
9   [1 1 1 1 0]
10  [1 1 1 1 0]
11  [0 0 1 1 0]
12  [0 0 0 0 0]

The period is $12$.

And when $n=7$,

0   [0 0 0 0 0 0 0]
1   [1 1 0 0 0 0 0]
2   [1 1 1 1 0 0 0]
3   [1 1 1 1 1 1 0]
4   [1 1 1 1 1 1 0]
5   [1 0 0 1 1 1 0]
6   [1 0 0 0 0 1 0]
7   [1 0 0 0 0 1 0]
8   [1 0 0 0 0 1 0]
9   [1 0 1 1 0 1 0]
10  [1 0 1 1 0 1 0]
11  [1 0 1 1 0 1 0]
12  [1 0 1 1 0 1 0]
13  [1 0 1 1 0 1 0]
14  [1 0 1 1 0 1 0]
15  [1 0 1 1 0 1 0]
16  [1 0 0 0 0 1 0]
17  [1 0 0 0 0 1 0]
18  [1 0 0 0 0 1 0]
19  [1 1 1 0 0 1 0]
20  [1 1 1 1 1 1 0]
21  [1 1 1 1 1 1 0]
22  [0 0 1 1 1 1 0]
23  [0 0 0 0 1 1 0]
24  [0 0 0 0 0 0 0]

The period is $24$.

It looks like the series of periods follows A046092 (0, 4, 12, 24, 40, 60, 84, 112, 144, 180, 220, 264,… )

How can I prove this?

(If you want to look into more longer cases, refer here )

(Any modification of my English will be appreciated. English is not my mother tongue.)

Answer 1

This question is quite old, but as there is no answer yet, I decided to answer it.

Lets split or steps in groups of size $n$, so that after each "batch", the cursor is back at the beginning of the list. This batch is equivalent at the following operations:

• For each pair (even-odd), if they are equal, flip them. ($\frac{n-1}{2}$ steps)
• For each pair (odd-even), if they are equal, flip them. ($\frac{n+1}{2}$ steps)

As the last element of the list is always a zero bordered by ones, it can be safely ignored.

So applying these operations in order, one gets the following pattern:

 0 : 000000000
 4 : 111111110
 9 : 100000010
13 : 101111010
18 : 101001010

At each step, there is a clump of same value element, surrounded by alternating elements. Each step, the clump flips its value, leaving the two outermost values the same, growing the alternating area. This goes on until the middle cannot be swapped anymore, and the last step will be a no-op. Then, because of the reversibility of the described operations, it will reverse the effects and end back at the original state:

22 : 101001010
27 : 101111010
31 : 100000010
36 : 111111110
40 : 000000000

Because of this, the operation will reach its initial state after $n$ such operations, or $n\frac{n-1}{2}+\frac{n-1}{2}=\frac{(n-1)(n+1)}{2}$ original operations. The odds terms of this formula match the given sequence in the question.