Firstly, let's brute force some small numbers. So, we have $$$ans(3)=4,ans(5)=16,ans(7)=8$$$. The first obvious conclusion is that the answer is $$$2^i$$$ for some $$$i$$$. But this assumption fails when $$$n=11$$$, because $$$ans(11)=342$$$. After computing $$$ans(13)=820$$$ we arrive to another possible property of $$$ans(n)$$$: $$$ans(n)-1$$$ is divisible by $$$n$$$ and $$$\frac{ans(n)-1}{n}=2^i-1$$$ for some $$$i$$$. That is true for some cases, but fails in general for $$$n=23$$$ because $$$ans(23)=2048$$$ and $$$\frac{2047}{23}=89$$$. So, the assumption is that there are only three cases:

1. $$$ans(n)=2^i$$$ for some $$$i$$$

2. $$$ans(n)=n\cdot (2^i-1)+1$$$ for some $$$i$$$

3. $$$ans(n)=n\cdot k+1\neq 2^i$$$ where $$$k\neq 2^i-1$$$ for all $$$i$$$

This is, in fact, true, moreover, by brute forcing more numbers we can arrive to the following:

Theorem.

Let $$$i_1$$$ be the smallest $$$i>0$$$ such that $$$2^i-1$$$ is divisible by $$$n$$$ or $$$\infty$$$ if no such $$$i$$$ exists. Similarly, let $$$i_2$$$ be the smallest $$$i>0$$$ such that $$$2^i+1$$$ is divisible by $$$n$$$ or $$$\infty$$$ if no such $$$i$$$ exists. We will prove further that at least one of $$$i_1,i_2$$$ is finite. The main claim is: if $$$i_1<i_2$$$, then $$$ans(n)=2^{i_1}$$$, otherwise, $$$ans(n)=n\cdot k+1$$$ where $$$k$$$ is the reason I wrote this blog, because it seems impossible to compute it.

Proof.

Firstly, let's note that after the first operation the number of ones will always be even and for each array $$$a_0$$$ there are only two arrays $$$a_1,a_2$$$ such that $$$a_0$$$ can be obtained by applying the operation to $$$a_1,a_2$$$. Those arrays $$$a_1,a_2$$$ have the following property: if $$$a_1[i]=0$$$, then $$$a_2[i]=1$$$ and vice versa. From this follows that the number of ones in $$$a_1,a_2$$$ has different parity, so the cycle will be formed starting from the array $$$a=[1,0,\cdots ,0,1]$$$ and we are asked to find the length of this cycle and the answer will be the length of the cycle plus one.

So, let's consider array $$$a_1$$$ in the middle where the number of ones is two. Obviously, when we get two neighboring ones, we get either

1. the shift of the initial $$$a_0=[1,0,\cdots ,0,1]$$$ and the number of such shifts will be $$$n$$$ since $$$n$$$ is prime.

2. the start of a cycle with $$$a_1=a_0$$$.

The first case leads to $$$ans(n)=n\cdot k+1$$$ for some $$$k$$$ in which i couldn't advance further. The second case is much easier and leads to $$$ans(n)=2^{i_1}$$$, so let's prove this.

We will use the following notation for the array $$$a=[1,0,\cdots ,0,1]$$$ after $$$i$$$ operations: $$$b[i]$$$ with $$$b[0]=[1,0,\cdots ,0,1]$$$. The following can be easily proved by induction:

From it follows that the value of $$$t$$$ for which $$$b[1+2^t]$$$ has exactly two ones with one one at the beginning is $$$1$$$ and generally for each $$$t$$$, $$$b[2^t-1]$$$ has exactly two ones with one one at the beginning. Consider the index $$$j$$$ of the last one in 0-indexing. For $$$t=0$$$, $$$j=n-1$$$, for $$$t=1$$$, $$$j=n-2$$$ and for arbitrary $$$t$$$, $$$j=n-(2^t\mod n)$$$. Clearly, for the first $$$t>0$$$ such that $$$j=n-1$$$ and the cycle is formed, $$$2^t-1$$$ is divisible by n and for all $$$0<s<t$$$, $$$2^s\mod n\neq 1$$$ so $$$2^s-1$$$ is not divisible by $$$n$$$, so the answer is $$$2^{i_1}$$$.

In the second case, from (1) also follow the shifts, but since $$$i_2<i_1$$$, the case where $$$j=n-(2^t\mod n)=1$$$ comes before the case where $$$j=n-(2^t\mod n)=n-1$$$, so the shift from $$$b[0]$$$ to $$$a=[1,1,0,\cdots ,0]$$$ takes $$$2^{i_2}-1$$$ operations. The problem is that there can exists $$$s<2^{i_2}-1$$$ such that $$$b[s]=[0,\cdots ,0,1,1,0,\cdots ,0]$$$ so we can not say that the answer is $$$n\cdot (2^{i_2}-1)+1$$$. An example is $$$n=37$$$.

$$$n\cdot (2^{i_2}-1)+1$$$