login
A273004
Sum of coefficients in the hereditary representation of n in base 2.
2
0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 4, 5, 6, 7, 7, 8, 9, 10, 8, 9, 10, 11, 11, 12, 13, 14, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14, 15, 9, 10, 11, 12, 12, 13, 14, 15, 13, 14, 15, 16, 16, 17, 18, 19, 6, 7, 8, 9, 9, 10, 11, 12, 10, 11, 12, 13, 13, 14, 15, 16, 10, 11, 12, 13, 13, 14, 15, 16, 14, 15, 16, 17, 17, 18, 19, 20, 11, 12, 13, 14, 14
OFFSET
0,3
COMMENTS
The hereditary representation of a number n in base b is a [possibly empty] sum (possibly represented as a list) of monomials of the form m*b^e (possibly represented as a list [m,e] or as a single number m if e = 0) with coefficients 0 < m < b, and the (strictly increasing) exponents e > 0 recursively again expressed in the same form. Thus 0 = [], 1 = 1*b^0 = [1], b = 1*b^1 = [[1, [1]]] etc.
LINKS
Eric Weisstein's World of Mathematics, Hereditary Representation.
FORMULA
If n = Sum_{j=1..k} 2^e_j where 0 <= e_1 < ... < e_k, then a(n) = k + Sum_{j=1..k} a(e_j). - Pontus von Brömssen, Sep 17 2020
EXAMPLE
266 = 1*2^1 + 1*2^(1+1*2^1) + 1*2^(1*2^(1+1*2^1)) which can be represented as [[1, [1]], [1, [1, [1, [1]]]], [1, [[1, [1, [1, [1]]]]]]], and there are 11 "1"s, therefore a(266) = 11.
MATHEMATICA
a[n_] := a[n] = Total[1 + a /@ Log2[DeleteCases[NumberExpand[n, 2], 0]]]; (* Vladimir Reshetnikov, Dec 21 2023 *)
PROG
(PARI) (hr(n, b=2)=if(1<#n=digits(n, b), my(v=if(n[#n], [n[#n]], [])); forstep(i=#n-1, 1, -1, n[i]&&v=concat(v, [[n[i], hr(#n-i, b)]])); v, n)); (cc(v)=if(type(v)=="t_VEC", sum(i=1, #v, cc(v[i])), v)); a(n)=cc(hr(n))
(Python)
def A273004(n):
s=format(n, 'b')[::-1]
return sum(1+A273004(i) for i in range(len(s)) if s[i]=='1') # Pontus von Brömssen, Sep 17 2020
CROSSREFS
Cf. A056004, A222112, A273005 (base 10 analog).
Sequence in context: A007998 A203899 A202704 * A029931 A350311 A331297
KEYWORD
nonn,base
AUTHOR
M. F. Hasler, May 12 2016
STATUS
approved