

A108918


Reversed binary words in reversed lexicographic order.


5



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, 31, 30, 28, 24, 16, 33, 35, 34, 37, 39, 38, 36, 41, 43, 42, 45, 47, 46, 44, 40, 49, 51, 50, 53, 55, 54, 52, 57, 59, 58, 61, 63, 62, 60, 56, 48, 32, 65
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The lexicographic order of the subsets of the 4element 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 and read upside down give the sequence.
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


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.7074
Joerg Arndt, Subsetlex: did we miss an order?, arXiv:1405.6503 [math.CO], (26May2014)
Index entries for sequences that are permutations of the natural numbers


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). */


CROSSREFS

The sequence of lowest bits is A079559. The sequence of fixed points (i.e. a(n)=n) is A079471.
Sequence in context: A292962 A069196 A222209 * A118320 A316472 A082334
Adjacent sequences: A108915 A108916 A108917 * A108919 A108920 A108921


KEYWORD

nonn


AUTHOR

Joerg Arndt, Jul 20 2005


STATUS

approved



