Create binary numbers with a described pattern
Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$ on the &quot;top level&quot; are symbols, and let $0^n, 1^n$ represent $n$ consecutive zeroes and ones respectively.

For size 2, $E = 1$, and the one string is given by $0^1 1^1 = 01$.

For size 4, $E = 2$, and the two strings are $0^2 1^2 = (0^2 1^2)^1 = 0011$ and $(0^1 1^1)^2 = 0101$.

For size 8, $E = 3$, and the three strings are $(0^4 1^4)^1 = 00001111$, $(0^2 1^2)^2 = 00110011$, $(0^1 1^1)^4 = 01010101$.

For size $n = 2^E$, the $E$ strings include $(0^1 1^1)^{n/2} = (0^{2^0} 1^{2^0})^{2^{E-1}}$ to $(0^{n/2} 1^{n/2})^1 = (0^{2^{E-1}} 1^{2^{E-1}})^{2^{0}}$. Thus, the $E$ strings can be parameterized by a natural number $k$ from 0 to $E-1$ such that the member is expressible as $(0^{2^k} 1^{2^k})^{2^{(E-1)-k}}$.


Thus, the examples are:

Size 2: $E = 1$. The one string is $(0^1 1^1)^1 = (0^{2^0}1^{2^0})^{2^0}$

Size 4: $E = 2$. The two strings are $0101 = (0^1 1^1)^2 = (0^{2^0} 1^{2^0})^{2^1}$ and $0011 = (0^2 1^2)^1 = (0^{2^1} = 1^{2^1})^{2^0}$.

Size 8: $E = 3$. The three strings are $01010101 = (0^{2^0} 1^{2^0})^{2^2}$ with $k = 0$, $00110011 = (0^{2^1} 1^{2^1})^{2^1}$ with $k = 1$, $00001111 = (0^{2^2} 1^{2^2})^{2^0}$ with $k = 2$.


This is an iterative algorithm. You list each string, of length $n$ a total of $\log n$ times. It is $O(n \log n)$ to list all the strings explicity. It is $O(\log n)$ to express them regex style like $(0^x 1^x)^y$ [note $x, y$ are powers of 2, and the exponents in the power form of $x, y$ add up to $E-1$].