%I #16 Sep 07 2024 08:35:46
%S 0,1,1,2,2,3,3,3,4,5,5,5,6,6,6,4,7,8,9,8,10,10,10,7,11,11,12,9,12,10,
%T 10,5,11,12,15,12,17,16,17,11,18,18,20,15,20,17,17,9,18,18,22,16,23,
%U 20,21,12,21,19,22,14,20,15,15,6,16,17,23,17,27,24,27,16,29,28,33,23,33,27,28
%N Number of digits 1 in all hyperbinary representations of n. A hyperbinary representation of a nonnegative integer n is a representation of n as a sum of powers of 2, each power being used at most twice.
%C a(n) = dB(n+1,t)/dt|_{t=1}, where B(n,t) are the Stern polynomials, defined by B(0,t)=0, B(1,t)=1, B(2n,t)=tB(n,t), B(2n+1,t)=B(n+1,t)+B(n,t) for n>=1 (see S. Klavzar et al. and A125184).
%H N. Calkin and H. S. Wilf, <a href="http://www.jstor.org/stable/2589182">Recounting the rationals</a>, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.
%H S. Klavzar, U. Milutinovic, and C. Petr, <a href="http://dx.doi.org/10.1016/j.aam.2006.01.003">Stern polynomials</a>, Adv. Appl. Math. 39 (2007) 86-95.
%F a(0)=0, a(1)=0, a(2)=1, a(2n+1)=a(n)+a(n+1), a(4n)=2a(2n)-a(n), a(4n+2)=a(2n+2)+a(2n) for n>=1.
%e a(8)=4 because the hyperbinary representations of 8 are 200 (=2*2^2+0*2^1+0*2^0), 120 (=1*2^2+2*2^1+0*2^0), 1000 (=1*2^3+0*2^2+0*2^1+0*2^0) and 112 (=1*2^2+1*2^1+2*1^0), having a total of 0+1+1+2=4 digits 1 (see S. Klavzar et al. Table 1).
%p a[0]:=0: a[1]:=0: a[2]:=1: for n from 1 to 50 do a[2*n+1]:=a[n]+a[n+1]: a[4*n]:=2*a[2*n]-a[n]: a[4*n+2]:=a[2*n+2]+a[2*n] od: seq(a[n+1],n=0..100);
%p B:=proc(n) if n=0 then 0 elif n=1 then 1 elif n mod 2 = 0 then t*B(n/2) else B((n+1)/2)+B((n-1)/2) fi end: seq(subs(t=1,diff(B(n+1),t)),n=0..100);
%t B[0, _] = 0; B[1, _] = 1; B[n_, t_] := B[n, t] = If[EvenQ[n], t*B[n/2, t], B[1 + (n-1)/2, t] + B[(n-1)/2, t]]; a[n_] := D[B[n+1, t], t] /. t -> 1; Table[a[n], {n, 0, 78}] (* _Jean-François Alcover_, Sep 07 2024, after 2nd Maple program *)
%Y Cf. A125184.
%K nonn,base
%O 0,4
%A _Emeric Deutsch_, Dec 05 2006