A260812 - OEIS

%I #43 Jan 25 2025 13:55:38

%S 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,

%T 22,26,34,30,38,46,62,12,14,16,20,18,22,26,34,20,24,28,36,32,40,48,64,

%U 22,26,30,38,34,42,50,66,38,46,54,70,62,78,94,126

%N 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.

%H Lorenzo Cococcia, <a href="/A260812/b260812.txt">Table of n, a(n) for n = 0..999</a>

%F 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).

%e a(6) = 10:

%e The binary representation of 6 is 110.

%e   digit    h

%e   1        0        O

%e                   /   \

%e   1        1     O     O

%e                 / \   / \

%e   0        2   O   O O   O

%e                |   | |   |

%e                O   O O   O

%e so the number of edges is 10.

%o (Python)

%o def a(n):

%o     t=1

%o     edges=0

%o     for digit in bin(n)[2:]:

%o         t=t*(int(digit)+1)

%o         edges=edges+t

%o     return edges

%o print([a(n) for n in range(0,100)])

%o (PARI) a(n) = if (n==0, 0, if (n==1, 2, 2^hammingweight(n) + a(n\2))); \\ _Michel Marcus_, Aug 17 2015

%Y Cf. A000120.

%K nonn,base

%O 0,2

%A _Lorenzo Cococcia_, Jul 31 2015