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

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, 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, 1, 1, 2, 1, 2, 0, 1, 2, 0, 3, 4, 0, 1, 1, 2, 1, 1, 2, 3

Offset: 0

Author

Kevin Ryde, Apr 03 2021

Keywords

• nonn
• easy

Comments

See A343029 for further notes.

Examples

			n = 628 = binary 1001110100
                 ^  ^^^      a(n) = 4
		

Links

• Kevin Ryde, Table of n, a(n) for n = 0..8192

Crossrefs

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

Programs

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;

Python

def a(n):
  b = bin(n)[2:]
  return sum(bi=='1' and b[i:].count('0')%2==1 for i, bi in enumerate(b))
print([a(n) for n in range(87)]) # Michael S. Branicky, Apr 03 2021

Formula

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

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

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

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

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

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

a(2(2^n - 1)) = n. - Michael S. Branicky, Apr 03 2021