[math-fun] OEIS: base 2 rev rev lex order fixed points
Didn't find them in the OEIS. Btw. where does the EOIS live by now ? (I recall it was asked not to submit new sequences at the old site). Reversed binary words of the words in reversed lex order ('.' for zero, asterisk at fixed points): 0: .... = 0 * 1: ...1 = 1 * 2: ..11 = 3 3: ..1. = 2 4: .1.1 = 5 5: .111 = 7 6: .11. = 6 * 7: .1.. = 4 8: 1..1 = 9 9: 1.11 = 11 10: 1.1. = 10 * 11: 11.1 = 13 12: 1111 = 15 13: 111. = 14 14: 11.. = 12 15: 1... = 8 16: 1...1 = 17 17: 1..11 = 19 18: 1..1. = 18 * 19: 1.1.1 = 21 Step through the words via: static inline ulong next_lexrev(ulong x) // Return next word in (reversed) lex order. { ulong x0 = x & -x; if ( 1==x0 ) { x ^= x0; x0 = x & -x; x0 ^= (x0>>1); } else x0 >>= 1; x ^= x0; return x; } static inline ulong prev_lexrev(ulong x) // Return previous word in (reversed) lex order. { ulong x0 = x & -x; if ( x & (x0<<1) ) x ^= x0; else { x0 ^= (x0<<1); x ^= x0; x |= 1; } return x; } fixed points are the seq: 0, 1, 6, 10, 18, 34, 60, 66, 92, 108, 116, 130, 156, 172, 180, 204, 212, 228, 258, 284, 300, 308, 332, 340, 356, 396, 404, 420, 452, 514, 540, 556, 564, 588, 596, 612, 652, 660, 676, 708, 780, 788, 804, 836, 900, 1026, 1052, 1068, 1076, 1100, 1108, 1124, 1164, 1172, 1188, 1220, 1292, 1300, 1316, 1348, 1412, 1548, 1556, 1572, 1604, 1668, 1796, 2040, 2050, 2076, 2092, 2100, 2124, 2132, 2148, 2188, 2196, 2212, 2244, 2316, 2324, 2340, 2372, 2436, 2572, 2580, 2596, 2628, 2692, 2820, 3064, 3084, 3092, 3108, 3140, 3204, 3332, 3576, 3588, 3832, 3960, 4024, 4056, 4072, 4098, 4124, 4140, 4148, 4172, 4180, 4196, 4236, 4244, 4260, 4292, 4364, 4372, 4388, 4420, 4484, 4620, 4628, 4644, 4676, 4740, 4868, 5112, 5132, 5140, 5156, 5188, 5252, 5380, 5624, 5636, 5880, 6008, 6072, 6104, 6120, 6156, 6164, 6180 ... These are the words where the bit count is equal zero and to 2**(i0) where i0 is the index of the lowest set bit: 0: ........... 1: ..........1 6: ........11. 10: .......1.1. 18: ......1..1. 34: .....1...1. 60: .....1111.. 66: ....1....1. 92: ....1.111.. 108: ....11.11.. 116: ....111.1.. 130: ...1.....1. 156: ...1..111.. 172: ...1.1.11.. 180: ...1.11.1.. 204: ...11..11.. 212: ...11.1.1.. 228: ...111..1.. 258: ..1......1. 284: ..1...111.. 300: ..1..1.11.. 308: ..1..11.1.. 332: ..1.1..11.. 340: ..1.1.1.1.. 356: ..1.11..1.. 396: ..11...11.. 404: ..11..1.1.. 420: ..11.1..1.. 452: ..111...1.. 514: .1.......1. 540: .1....111.. 556: .1...1.11.. [-snip-] 1556: ..11....1.1.. 1572: ..11...1..1.. 1604: ..11..1...1.. 1668: ..11.1....1.. 1796: ..111.....1.. 2040: ..11111111... 2050: .1.........1. 2076: .1......111.. 2092: .1.....1.11.. 2100: .1.....11.1.. 2124: .1....1..11.. 2132: .1....1.1.1.. 2148: .1....11..1.. [-snip-] 4644: .1..1...1..1.. 4676: .1..1..1...1.. 4740: .1..1.1....1.. 4868: .1..11.....1.. 5112: .1..1111111... 5132: .1.1......11.. 5140: .1.1.....1.1.. 5156: .1.1....1..1.. 5188: .1.1...1...1.. 5252: .1.1..1....1.. 5380: .1.1.1.....1.. 5624: .1.1.111111... 5636: .1.11......1.. 5880: .1.11.11111... 6008: .1.111.1111... 6072: .1.1111.111... 6104: .1.11111.11... 6120: .1.111111.1... 6156: .11.......11.. 6164: .11......1.1.. 6180: .11.....1..1.. ulong is_lexrev_fixed_point(ulong x) // Return whether x is a fixed point in the prev_lexrev() - sequence { if ( x & 1 ) { if ( 1==x ) return 1; else return 0; } else { ulong w = bit_count(x); if ( w != (w & -w) ) return 0; if ( 0==x ) return 1; return ( (x & -x) & w ); } } Hope C isn't that much hated here I am not allowed to post snippets like this. I wrote the equivalent routines for mixed radix lex order words, there seem to be no nontrivial fixed points for base =!=2. (Still have to check the code and this assertion). all the best, jj -- p=2^q-1 prime <== q>2, cosh(2^(q-2)*log(2+sqrt(3)))%p=0 Life is hard and then you die.
participants (1)
-
Joerg Arndt