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

%I #40 Nov 05 2023 09:04:04

%S 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,

%T 22,15,31,1,18,10,28,6,25,16,36,4,25,15,37,10,33,22,46,3,28,16,42,10,

%U 37,24,52,7,36,22,52,15,46,31,63,1,34,18,52,10,45,28

%N 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.

%H Alois P. Heinz, <a href="/A264596/b264596.txt">Table of n, a(n) for n = 0..20000</a>

%F a(2^n) = 1.

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

%F a(2n) = a(n), a(2n+1) = a(n) + n+1, a(0) = 0. - _Alois P. Heinz_, Nov 19 2015

%F Conjecture: a(n) = n*(n + 3)/2 - A007814(A293290(n)) for n > 0. - _Velin Yanev_, Sep 12 2017

%e S_0 = [0], a(0) = 0;

%e S_1 = [0, 1], a(1) = 1;

%e S_2 = [0, 01, 1], a(2) = 1;

%e S_3 = [0, 01, 1, 11], a(3) = 3;

%e S_4 = [0, 001, 01, 1, 11], a(4) = 1;

%e S_5 = [0, 001, 01, 1, 101, 11], a(5) = 4;

%e S_6 = [0, 001, 01, 011, 1, 101, 11], a(6) = 3;

%e S_7 = [0, 001, 01, 011, 1, 101, 11, 111], a(7) = 7;

%e S_8 = [0, 0001, 001, 01, 011, 1, 101, 11, 111], a(8) = 1;

%e ...

%p a:= proc(n) option remember; `if`(n=0, 0,

%p `if`(irem(n, 2, 'r')=0, a(r), a(r)+r+1))

%p end:

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Nov 19 2015

%t 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_ *)

%o (Python)

%o def A264596(n):

%o return sorted(format(i,'b')[::-1] for i in range(n+1)).index(format(n,'b')[::-1]) # _Chai Wah Wu_, Nov 22 2015

%Y Suggested by John Bodeen's A263856.

%Y Cf. A188215.

%K nonn,base

%O 0,4

%A _N. J. A. Sloane_, Nov 19 2015

%E More terms from _Alois P. Heinz_, Nov 19 2015