login
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
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
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^j-1)/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
(SWI-Prolog)
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
Sequence in context: A130260 A276621 A111393 * A062537 A279596 A224458
KEYWORD
nonn,look
AUTHOR
Luc Rousseau, Jan 23 2019
STATUS
approved