login
Number of 1-bits in the binary expansion of n which have an odd number of 0-bits at less significant bit positions.
5

%I #9 Apr 17 2021 19:51:26

%S 0,0,1,0,0,1,2,0,1,0,1,1,0,2,3,0,0,1,2,0,1,1,2,1,2,0,1,2,0,3,4,0,1,0,

%T 1,1,0,2,3,0,1,1,2,1,1,2,3,1,0,2,3,0,2,1,2,2,3,0,1,3,0,4,5,0,0,1,2,0,

%U 1,1,2,1,2,0,1,2,0,3,4,0,1,1,2,1,1,2,3

%N Number of 1-bits in the binary expansion of n which have an odd number of 0-bits at less significant bit positions.

%C See A343029 for further notes.

%H Kevin Ryde, <a href="/A343030/b343030.txt">Table of n, a(n) for n = 0..8192</a>

%F a(n) = A343029(n) - A004718(n).

%F a(n) = A000120(n) - A343029(n), where A000120 is the number of 1-bits in n (binary weight).

%F a(2*n) = A000120(n) - a(n).

%F a(2*n+1) = a(n).

%F G.f. satisfies g(x) = (x-1)*g(x^2) + A000120(x^2).

%F G.f.: (1/2)* Sum_{k>=0} x^(2^k)*( (1-x^(2^k))/(1-x) - Prod_{j=0..k-1} x^(2^j)-1 )/( 1-x^(2*2^k ) ).

%F a(2(2^n - 1)) = n. - _Michael S. Branicky_, Apr 03 2021

%e n = 628 = binary 1001110100

%e ^ ^^^ a(n) = 4

%o (PARI) a(n) = my(t=0,ret=0); for(i=0,if(n,logint(n,2)), if(bittest(n,i), ret+=t, t=!t)); ret;

%o (Python)

%o def a(n):

%o b = bin(n)[2:]

%o return sum(bi=='1' and b[i:].count('0')%2==1 for i, bi in enumerate(b))

%o print([a(n) for n in range(87)]) # _Michael S. Branicky_, Apr 03 2021

%Y Cf. A343029, A004718, A000120, A000918 (indices of new highs).

%K nonn,easy

%O 0,7

%A _Kevin Ryde_, Apr 03 2021