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

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), 85-94.

Hsien-Kuei 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/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer 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((n-1)/4)+f((n-1)/4+1); elif n mod 4 = 2 then 2*f((n-2)/4)+2*f((n-2)/4+1); else f((n-3)/4)+3*f((n-3)/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