A125186 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.

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, 10, 5, 11, 12, 15, 12, 17, 16, 17, 11, 18, 18, 20, 15, 20, 17, 17, 9, 18, 18, 22, 16, 23, 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

Offset

0,4

Comments

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).

Links

Table of n, a(n) for n=0..78.

N. Calkin and H. S. Wilf, Recounting the rationals, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.

S. Klavzar, U. Milutinovic and C. Petr, Stern polynomials, Adv. Appl. Math. 39 (2007) 86-95.

Formula

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.

Example

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).

Maple

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);
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);

Crossrefs

Cf. A125184.

Sequence in context: A227386 A351833 A354967 * A226222 A140473 A115384

Adjacent sequences: A125183 A125184 A125185 * A125187 A125188 A125189

Keyword

nonn,base

Author

Emeric Deutsch, Dec 05 2006

Status

approved