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
KEYWORD
nonn,base
AUTHOR
M. F. Hasler, May 12 2016
STATUS
approved