cp's OEIS Frontend

A108918 Reversed binary words in reversed lexicographic order.

%I A108918 #69 Jan 06 2024 08:53:53
%S A108918 1,3,2,5,7,6,4,9,11,10,13,15,14,12,8,17,19,18,21,23,22,20,25,27,26,29,
%T A108918 31,30,28,24,16,33,35,34,37,39,38,36,41,43,42,45,47,46,44,40,49,51,50,
%U A108918 53,55,54,52,57,59,58,61,63,62,60,56,48,32,65
%N A108918 Reversed binary words in reversed lexicographic order.
%C A108918 The lexicographic order of the subsets of the 4-element set is:
%C A108918   1... {0}
%C A108918   11.. {0, 1}
%C A108918   111. {0, 1, 2}
%C A108918   1111 {0, 1, 2, 3}
%C A108918   11.1 {0, 1, 3}
%C A108918   1.1. {0, 2}
%C A108918   1.11 {0, 2, 3}
%C A108918   1..1 {0, 3}
%C A108918   .1.. {1}
%C A108918   .11. {1, 2}
%C A108918   .111 {1, 2, 3}
%C A108918   .1.1 {1, 3}
%C A108918   ..1. {2}
%C A108918   ..11 {2, 3}
%C A108918   ...1 {3}
%C A108918 The strings of dots and ones interpreted as binary words give this sequence:
%C A108918   ...1   1
%C A108918   ..11   3
%C A108918   ..1.   2
%C A108918   .1.1   5
%C A108918   .111   7
%C A108918   .11.   6
%C A108918   .1..   4
%C A108918   1..1   9
%C A108918   1.11  11
%C A108918   1.1.  10
%C A108918   11.1  13
%C A108918   1111  15
%C A108918   111.  14
%C A108918   11..  12
%C A108918   1...   8
%C A108918 The index of the lowest set bit of a(n) is A082850(n) - 1. - _Joerg Arndt_, Apr 06 2011
%C A108918 The sequence is a permutation of the positive integers. - _Joerg Arndt_, Jan 31 2012
%C A108918 This is the output of the depth-first search with postordering in the binomial tree described in A129760 where the children of every node are visited in the ascending order of their values. Descending order cannot be used because 0 has infinite number of children; using preordering instead of postordering gives the natural numbers in their standard order. - _Andrey Zabolotskiy_, Sep 06 2019
%D A108918 Donald E. Knuth, The Art of Computer Programming, Volume 4A, section 7.2.1.3 exercise 19 (binomial tree traversed in post-order).
%H A108918 Alois P. Heinz, <a href="/A108918/b108918.txt">Table of n, a(n) for n = 1..8192</a>
%H A108918 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 1.26 "Binary words in lexicographic order for subsets", pp.70-74
%H A108918 Joerg Arndt, <a href="http://arxiv.org/abs/1405.6503">Subset-lex: did we miss an order?</a>, arXiv:1405.6503 [math.CO], 2014-2015.
%H A108918 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A108918 a(2^(m+1)-1) = 2^m; a(2^m+k) = a(k+1) + 2^m for 0 <= k < 2^m-1. - _Andrey Zabolotskiy_, Oct 10 2019
%t A108918 n=6; Reverse[ SortBy[ Range[2^n - 1], PadRight[ Flatten[ Position[ IntegerDigits[#, 2, n], 1] ], n] &]] (* _Birkas Gyorgy_, Jul 09 2012 *)
%o A108918 (C++) /* To generate a(k): */
%o A108918 ulong negidx2lexrev(ulong k)
%o A108918 {
%o A108918   ulong z = 0;
%o A108918   ulong h = highest_bit(k);
%o A108918   while ( k )
%o A108918   {
%o A108918     while ( 0==(h&k) ) h >>= 1;
%o A108918     z ^= h;
%o A108918     ++k;
%o A108918     k &= h - 1;
%o A108918   }
%o A108918   return z;
%o A108918 }
%o A108918 /* Where highest_bit(x) shall return the word with
%o A108918    just the highest bit set (and zero for zero x). */
%o A108918 (PARI) a(n) = my(s); forstep(k=logint(n,2),0,-1, if(bittest(n,k), n++;s=k)); n-(1<<s); \\ _Kevin Ryde_, Mar 31 2020
%o A108918 (Python)
%o A108918 def a(n):
%o A108918     s = 0
%o A108918     for k in range(n.bit_length()-1, -1, -1):
%o A108918         if n & (1 << k): n += 1; s = k
%o A108918     return n - (1 << s)
%o A108918 print([a(n) for n in range(1, 65)]) # _Michael S. Branicky_, Aug 15 2022 after _Kevin Ryde_
%Y A108918 The sequence of lowest bits is A079559. The sequence of fixed points (i.e. a(n)=n) is A079471. The inverse permutation is A118319.
%Y A108918 The corresponding Gray code is described in A217262.
%K A108918 nonn
%O A108918 1,2
%A A108918 _Joerg Arndt_, Jul 20 2005