

A323665


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.


2



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, 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, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 6, 7, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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.


LINKS

Luc Rousseau, Table of n, a(n) for n = 1..10000


EXAMPLE

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:
100 o
/ \ / \
2 12 o o
/ / \ or more simply / / \
1 2 1 o o o
/ /
1 o
7 vertices, so a(100) = 7.


MAPLE

a:= proc(n) option remember; `if`(n=0, 0, (j>
1+a(j)+a((n/2^j1)/2))(padic[ordp](n, 2)))
end:
seq(a(n), n=1..100); # Alois P. Heinz, Jan 23 2019


MATHEMATICA

nEdges[n_] :=
If[n == 0, 0,
Module[{c, xx, k}, c = IntegerExponent[n, 2]; xx = n/2^c;
k = (xx  1)/2;
Boole[c != 0]*(1 + nEdges[c]) + Boole[k != 0]*(1 + nEdges[k])]]
a[n_] := nEdges[n] + 1
Table[a[n], {n, 1, 87}]


PROG

(SWIProlog)
v(M, V) :
R is mod(M, 2),
R = 1 > (V = 0) ; (N is M / 2, v(N, W), V is 1 + W).
a(N, S, R) : N = 0, !, S = x, R = 0.
a(N, S, R) :
v(N, C),
X is (N / 2^C),
K is (X  1) / 2,
a(C, SC, RC),
a(K, SK, RK),
S = o(SC, SK),
R is 1 + RC + RK.
main : forall(between(1, 87, N), (a(N, _, A), maplist(write, [A, ', ']))).


CROSSREFS

Cf. A117303, A323710.
Sequence in context: A130260 A276621 A111393 * A062537 A279596 A224458
Adjacent sequences: A323662 A323663 A323664 * A323666 A323667 A323668


KEYWORD

nonn,look


AUTHOR

Luc Rousseau, Jan 23 2019


STATUS

approved



