A344985 Sum of imbalance of all initial subsequences of the binary representation of n.

1, 1, 3, 2, 2, 4, 6, 4, 2, 2, 4, 4, 6, 8, 10, 7, 5, 3, 3, 3, 3, 5, 7, 5, 5, 7, 9, 9, 11, 13, 15, 11, 9, 7, 5, 5, 3, 3, 5, 5, 3, 3, 5, 5, 7, 9, 11, 7, 5, 5, 7, 7, 9, 11, 13, 9, 11, 13, 15, 15, 17, 19, 21, 16, 14, 12, 10, 10, 8, 6, 6, 8, 6, 4, 4, 4, 4, 6, 8, 8

Offset

1,3

Comments

The imbalance of a sequence of zeros and ones is given as the absolute value of the difference between the number of zeros and the number of ones (that is, the absolute value of A037861 if n is the sequence A007088).

Links

Alois P. Heinz, Table of n, a(n) for n = 1..16384

Formula

a(n) = a(floor(n/2)) + |A037861(n)|. - R. J. Mathar, Jul 07 2021

Example

9 in binary is 1001. The imbalance of 1 is 1, the imbalance of 10 is 0, the imbalance of 100 is 1 and the imbalance of 1001 is 0. thus a(9)=1+0+1+0=2.

Maple

imbal := proc(L)
     abs(numboccur(0, L) - numboccur(1, L))
end proc:
A344985 := proc(n)
    dgs := ListTools[Reverse](convert(n, base, 2)) ;
    add(imbal( dgs[1..l]), l=1..nops(dgs)) ;
end proc: # R. J. Mathar, Jul 07 2021
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 0, a(iquo(n, 2))+
      (l-> abs(add(1-2*i, i=l)))(Bits[Split](n)))
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, Jul 07 2021

Prog

(PARI) a(n) = my(b=binary(n)); sum(k=1, #b, abs(sum(j=1, k, b[j]==1) - sum(j=1, k, b[j]==0))); \\ Michel Marcus, Jun 09 2021
(Python)
def A344985(n):
    s, c, b = bin(n)[2:], 0, 0
    for x in s:
        b += 1 if x == '1' else -1
        c += abs(b)
    return c # Chai Wah Wu, Jul 07 2021

Crossrefs

Cf. A007088, A037861.

Sequence in context: A298904 A308194 A245572 * A325596 A254876 A249159

Adjacent sequences: A344982 A344983 A344984 * A344986 A344987 A344988

Keyword

nonn,base,look,easy

Author

André Engels, Jun 04 2021

Status

approved