A295556 a(n) = 0 for n <= 1; thereafter a(n) = a(floor(n/2)) + a(ceiling(n/2)) + floor(n/2) if n not congruent to 0 mod 4, a(n) = a(n/2-1) + a(n/2+1) + n/2 if n == 0 (mod 4).

0, 0, 1, 2, 4, 5, 7, 9, 11, 13, 15, 17, 20, 22, 25, 27, 30, 32, 35, 37, 40, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 112, 115, 119, 122, 126, 129, 133, 136, 140, 143, 147, 150, 154, 157, 161, 164, 168

Offset

0,4

Links

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

Hsien-Kuei Hwang, S. Janson, T.-H. 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.

Hsien-Kuei Hwang, S. Janson, T.-H. Tsai, 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. See Ex. 7.4.

Maple

f:=proc(n) option remember;
if n <= 1 then 0
elif (n mod 4 = 0) then f(n/2-1)+f(n/2+1)+n/2;
else f(floor(n/2))+f(ceil(n/2))+floor(n/2);
fi; end;
[seq(f(n), n=0..60)];

Mathematica

a[n_] := a[n] = If[Mod[n, 4] == 0, a[n/2 -1] + a[n/2 +1] + n/2, a[Floor[n/2]] + a[Ceiling[n/2]] + Floor[n/2]]; a[0] = a[1] = 0; Array[a, 61, 0] (* Robert G. Wilson v, Dec 10 2017 *)

Crossrefs

Cf. A294456.

Sequence in context: A287175 A027921 A357574 * A047893 A125552 A185546

Adjacent sequences: A295553 A295554 A295555 * A295557 A295558 A295559

Keyword

nonn

Author

N. J. A. Sloane, Nov 26 2017

Status

approved