A323665 - OEIS

%I #14 Jan 24 2019 17:50:59

%S 1,2,2,3,3,3,3,3,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,4,5,5,5,5,5,5,5,4,5,5,

%T 5,6,6,6,6,5,6,6,6,6,6,6,6,5,5,6,6,6,6,6,6,5,6,6,6,6,6,6,6,4,5,6,6,6,

%U 6,6,6,6,7,7,7,7,7,7,7,6,6,7,7,7,7,7,7,6,7,7

%N a(n) is the number of vertices in the binary tree the root of which is assigned the value n and built recursively by the rule: write node's value as (2^c)*(2k+1); if c>0, create a left child with value c; if k>0, create a right child with value k.

%C Mirroring (left <--> right) the tree corresponding to n and computing back a number gives rise to sequence A323710. Swapping the left and right subtrees of the root of the tree corresponding to n and computing back a number gives rise to sequence A117303.

%H Luc Rousseau, <a href="/A323665/b323665.txt">Table of n, a(n) for n = 1..10000</a>

%e 100 = (2^2)*(2*12+1) and recursively, 2 = (2^1), 12 = (2^2)*(2*1+1). We then have the following binary tree representation:

%e      100                                         o

%e      / \                                        / \

%e     2  12                                      o   o

%e    /   / \              or more simply        /   / \

%e   1   2   1                                  o   o   o

%e      /                                          /

%e     1                                          o

%e 7 vertices, so a(100) = 7.

%p a:= proc(n) option remember; `if`(n=0, 0, (j->

%p       1+a(j)+a((n/2^j-1)/2))(padic[ordp](n, 2)))

%p     end:

%p seq(a(n), n=1..100);  # _Alois P. Heinz_, Jan 23 2019

%t nEdges[n_] :=

%t If[n == 0, 0,

%t   Module[{c, xx, k}, c = IntegerExponent[n, 2]; xx = n/2^c;

%t    k = (xx - 1)/2;

%t    Boole[c != 0]*(1 + nEdges[c]) + Boole[k != 0]*(1 + nEdges[k])]]

%t a[n_] := nEdges[n] + 1

%t Table[a[n], {n, 1, 87}]

%o (SWI-Prolog)

%o v(M, V) :-

%o         R is mod(M, 2),

%o         R = 1 -> (V = 0) ; (N is M / 2, v(N, W), V is 1 + W).

%o a(N, S, R) :- N = 0, !, S = x, R = 0.

%o a(N, S, R) :-

%o         v(N, C),

%o         X is (N / 2^C),

%o         K is (X - 1) / 2,

%o         a(C, SC, RC),

%o         a(K, SK, RK),

%o         S = o(SC, SK),

%o         R is 1 + RC + RK.

%o main :- forall(between(1,87,N),(a(N,_,A),maplist(write,[A,', ']))).

%Y Cf. A117303, A323710.

%K nonn,look

%O 1,2

%A _Luc Rousseau_, Jan 23 2019