cp's OEIS Frontend

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

%I A343029 #10 Apr 17 2021 19:51:05
%S A343029 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,
%T A343029 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,
%U A343029 1,2,1,3,0,3,2,2,3,1,0,5,1,2,1,3,2,2,1
%N A343029 Number of 1-bits in the binary expansion of n which have an even number of 0-bits at less significant bit positions.
%C A343029 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).
%C A343029 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.
%C A343029 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.
%H A343029 Kevin Ryde, <a href="/A343029/b343029.txt">Table of n, a(n) for n = 0..8192</a>
%F A343029 a(n) = A004718(n) + A343030(n).
%F A343029 a(n) = A000120(n) - A343030(n), where A000120 is the number of 1-bits in n (binary weight).
%F A343029 a(2*n) = A000120(n) - a(n).
%F A343029 a(2*n+1) = a(n) + 1.
%F A343029 G.f. satisfies g(x) = (x-1)*g(x^2) + A000120(x^2) + x/(1-x^2).
%F A343029 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 A343029 a(2^n - 1) = n. - _Michael S. Branicky_, Apr 03 2021
%e A343029 n = 860 = binary 1101011100
%e A343029                  ^^   ^^^    a(n) = 5
%o A343029 (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;
%o A343029 (Python)
%o A343029 def a(n):
%o A343029   b = bin(n)[2:]
%o A343029   return sum(bi=='1' and b[i:].count('0')%2==0 for i, bi in enumerate(b))
%o A343029 print([a(n) for n in range(87)]) # _Michael S. Branicky_, Apr 03 2021
%Y A343029 Cf. A343030, A004718, A000225 (indices of new highs).
%Y A343029 Cf. A000120, A007814, A106400.
%K A343029 nonn,easy
%O A343029 0,4
%A A343029 _Kevin Ryde_, Apr 03 2021