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
Examples
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
so the number of edges is 10.
Links
- Lorenzo Cococcia, Table of n, a(n) for n = 0..999
Crossrefs
Cf. A000120.
Programs
-
PARI
a(n) = if (n==0, 0, if (n==1, 2, 2^hammingweight(n) + a(n\2))); \\ Michel Marcus, Aug 17 2015
-
Python
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)])