

A080678


Rooted at a(0)=0 and a(1)=a(2)=a(3)=1, 4 cases of index mod 4: a(4n)=4*a(n), a(4n+1)= 3*a(n)+a(n+1), a(4n+2) = 2*a(n)+2*a(n+1), and a(4n+3) = a(n)+3*a(n+1).


0



0, 1, 1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 7, 10, 13, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


REFERENCES

J. Arkin, D. C. Arney, L. S. Dewald and W. E. Ebel, Jr., Families of recursive sequences, J. Rec. Math., 22 (No. 22, 1990), 8594.
HsienKuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wpcontent/files/2016/12/aathhrr1.pdf. Also Exact and Asymptotic Solutions of a DivideandConquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585


LINKS

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


MAPLE

f := proc(n) if n=0 then RETURN(0); fi; if n<=3 then RETURN(1); fi; if n mod 4 = 0 then 4*f(n/4) elif n mod 4 = 1 then 3*f((n1)/4)+f((n1)/4+1); elif n mod 4 = 2 then 2*f((n2)/4)+2*f((n2)/4+1); else f((n3)/4)+3*f((n3)/4+1); fi; end;


CROSSREFS

A generalization of A006166.
Sequence in context: A258199 A290205 A066014 * A096300 A333534 A035672
Adjacent sequences: A080675 A080676 A080677 * A080679 A080680 A080681


KEYWORD

nonn


AUTHOR

N. J. A. Sloane, Mar 03 2003


STATUS

approved



