A294456 a(1)=0, a(2)=1; thereafter a(n) = a(floor(n/2)) + a(ceiling(n/2)) + 2.

0, 1, 3, 4, 6, 8, 9, 10, 12, 14, 16, 18, 19, 20, 21, 22, 24, 26, 28, 30, 32, 34, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116

Offset

1,3

Links

Robert Israel, Table of n, a(n) for n = 1..10000

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; ACM Transactions on Algorithms, accepted for publication (July, 2017).

Formula

G.f. g(x) satisfies g(x) = (x^2+x^3)/(1-x) + (x + 2 + 1/x)*g(x^2). - Robert Israel, Nov 26 2017

Maple

f:= proc(n) option remember;
  procname(floor(n/2)) + procname(ceil(n/2))+2 end proc:
f(1):= 0: f(2):= 1:
map(f, [$1..200]); # Robert Israel, Nov 26 2017

Prog

(PARI) first(n) = { my(res = vector(n)); res[1] = 0; res[2] = 1; for(i = 3, n, res[i] = res[floor(i/2)] + res[ceil(i/2)] + 2); res; } \\ Iain Fox, Nov 26 2017

Crossrefs

Sequence in context: A183867 A182829 A112800 * A062969 A175035 A025063

Adjacent sequences: A294453 A294454 A294455 * A294457 A294458 A294459

Keyword

nonn

Author

N. J. A. Sloane, Nov 26 2017

Status

approved