OFFSET
1,2
COMMENTS
The lexicographic order of the subsets of the 4-element set is:
1... {0}
11.. {0, 1}
111. {0, 1, 2}
1111 {0, 1, 2, 3}
11.1 {0, 1, 3}
1.1. {0, 2}
1.11 {0, 2, 3}
1..1 {0, 3}
.1.. {1}
.11. {1, 2}
.111 {1, 2, 3}
.1.1 {1, 3}
..1. {2}
..11 {2, 3}
...1 {3}
The strings of dots and ones interpreted as binary words give this sequence:
...1 1
..11 3
..1. 2
.1.1 5
.111 7
.11. 6
.1.. 4
1..1 9
1.11 11
1.1. 10
11.1 13
1111 15
111. 14
11.. 12
1... 8
The index of the lowest set bit of a(n) is A082850(n) - 1. - Joerg Arndt, Apr 06 2011
The sequence is a permutation of the positive integers. - Joerg Arndt, Jan 31 2012
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
REFERENCES
Donald E. Knuth, The Art of Computer Programming, Volume 4A, section 7.2.1.3 exercise 19 (binomial tree traversed in post-order).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..8192
Joerg Arndt, Matters Computational (The Fxtbook), section 1.26 "Binary words in lexicographic order for subsets", pp.70-74
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014-2015.
FORMULA
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
MATHEMATICA
n=6; Reverse[ SortBy[ Range[2^n - 1], PadRight[ Flatten[ Position[ IntegerDigits[#, 2, n], 1] ], n] &]] (* Birkas Gyorgy, Jul 09 2012 *)
PROG
(C++) /* To generate a(k): */
ulong negidx2lexrev(ulong k)
{
ulong z = 0;
ulong h = highest_bit(k);
while ( k )
{
while ( 0==(h&k) ) h >>= 1;
z ^= h;
++k;
k &= h - 1;
}
return z;
}
/* Where highest_bit(x) shall return the word with
just the highest bit set (and zero for zero x). */
(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
(Python)
def a(n):
s = 0
for k in range(n.bit_length()-1, -1, -1):
if n & (1 << k): n += 1; s = k
return n - (1 << s)
print([a(n) for n in range(1, 65)]) # Michael S. Branicky, Aug 15 2022 after Kevin Ryde
CROSSREFS
KEYWORD
nonn
AUTHOR
Joerg Arndt, Jul 20 2005
STATUS
approved