login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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 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.70-74

Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], (26-May-2014)

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: A182846 A069196 A222209 * A118320 A082334 A151749

Adjacent sequences:  A108915 A108916 A108917 * A108919 A108920 A108921

KEYWORD

nonn

AUTHOR

Joerg Arndt, Jul 20 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 23 02:52 EDT 2017. Contains 288633 sequences.