To generate the necklaces for length n... Let N = 2^n and f(j) = 2*j if j < N/2, otherwise (2*j+1) (mod N). This induces a permutation of the elements [0...N-1]. Now write down the cycles, and for a cycle (r, s, t, ..., z), map its elements to {0,1} using m(x) = 0 if x < N/2, otherwise 1. An example for n=5. The cycles are (0) (1 2 4 8 16) (3 6 12 24 17) (5 10 20 9 18) (7 14 28 25 19) (11 22 13 26 21) (15 30 29 27 23) (31) The map m gives (dots for zeros) . ....1 ...11 ..1.1 ..111 .1.11 .1111 1 These are the primitive parts of the necklaces of length n. In other words: the Lyndon words whose length divide n. (Btw. for n prime this gives a neat algorithm to generate a random Lyndon word of length n with just n operations). This is implied in section "Example using inverse Burrows-Wheeler transform" in https://en.wikipedia.org/wiki/De_Bruijn_sequence All this is likely known but I have not seen it in this particular form. (Btw. the generalization from binary to k-ary is easy). Now here is a twist: Using the map f(j) = 2*j if j >= N/2, otherwise (2*j+1) (mod N). (note "j >= N/2", the condition is "swapped") and otherwise the procedure above I get n = 0: . # = 1 n = 1: .1 # = 1 n = 2: ..11 # = 1 n = 3: ...111 .1 # = 2 n = 4: ....1111 ..1.11.1 # = 2 n = 5: .....11111 ...1.111.1 ..1..11.11 .1 # = 4 n = 6: ......111111 ....1.1111.1 ...1..111.11 ...11.111..1 ..1.1.11.1.1 ..11 # = 6 n = 7: .......1111111 .....1.11111.1 ....1..1111.11 ....11.1111..1 ...1...111.111 ...1.1.111.1.1 ...11..111..11 ..1..1.11.11.1 ..1.1..11.1.11 .1 # = 10 These do seem to be the shift register sequences counted in A000016. IS THIS CORRECT? If it is, I'll enter comments to both sequences. Best regards, jj