A260812 a(n) is the number of edges in a rooted 2-ary tree built from the binary representation of n: each vertex at level i (i=0,...,floor(log_2(n))) has two children if the i-th most significant bit is 1 and one child if the i-th bit is 0.

1, 2, 4, 6, 6, 8, 10, 14, 8, 10, 12, 16, 14, 18, 22, 30, 10, 12, 14, 18, 16, 20, 24, 32, 18, 22, 26, 34, 30, 38, 46, 62, 12, 14, 16, 20, 18, 22, 26, 34, 20, 24, 28, 36, 32, 40, 48, 64, 22, 26, 30, 38, 34, 42, 50, 66, 38, 46, 54, 70, 62, 78, 94, 126

Offset

0,2

Links

Lorenzo Cococcia, Table of n, a(n) for n = 0..999

Formula

a(0) = 1, a(1) = 2, a(2*n) = 2^A000120(2*n) + a(n), a(2*n+1) = 2^A000120(2*n+1) + a(n).

Example

a(6) = 10:
The binary representation of 6 is 110.
digit    h
1        0        O
                /   \
1        1     O     O
              / \   / \
0        2   O   O O   O
             |   | |   |
             O   O O   O
thus number of edges is 10.

Prog

(Python 3)
def a(n):
    t=1
    edges=0
    for digit in bin(n)[2:]:
        t=t*(int(digit)+1)
        edges=edges+t
    return edges
print([a(n) for n in range(0, 100)])
(PARI) a(n) = if (n==0, 0, if (n==1, 2, 2^hammingweight(n) + a(n\2))); \\ Michel Marcus, Aug 17 2015

Crossrefs

Cf. A000120.

Sequence in context: A099188 A085271 A347376 * A003972 A023853 A056526

Adjacent sequences: A260809 A260810 A260811 * A260813 A260814 A260815

Keyword

nonn,base

Author

Lorenzo Cococcia, Jul 31 2015

Status

approved