How to perform AND on binary "recursive repeating sequences"?
Let $A,B$ be the two recursive repeating sequences, where $|A| = |B|$. If $|A| = |B| = 1$ then there is nothing to do. Otherwise, either $A$ is of the form $A_1A_2$ or of the form $(A')_k$, where $k &gt; 1$. In the second case, we can write $A = A' (A')_{k-1}$, which is also of the form $A_1A_2$. Thus it suffices to explain how to compute $A_1 A_2 \land B$ (here $\land$ means AND). We will show that we can find two recursive repeating sequences $B_1B_2$ such that $B=B_1B_2$ and $|A_1|=|B_1|$, $|A_2|=|B_2|$. We can then compute $A \land B = (A_1 \land B_1) (A_2 \land B_2)$.
Given a recursive repeating sequence $B$ and a number $\ell$, we have to break $B$ into $B_1B_2$, where $|B_1| = \ell$. We consider two cases:

$B = C_1 C_2 \dots C_r$. We can find $t$ such that $|C_1 C_2 \dots C_t| \leq \ell &lt; |C_1 C_2 \dots C_t| + |C_{t+1}|$. If $|C_1 C_2 \dots C_t| = \ell$ then we can take $B_1 = C_1 C_2 \dots C_t$ and $B_2 = C_{t+1} \dots C_r$. Otherwise, we break $C_{t+1}$ into two parts $D_1D_2$, where $|D_1| = \ell - |C_1 C_2 \dots C_t|$, and take $B_1 = C_1 C_2 \dots C_t D_1$ and $B_2 = D_2 C_{t+2} \dots C_r$.

$B = (C)_r$. We treat this as an explicit description of the preceding case, where $C_1 = \cdots = C_r = C$. We use division with remainder to find $t$ efficiently. In the easy case we take $B_1 = (C)_t$ and $B_2 = (C)_{r-t}$, and in the complicated case we take $B_1 = (C)_t D_1$ and $B_2 = D_2 (C)_{r-t-1}$.