A233905 - OEIS

%I #14 Dec 22 2013 02:00:31

%S 0,0,0,1,0,2,1,4,0,4,2,7,1,7,4,11,0,8,4,13,2,12,7,18,1,13,7,20,4,18,

%T 11,26,0,16,8,25,4,22,13,32,2,22,12,33,7,29,18,41,1,25,13,38,7,33,20,

%U 47,4,32,18,47,11,41,26,57,0,32,16,49,8,42,25,60,4,40,22,59,13,51,32,71,2,42,22,63,12,54

%N a(2n) = a(n), a(2n+1) = a(n) + n, with a(0)=0.

%C For every one bit in the binary representation of n, add the number represented by the substring left of it.

%H Antti Karttunen, <a href="/A233905/b233905.txt">Table of n, a(n) for n = 0..8192</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) = sum(k=0..floor(log(n)/log(2)), bittest(n,k) * floor(n/2^(k+1)) ) = sum(k=0..A000523(n), A030308(n,k+1) * floor(n/2^(k+1)) ), with bittest(n,k)=0 or 1 according to the k-th bit of n (the zeroth bit the least significant).

%F a(n) = A011371(n) - A233931(n).

%e 27 is 11011 in binary, so we add 1, 110=6, and 1101=13, so a(27)=20.

%o (PARI) a(n)=if(n<1,0,if(n%2,a(n\2)+n\2,a(n/2)))

%o (PARI) a(n)=sum(k=0,floor(log(n)/log(2)),bittest(n,k)*floor(n/2^(k+1)))

%o (Scheme, with memoizing definec-macro from Antti Karttunen's IntSeq-library)

%o (definec (A233905 n) (cond ((zero? n) n) ((even? n) (A233905 (/ n 2))) (else (+ (A233905 (/ (- n 1) 2)) (/ (- n 1) 2)))))

%o ;; _Antti Karttunen_, Dec 21 2013

%K nonn

%O 0,6

%A _Ralf Stephan_, Dec 17 2013