Possible Duplicate:
Formula for the summation of this sequence?
$a(2n)=a(n)+a(n+1)$ $a(2n+1)=2a(n+1)$ $n>1$
Outputs $1, 2, 4, 6, 10, 12, 16, 20, 22$ etc, but I am trying to find a formula that finds the summation of these terms. In OEIS, this sequence is https://oeis.org/A005942
I can generate the terms fine but summing them up for large N takes forever. I'd like to find a way to handle this in O(lg n) time if there is a possible way to do it, mathematically speaking.