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,4

Links

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

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

Example

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

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

Prog

(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

Crossrefs

Suggested by John Bodeen's A263856.

Cf. A188215.

Sequence in context: A230877 A326041 A209613 * A262214 A340760 A035626

Adjacent sequences: A264593 A264594 A264595 * A264597 A264598 A264599

Keyword

nonn,base

Author

N. J. A. Sloane, Nov 19 2015

Extensions

More terms from Alois P. Heinz, Nov 19 2015

Status

approved