A330072 a(n) is the sum of all integers whose binary representation is contained in the binary representation of n (with multiplicity).

0, 1, 3, 5, 7, 10, 13, 16, 15, 19, 24, 28, 29, 33, 38, 42, 31, 36, 43, 48, 52, 57, 64, 69, 61, 66, 73, 78, 82, 87, 94, 99, 63, 69, 78, 84, 91, 97, 106, 112, 108, 114, 123, 129, 136, 142, 151, 157, 125, 131, 140, 146, 153, 159, 168, 174, 170, 176, 185, 191, 198

Offset: 0

Author

Tonio Kettner, Nov 30 2019

Keywords

• nonn
• base

Examples

			For n = 5: 5 in binary is 101, so a(n) = 101 + 10 + 01 + 1 + 0 + 1 in binary, which is 5 + 2 + 1 + 1 + 0 + 1 = 10.
		

Crossrefs

Cf. A007088, A005187, A049802, A078823, A225580 (base-10 version).

Programs

Mathematica

a[n_] := Block[{d = IntegerDigits[n, 2]}, Sum[FromDigits[Take[d, {i, j}], 2], {j, Length[d]}, {i, j}]]; Array[a, 61, 0] (* Giovanni Resta, Dec 02 2019 *)

Python

def bitlist(n):
    output = []
    while n != 0:
        output.append(n % 2)
        n //= 2
    return output
#converts a number into a list of the digits in binary reversed
def bitsum(bitlist):
    output = 0
    for bit in bitlist:
        if bit == 1:
            output += 1
    return output
#gives the cross sum of a bitlist
def a(bitlist):
    output = 0
    l = len(bitlist)
    for x in range(l):
        output += bitlist[x] * (l - x) * (2**(x + 1) - 1)
    return output
#to get the first 60 numbers of the sequence, write:
for x in range(0, 60):
    print(a(bitlist(x)))

Python

def a(n):
    b = n.bit_length()
    return sum((n//2**i) % (2**j) for i in range(b+1) for j in range(b-i+1))
# David Radcliffe, May 14 2025

Formula

a(2^k) = 2^(k+1)-1.

a(2^k-1) = (8*2^k-8-5*k-k^2)/2. - Giovanni Resta, Dec 02 2019

From David Radcliffe, May 14 2025: (Start)

a(n) = Sum_{i=0..b} Sum_{j=0..b-i} ([n/2^i] mod 2^j) where b is the bit length of n.

a(n) - 3a([n/2]) + 2a([n/4]) = A070939(n) if n is odd, 0 otherwise. (End)