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

Author

Grant Garcia, Mar 24 2011

Keywords

• nonn
• base

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.

Examples

			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)
		

Links

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

Crossrefs

Cf. A264596.

Programs

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

Python

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

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.

Extensions

Program added by Grant Garcia, Mar 30 2011

Edited by Grant Garcia, Apr 13 2011