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
Keywords
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
Crossrefs
A generalization of A006166.
Programs
-
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;