-------- Original Message -------- Date: 2019-04-01 07:18 From: Joerg Arndt <arndt@jjj.de> To: math-fun <math-fun@mailman.xmission.com> Reply-To: math-fun <math-fun@mailman.xmission.com> 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[s] 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 Golly animation of a shift register sequence: #Life 1.05 #D Pseudorandom LWSS generator with p46 logic #D A lightweight spaceship stream is emitted representing a #D pseudorandom binary sequence satisfying the recursion #D a[n] = a[n-1] XOR a[n-19]. (By spreading out the pattern, #D the 19 can be changed.) The sequence has period 413385, #D so the gun has period 46*413385 = 19015710. #D Built by Bill Gosper, October 1989 or earlier #D (Header by Dean Hickerson, 4/11/93) x = 167, y = 139, rule = B3/S23 77b2o7b2o$77b2o6bo2b2o$76bo2bo4b6o$77b2obo5b4o$77b2obo2$77b2obo$77b2ob o5b4o$74b2ob3o4b6o11b2o$74bobobo6bo2b2o11b2o$75b4o7b2o$76b2o40$22b2o$ 22b2o5$157b2o$157b2o5$23b2o3b2o5$21b2obo3bob2o$21bo2bo3bo2bo$22b3o3b3o 126b2o5b2o$156bobo5bobo$156bo2bo3bo2bo$157b2o5b2o5$22b2o$22b2o5$157b2o $157b2o9$2b2o$2b2o6$2b3o3b3o$bo2bo3bo2bo$bo3bobo3bo$2obobobobob2o$2ob 2o3b2ob2o69b2o$b3o5b3o69bo2b2o$49b2o30bo3bo$48bo2bo30bo2bo$48bo2bo30b 3o$49b3o$82b3o$9bo72bo2bo$8bobo58b2o10bo3bo10b2o$7bo3bo37b3o17b2o10bo 2b2o10b2o$7b5o24b2o10bo2bo11b2o17b2o$6bobobobo23b2o10bo2bo11b2o$7bo3bo 37b2o2$7bo3bo$6bobobobo$2b2o3b5o76b2o$2b2o3bo3bo75bobo$8bobo75b2obo$9b o38b3o3bo32b2o26b2o$46b5o2bobo32bo25b2ob2o$41bo3b2o3b2o3bo59bo2bo$36bo 3bo4b3o3bo2bo33bo26bo2bo$35bo8bob2o3b3o33b2o27b2o$35bo2b2o5bo32b2o6b2o bo$36b2o5bo2b2o3b3o24b2o7bobo26b2o$37b3o3b5o3bo2bo33b2o25bo2bo$45b2o3b 2o3bo12b2o45bo2bo6b2o$37b3o3b8o2bobo12b2o44b2ob2o6b2o$36b2o5bo2bob3o3b o60b2o$21b2o12bo2b2o5bo$21b2o12bo8b2o$36bo3bo$41bo! Period 46 ⨉ 2088705 = 96080430 version (stifled) x = 180, y = 162, rule = B3/S23 56b2o7b2o$56b2o6bo2b2o$55bo2bo4b6o$56b2obo5b4o$56b2obo2$56b2obo$56b2ob o5b4o$53b2ob3o4b6o11b2o$53bobobo6bo2b2o11b2o$54b4o7b2o$55b2o40$b2o5bo$ b2o4b3o$6b2ob2o2$5bobobobo2$6b2ob2o$6b2ob2o$8bo9$2obo3bob2o$o2bo3bo2bo $b3o3b3o8$b2o$b2o$159b2o$159b2o12$160bo5bo$159b3o3b3o$158bo3bobo3bo$ 158bo9bo$159b3o3b3o5$161b2ob2o$162bobo$158b2ob2ob2ob2o$158bo2bo3bobo$ 158bo7bo$158bo2bo$159b2o9$4b2o$4b2o172b2o$178bo$176bobo$46bo2bo42bo2bo 42bo2bo34b2o$24b4o22bo19b4o22bo19b4o22bo19b4o$23bo3bo18bo3bo18bo3bo18b o3bo18bo3bo18bo3bo18bo3bo$4b3o3b3o14bo19b4o22bo19b4o22bo19b4o22bo$3bo 2bo3bo2bo9bo2bo42bo2bo42bo2bo42bo2bo$3bo3bobo3bo$2b2obobobobob2o69b2o$ 2b2ob2o3b2ob2o59b2o10bo$3b3o5b3o9b2o47bo3b2o5b2o2bo$22b2o17b2o7b3o19bo 4bo6bo2bo$24bo15bo2bo4bo4bo18bo3b2o7bobo$40bo2bo4bo5bo19b2o9b2o$40bo3b o8bo$41b2o8b2o32b2o32b3o$11bo73bobo33bo$10bobo28b2o8b2o18b2o11bo2bo10b 2o20bo$9bo3bo30bo8bo17b2o10b2o2bo10b2o$9b5o24b2o8bo5bo10b2o19bo$8bobob obo23bo9bo4bo11b2o17b2o$9bo3bo21bo6bo7b3o$34b2o3bo2bo$9bo3bo20bobo$8bo bobobo$4b2o3b5o76b2o$4b2o3bo3bo75bobo16b2o$10bobo75b2obo15bobo$11bo38b 3o3bo32b2o18bo7b2o$48b5o2bobo32bo25b2ob2o$43bo3b2o3b2o3bo59bo2bo$38bo 3bo4b3o3bo2bo33bo26bo2bo$37bo8bob2o3b3o33b2o27b2o$37bo2b2o5bo32b2o6b2o bo$38b2o5bo2b2o3b3o24b2o7bobo26b2o$39b3o3b5o3bo2bo33b2o25bo2bo$47b2o3b 2o3bo12b2o45bo2bo6b2o$39b3o3b8o2bobo12b2o44b2ob2o6b2o$38b2o5bo2bob3o3b o60b2o$23b2o12bo2b2o5bo$23b2o12bo8b2o$38bo3bo$43bo! (If you are a sequence person but not a Golly person, you're missing out.) —rwg