OFFSET
1,3
REFERENCES
D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 0. See exercise 7.1.2.36 and solution.
R. E. Ladner and M. J. Fischer, Parallel Prefix Computation, JACM 27 (1980) 831-838.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1000
FORMULA
With s = floor(n/2), r = ceiling(n/2) and a(1) = b(1) = 0,
recurrence relation is a(n) = s + b(r) + a(s), b(n) = 2s-1 + a(r).
If n = 2^m then a(n) = 4n+1 - Fibonacci(m+5).
PROG
(PARI)
b(n)={if(n<=1, 0, 2*(n\2) - 1 + a((n+1)\2))}
a(n)={if(n<=1, 0, n\2 + b((n+1)\2) + a(n\2))} \\ Andrew Howroyd, Mar 28 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Frank Ruskey, Mar 22 2009
EXTENSIONS
Terms a(41) and beyond from Andrew Howroyd, Mar 28 2020
STATUS
approved