A273004 - OEIS

%I #30 Dec 22 2023 03:59:37

%S 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,

%T 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,

%U 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

%N Sum of coefficients in the hereditary representation of n in base 2.

%C 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.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HereditaryRepresentation.html">Hereditary Representation.</a>

%F 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

%e 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.

%t a[n_] := a[n] = Total[1 + a /@ Log2[DeleteCases[NumberExpand[n, 2], 0]]]; (* _Vladimir Reshetnikov_, Dec 21 2023 *)

%o (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))

%o (Python)

%o def A273004(n):

%o   s=format(n,'b')[::-1]

%o   return sum(1+A273004(i) for i in range(len(s)) if s[i]=='1') # _Pontus von Brömssen_, Sep 17 2020

%Y Cf. A056004, A222112, A273005 (base 10 analog).

%K nonn,base

%O 0,3

%A _M. F. Hasler_, May 12 2016