A188215 Starting with an empty list, n is inserted after the a(n)th element such that the binary representations of the list's elements are always sorted lexicographically.

0, 1, 2, 3, 3, 4, 6, 7, 4, 5, 7, 8, 11, 12, 14, 15, 5, 6, 8, 9, 12, 13, 15, 16, 20, 21, 23, 24, 27, 28, 30, 31, 6, 7, 9, 10, 13, 14, 16, 17, 21, 22, 24, 25, 28, 29, 31, 32, 37, 38, 40, 41, 44, 45, 47, 48, 52, 53, 55

Offset

0,3

Comments

The last occurrence of any positive n in this sequence is a(2^(n - 1)).

As the list in question expands, its initial terms converge toward A131577.

The last item of the list is always zero or an element of A075427.

Links

T. D. Noe, Table of n, a(n) for n = 0..1023

Formula

a(2^n + b) = n + b + 1 for b = 0 or 1.

a(2^n - b) = 2^n - b for b = 1 or 2.

Example

For example, an a(n) of 3 means that n should be inserted after the 3rd element of the list to keep the elements lexicographically ordered.
[] (Initial empty list)
[0] (Zero inserted at the beginning: a(0) = 0)
[0, 1] (One inserted after element 1: a(1) = 1)
[0, 1, 10] (Two inserted after element 2: a(2) = 2)
[0, 1, 10, 11] (Three inserted after element 3: a(3) = 3)
[0, 1, 10, 100, 11] (Four inserted after element 3: a(4) = 3)

Mathematica

lst = {}; Table[s = IntegerString[n, 2]; lst = Sort[Append[lst, s]]; Position[lst, s][[1, 1]] - 1, {n, 0, 63}] (* T. D. Noe, Apr 19 2011 *)

Prog

(Python)
l = []
for i in range(17):
    b = bin(i)[2:]
    l.append(b)
    l.sort()
    print(l.index(b))

Crossrefs

Cf. A264596.

Sequence in context: A181692 A145806 A100989 * A162627 A023158 A120882

Adjacent sequences: A188212 A188213 A188214 * A188216 A188217 A188218

Keyword

nonn,base

Author

Grant Garcia, Mar 24 2011

Extensions

Program added by Grant Garcia, Mar 30 2011

Edited by Grant Garcia, Apr 13 2011

Status

approved