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. 6
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

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

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.

Index entries for sequences that are permutations of the natural numbers

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

CROSSREFS

The sequence of lowest bits is A079559. The sequence of fixed points (i.e. a(n)=n) is A079471. The inverse permutation is A118319.

Sequence in context: A069196 A222209 A118320 * A316472 A082334 A294371

Adjacent sequences:  A108915 A108916 A108917 * A108919 A108920 A108921

KEYWORD

nonn,changed

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 05:07 EDT 2019. Contains 328145 sequences. (Running on oeis4.)