|
| |
|
|
A343029
|
|
Number of 1-bits in the binary expansion of n which have an even number of 0-bits at less significant bit positions.
|
|
5
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
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) ).
|
|
|
EXAMPLE
|
n = 860 = binary 1101011100
^^ ^^^ a(n) = 5
|
|
|
PROG
|
(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))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
