Solution
Primitive Necklaces
Show the problem again
A necklace of 12 beads, each black or white, is considered up to rotation. Call it primitive if no rotation other than the identity maps it to itself (equivalently, it does not consist of a shorter block repeated). How many primitive necklaces of 12 beads are there? Give an integer.
Worked solution
The answer is 335. Let $A(d)$ be the number of binary strings of length $d$ that are aperiodic (not a power of a shorter string). Every string of length 12 is uniquely a repetition of an aperiodic string of length $d$ dividing 12, so $\sum_{d \mid 12} A(d) = 2^{12}$, and Mobius inversion gives $A(12) = \sum_{d \mid 12} \mu(12/d)\, 2^{d} = 2^{12} - 2^{6} - 2^{4} + 2^{2} = 4096 - 64 - 16 + 4 = 4020$. An aperiodic string has 12 distinct rotations, all aperiodic, so primitive necklaces number $4020/12 = 335$. (These are counted by the Lyndon words of length 12.)
Source: Counting aperiodic necklaces (Lyndon words) by Mobius inversion; standard material in combinatorics on words. Statement written for AxiomIQ.