A264596 Let S_n be the list of the first n nonnegative numbers written in binary, with least significant bits on the left, and sorted into lexicographic order; a(n) = position of n in S_n, starting indexing at 0.

0, 1, 1, 3, 1, 4, 3, 7, 1, 6, 4, 10, 3, 10, 7, 15, 1, 10, 6, 16, 4, 15, 10, 22, 3, 16, 10, 24, 7, 22, 15, 31, 1, 18, 10, 28, 6, 25, 16, 36, 4, 25, 15, 37, 10, 33, 22, 46, 3, 28, 16, 42, 10, 37, 24, 52, 7, 36, 22, 52, 15, 46, 31, 63, 1, 34, 18, 52, 10, 45, 28

Offset: 0

Author

N. J. A. Sloane, Nov 19 2015

Keywords

• nonn
• base

Examples

			S_0 = [0], a(0) = 0;
S_1 = [0, 1], a(1) = 1;
S_2 = [0, 01, 1], a(2) = 1;
S_3 = [0, 01, 1, 11], a(3) = 3;
S_4 = [0, 001, 01, 1, 11], a(4) = 1;
S_5 = [0, 001, 01, 1, 101, 11], a(5) = 4;
S_6 = [0, 001, 01, 011, 1, 101, 11], a(6) = 3;
S_7 = [0, 001, 01, 011, 1, 101, 11, 111], a(7) = 7;
S_8 = [0, 0001, 001, 01, 011, 1, 101, 11, 111], a(8) = 1;
...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..20000

Crossrefs

Suggested by John Bodeen's A263856.

Cf. A188215.

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 0,
      `if`(irem(n, 2, 'r')=0, a(r), a(r)+r+1))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Nov 19 2015

Mathematica

A264596[0]=0;A264596[n_]:=A264596[n]=A264596[Floor[n/2]]+Boole[OddQ[n]](Floor[n/2]+1);Array[A264596,100,0] (* Paolo Xausa, Nov 04 2023, after Alois P. Heinz *)

Python

def A264596(n):
    return sorted(format(i,'b')[::-1] for i in range(n+1)).index(format(n,'b')[::-1]) # Chai Wah Wu, Nov 22 2015

Formula

a(2^n) = 1.

a(2^n-1) = 2^n-1.

a(2n) = a(n), a(2n+1) = a(n) + n+1, a(0) = 0. - Alois P. Heinz, Nov 19 2015

Conjecture: a(n) = n*(n + 3)/2 - A007814(A293290(n)) for n > 0. - Velin Yanev, Sep 12 2017

Extensions

More terms from Alois P. Heinz, Nov 19 2015