Need a help to find the series formula for A005836 I need a help in finding the series formula for the Sequence $A005836$
$a(1)=0$
$a(2)=1$
$a(3)=3$
$a(4)=4$
$a(5)=9$
so series of above sequence would be
$A(1)=0$
$A(2)=1$
$A(3)=4$
$A(4)=8$
$A(5)=17$
where $$A(n)=a(1)+a(2)+a(3)+........+a(n)$$
the value of $n$ can be up to $10^{18}$.
So I am interested in finding the nth term of above series or the algorithm to compute $A(n)$ in an efficient way. Can someone help me with this.
Thanks
 A: $a(n)$ is defined such that it equals the ternary reading of the binary form of n. So, for example:
$$a(5) = a(101_2) = 101_3 = 1*3^0+0*3^1+1*3^2 = 10$$
Before continuing, I should note that I'm beginning the sequence at $n=0$ whereas you began at $n=1$. With that out of the way, we now look at how to sum these. Suppose we want $A(5)$. We just sum up the value (0 or 1) in each "column" and multiply them by the respective value of the column (power of 3). So, we have 0 through 5: 
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
We count in the "ones" column, a total of 3, in the "twos" column, a total of 2, and in the "fours" column, a total of 2. So we evaluate $A(5)$ as:
$$A(5) = 3*3^0+2*3^1+2*3^2 = 27$$
Now counting in each column is a little tricky. We'll denote $C(n,m)$ to sum up the digits in the mth column of all numbers up to n. This is:
$$C(n,m) = (n\backslash 2^{m+1}) * 2^m + f((n \bmod 2^{m+1})-2^m+1)$$
Where $f(x)$ returns $x$ if $x>0$ and returns $0$ otherwise. Now we just put together $A(n)$ from this as:
$$A(n) = \sum_{m=0}^{bits} C(n,m)*3^m$$

To see this in action, suppose we want to find $A(1000)$. We have:
$$\{(m, C(n,m))\} = \{(0,500), (1,500), (2,500), (3,497), (4,496), (5,489), (6,489),(7,489),(8,489),(9,489)\}$$
It might be worth noting that each of the changes in value corresponds to a change in the digit of 1000 in binary, $1111101000_2$. Anyway, now we just substitute this into the summation and find:
$$A(1000)=14\space 438\space 162$$
A: I suspect there is a relatively simple recursion with $O(\log n)$ complexity:
$$A(2^n+b) = (3^n-1)2^{n-2}+3^n b+A(b)$$ for $0 \le b \lt 2^b$ and with $A(0)=0$, where the $(3^n-1)2^{n-2}$ represents $A(2^n)$, the $3^n b$ represents the leading ternary digits of the final $b$ terms, and the $A(b)$ representing the other ternary digits of the final $b$ terms
So to take Hyrum Hammon's example


*

*$A(1000)=A(2^9+488)= (3^9-1)\times 2^7 +3^9 \times 488+A(488)$

*$A(488)=A(2^8+232)= (3^8-1)\times 2^6 +3^8 \times 232+A(232)$

*$A(232)=A(2^7+104)= (3^7-1)\times 2^5 +3^7 \times 104+A(104)$

*$A(104)=A(2^6+40)= (3^6-1)\times 2^4 +3^6 \times 40+A(40)$

*$A(40)=A(2^5+8)= (3^5-1)\times 2^3 +3^5 \times 8+A(8)$

*$A(8)=A(2^3+0)= (3^3-1)\times 2^1 +3^3 \times 0+A(0)$

*$A(0)=0$


Adding these up gives $A(1000)=14408732$ as Hyrum Hammon also found. 
In general $A(n)$ seems to be between $0.24$ and $0.29$ times $n^{\log_2 6}$ for $n \gt 4$ and $A(10^{18})$ is likely to be of the order of $9 \times 10^{45}$ 
