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

0, 1, 0, 2, 1, 1, 0, 3, 0, 2, 1, 2, 2, 1, 0, 4, 1, 1, 0, 3, 1, 2, 1, 3, 0, 3, 2, 2, 3, 1, 0, 5, 0, 2, 1, 2, 2, 1, 0, 4, 1, 2, 1, 3, 2, 2, 1, 4, 2, 1, 0, 4, 1, 3, 2, 3, 0, 4, 3, 2, 4, 1, 0, 6, 1, 1, 0, 3, 1, 2, 1, 3, 0, 3, 2, 2, 3, 1, 0, 5, 1, 2, 1, 3, 2, 2, 1

Offset: 0

Author

Kevin Ryde, Apr 03 2021

Keywords

• nonn
• easy

Comments

Each term of Per Nørgård's infinity sequence (A004718) is a sum of +1 or -1 for each 1-bit of n according as that bit has an even or odd number of 0-bits below it. The present sequence counts the "+1" bits and A343030 counts the "-1" bits so that A004718(n) = a(n) - A343030(n).

a(n) and A343030(n) can be iterated together by pair [a(n-1)-t, A343030(n-1)+1] -> [a(n), A343030(n)] if t odd or [A343030(n), a(n)] if t even, where t = A007814(n) is the 2-adic valuation of n.

In the generating function sum below, k is a bit position (0 for the least significant bit). 1/2 of each sum term gives 1*x^n at those n where bit k of n is 1 and has an even number of 0 bits below. The product part is like the +-1 Thue-Morse sequence A106400, but only the k lowest bits, and each product term negated so parity of 0-bits. These +-1 are turned into 2 or 0 and shifted and repeated in blocks which are where bit k of n is 1.

Examples

			n = 860 = binary 1101011100
                 ^^   ^^^    a(n) = 5
		

Links

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

Crossrefs

Cf. A343030, A004718, A000225 (indices of new highs).

Cf. A000120, A007814, A106400.

Programs

PARI

a(n) = my(t=1,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==0 for i, bi in enumerate(b))
print([a(n) for n in range(87)]) # Michael S. Branicky, Apr 03 2021

Formula

a(n) = A004718(n) + A343030(n).

a(n) = A000120(n) - A343030(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) + 1.

G.f. satisfies g(x) = (x-1)*g(x^2) + A000120(x^2) + x/(1-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^n - 1) = n. - Michael S. Branicky, Apr 03 2021