Leader Election: Every bit-reversal ring is $\frac{1}{2}$-symmetric
We will prove your formula for all $\ell$, with a bound of $\lceil \frac{n/2}{\ell} \rceil$. We can assume that $\ell &lt; n/2$, since otherwise $\lceil \frac{n/2}{\ell} \rceil = 1$, and there is nothing to prove. Also, if $n = 1$ then the result is trivial, so we can assume that $n \geq 2$.
The relative order of elements in the interval of length $n/2$ starting at $i$ is the same as the relative order of elements in the ring of length $n/2$, when read from position $i$. For example, here are all intervals of length $4$ in the ring of length $8$, and the corresponding intervals in the ring of length $4$:
\begin{align}
&amp;0,4,2,6 &amp; 0,2,1,3 \\
&amp;4,2,6,1 &amp; 2,1,3,0 \\
&amp;2,6,1,5 &amp; 1,3,0,2 \\
&amp;6,1,5,3 &amp; 3,0,2,1 \\
&amp;1,5,3,7 &amp; 0,2,1,3 \\
&amp;5,3,7,0 &amp; 2,1,3,0 \\
&amp;3,7,0,4 &amp; 1,3,0,2 \\
&amp;7,0,4,2 &amp; 3,0,2,1
\end{align}
To see this, note first that each interval on the left doesn't contain a pair of elements which differ only in their LSB. Therefore, we can ignore the LSB of all elements on the left. One way to do it is to divide all elements on the left by two. This results in the intervals on the right.
This property immediately implies a similar property for all intervals of length $\ell \leq n/2$: the relative order of elements in the interval of length $\ell$ starting at $i$ is the same as the relative order of elements in the interval of length $\ell$ starting at $i \bmod (n/2)$ in the ring of length $n/2$. This implies (by induction) that an interval of length $\ell \leq n/2$ has at least this many order-equivalent intervals: $2\lceil \frac{n/4}{\ell} \rceil \geq \lceil \frac{n/2}{\ell} \rceil$.