2
$\begingroup$

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.

  • 0
    @HSE: Ok see if you get my solution. I occasionally make typographical errors so please tell me if there are any.2011-12-30

1 Answers 1

0

Hint (as I don´t have time now to work it all out)

This is related to OEIS A053646 (distance to nearest power of 2) and various other sequences linked from there.

In particular, if you look at $2a(n) - 3(n-1)$, you should get something very similar to that OEIS sequence, perhaps with an offset. That should be enough to find the sum as the weighted sum or difference of two arithmentic progressions depending on whether the nearest power of 2 is above or below.

It might be easier if you shifted all your terms and formulae down one.

  • 0
    My answer was a reply to the original version of the partial sums of $1, 2, 3, 5, 6, 8, 10, 11, 12, 14, 16, 18, 20, 21, \dots$2011-12-30