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

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}$ 
