A080678 - OEIS

%I #10 Nov 26 2017 21:49:57

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

%T 16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,19,

%U 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

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

%D 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.

%D 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

%p 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;

%Y A generalization of A006166.

%K nonn

%O 0,5

%A _N. J. A. Sloane_, Mar 03 2003