for \(d|n\), for \(x\in \left\{ 0,1\right\}^d\), make sure \(x\) isn’t \(k\)-periodic for any \(k|d, k< d\); this can be done in linearithmic time because it suffices to check for \(p|d\) which is distinct prime divisors, and each such check requires linear time.

Now, you might ask, what the running time is. It is of course \[\sum_{d|n} 2^d d\log d\]

Now, is this actually better than just generating all binary strings of length \(n\) and then for each pair, checking if they are rotated copies of one another? of course! that’s like \(\Omega(4^n)\). This should be more like \(O(2^n n^2)\) or something… (I haven’t been able to do the sum yet, but whateves.)

it has been noted that it is possible to do this much faster and simpler with using hash tables; but can we beat \(O(2^n)\)? i kind of doubt it

Now you might ask, what if I want to also rule out reflectional symmetry and rotoation + reflectional symmetry ?

you might also ask is it possible to check rotational / roto-reflectional symmetry faster than \(n^2\) time?

to be continued after pickelball