Skip to main content
added 62 characters in body
Source Link

I believeFor aperiodic (sometimes also called, full period) strings, the term you are looking for is Lyndon words. These are the (unique lexicographically-least) representative of a full-period necklace (as stated in the comments, a necklace is the equivalence class under cyclic rotation). The number $k(n)$ you ask for is exactly the number of necklaces, and again, as stated in the comments, it is given by $k(n)=\frac{1}{n}\sum_{d|n}\phi(d)2^{n/d}$. You can check out a proof for this in S.W.Golomb's book "Shift Register Sequences" (in the 1967 edition, start looking at around page 171 and look for the cycles of $PCR_n$).

I believe the term you are looking for is Lyndon words. These are the (unique lexicographically-least) representative of a necklace (as stated in the comments, a necklace is the equivalence class under cyclic rotation). The number $k(n)$ you ask for is exactly the number of necklaces, and again, as stated in the comments, it is given by $k(n)=\frac{1}{n}\sum_{d|n}\phi(d)2^{n/d}$. You can check out a proof for this in S.W.Golomb's book "Shift Register Sequences" (in the 1967 edition, start looking at around page 171 and look for the cycles of $PCR_n$).

For aperiodic (sometimes also called, full period) strings, the term you are looking for is Lyndon words. These are the (unique lexicographically-least) representative of a full-period necklace (as stated in the comments, a necklace is the equivalence class under cyclic rotation). The number $k(n)$ you ask for is exactly the number of necklaces, and again, as stated in the comments, it is given by $k(n)=\frac{1}{n}\sum_{d|n}\phi(d)2^{n/d}$. You can check out a proof for this in S.W.Golomb's book "Shift Register Sequences" (in the 1967 edition, start looking at around page 171 and look for the cycles of $PCR_n$).

Source Link

I believe the term you are looking for is Lyndon words. These are the (unique lexicographically-least) representative of a necklace (as stated in the comments, a necklace is the equivalence class under cyclic rotation). The number $k(n)$ you ask for is exactly the number of necklaces, and again, as stated in the comments, it is given by $k(n)=\frac{1}{n}\sum_{d|n}\phi(d)2^{n/d}$. You can check out a proof for this in S.W.Golomb's book "Shift Register Sequences" (in the 1967 edition, start looking at around page 171 and look for the cycles of $PCR_n$).