|
%I #41 Jul 27 2014 12:24:22
%S 0,0,1,0,0,1,1,0,0,0,0,1,0,1,2,0,0,0,0,0,0,0,0,1,0,0,1,1,0,2,1,0,0,0,
%T 0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,1,0,0,1,2,0,1,2,0,0,0,0,0,
%U 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0
%N Write n>=1 as either n=2^k-2^r with 0 <= r <= k-1, in which case a(2^k-2^r)=wt(k-r-1), or as n=2^k-2^r+j with 2 <= r <= k-1, 1 <= j < 2^r-1, in which case a(2^k-2^r+j)=a(j)*wt(k-r-1) (where wt(i) = A000120(i)).
%C Other sequences defined by a recurrence of this class (see the Formula and Maple sections) include A245180, A245195, A048896, A245536, A038374.
%F This is an example of a class of sequences defined by the following recurrence.
%F We first choose a sequence G = [G(0), G(1), G(2), G(3), ...], which are the terms that will appear at the ends of the blocks: a(2^k-1) = G(k-1), and we also choose a parameter m (the "multiplier"). Then the recurrence (this defines a(1), a(2), a(3), ...) is:
%F a(2^k-2^r)=G(k-r-1) if 0 <= r <= k-1, a(2^k-2^r+j)=m*a(j)*G(k-r-1) if 2 <= r <= k-1, 1 <= j < 2^r-1.
%F To help apply the recurrence, here are the values of k,r,j for the first few values of n (if n=2^k-2^r we set j=0, although it is not used):
%F n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
%F k: 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4
%F r: 0 1 0 2 2 1 0 3 3 3 3 2 2 1 0
%F j: 0 0 0 0 1 0 0 0 1 2 3 0 1 0 0
%F --------------------------------------------------
%F n: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
%F k: 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
%F r: 4 4 4 4 4 4 4 4 3 3 3 3 2 2 1 0
%F j: 0 1 2 3 4 5 6 7 0 1 2 3 0 1 0 0
%F --------------------------------------------------
%F In the present example G(n) = wt(n) and m=1.
%e May be arranged into blocks of lengths 1,2,4,8,...:
%e 0,
%e 0, 1,
%e 0, 0, 1, 1,
%e 0, 0, 0, 0, 1, 0, 1, 2,
%e 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 2, 1,
%e 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 2, 0, 1, 2,
%e ...
%p Maple code for this sequence:
%p wt := proc(n) local w, m, i; w := 0; m := n; while m > 0 do i := m mod 2; w := w+i; m := (m-i)/2; od; w; end:
%p G:=[seq(wt(n),n=0..30)];
%p m:=1;
%p f:=proc(n) option remember; global m,G; local k,r,j,np;
%p k:=1+floor(log[2](n)); np:=2^k-n;
%p if np=1 then r:=0; j:=0; else r:=1+floor(log[2](np-1)); j:=2^r-np; fi;
%p if j=0 then G[k-r]; else m*G[k-r]*f(j); fi;
%p end;
%p [seq(f(n),n=1..120)];
%p # Maple code for the general recurrence:
%p G:=[seq(wt(n),n=0..30)]; # replace this by a list G=[G(0), G(1), G(2), ...], remembering that you have to tell Maple G[1] to get G(0), G[2] to get G(1), etc.
%p m:=1; # replace this by the correct multiplier
%p f:=proc(n) option remember; global m,G; local k,r,j,np;
%p k:=1+floor(log[2](n)); np:=2^k-n;
%p if np=1 then r:=0; j:=0; else r:=1+floor(log[2](np-1)); j:=2^r-np; fi;
%p if j=0 then G[k-r-1+1]; else m*G[k-r-1+1]*f(j); fi;
%p end;
%p [seq(f(n),n=1..120)];
%p # If G(n) = wt(n) and m=1 we get the present sequence
%p # If G(n) = A083424(n) and m=1 we get A245537
%p # If G(n) = A083424(n) and m=2 we get A245538
%p # If G(n) = A083424(n) and m=4 we get A245539
%p # If G(n) = A083424(n) and m=8 we get A245180 (and presumably A160239)
%p # If G(n) = n (n>=0) and m=1 we get A245536
%p # If G(n) = n+1 (n>=0) and m=1 we get A038374
%p # If G(n) = (n+1)(n+2)/2 (n>=0) and m=1 we get A245541
%p # If G(n) = (n+1)(n+2)/2 (n>=0) and m=2 we get A245547
%p # If G(n) = 2^n (n>=0) and m=1 we get A245195 (= 2^A014081)
%p # If G(n) = 2^n (n>=0) and m=2 we get A048896
%Y Cf. A000120, A160239, A245180, A245195, A014081, A048896, A038374, A245536, A245537, A245538, A245539, A048896, A245547.
%K nonn,tabf
%O 1,15
%A _N. J. A. Sloane_, Jul 25 2014
|
