OFFSET
1,2
COMMENTS
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^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
KEYWORD
nonn,look
AUTHOR
Luc Rousseau, Jan 23 2019
STATUS
approved