Asymptotics for the sequence A094589 Consider the integer sequence
$$1,2,4,6,10,14,20,26,32,38,48,...$$
Defined here
http://oeis.org/A094589
Im looking for good asymptotics.
And proofs of them.
I considered $\frac{n(n-\sqrt n)}{2}$ but that appears not So good. Not even sure If it is a main term ?
Any asymptotic ( in closed form ) that is better is helpful.

I assume there is a fast way to compute values of this sequence with large index, without requiring most of the previous values. Just a feeling.
 A: It doesn't look like the sequence $a_n$ will have any nice asymptotic formula.
By studying the values of $a_n$ for $n$ upto $10^6$, $a_n$ seems to
contain some non-trivial oscillation with slowing increasing period. It is sort of
hard to describe what it is without a picture. We will back to this later.
Using some hand-waving argument, I have approximated the original difference equation by an ODE:
$$a_{n+1} - a_n = a\left(\lfloor a^{-1}(n) \rfloor\right)
\quad\leadsto\quad
a'(n) = n - \frac13 - \frac12 a'(a^{-1}(n))
$$
To first and second order, this lead to following two approximations of $a_n$:
$$
a^{[1]}_n = \frac{n}{2}\left(n -\frac{2\sqrt{2}}{3}\sqrt{n}\right)
\quad\text{ AND }\quad
a^{[2]}_n = n\left(\frac{n}{2}-\frac23\left(\frac{n}{2}\right)^{\frac12} +\frac{2}{15}\left(\frac{n}{2}\right)^{\frac14} - \frac16\right)
$$
To compare them with the approximation proposed in question,
$$a^{[0]}_n = \frac{n}{2}\left(n - \sqrt{n}\right)$$
I have plotted their errors in a single picture:

In above picture,


*

*the red curve is $\frac{1}{10n}(a_n - a^{[0]}_n)$,

*the green curve is $\frac{1}{n}(a_n - a^{[1]}_n)$,

*the blue curve is $\frac{1}{n}(a_n - a^{[2]}_n)$,


There are two observations one can make:


*

*The red curve and green curve has approximately the same size. Since the red curve represent errors of original approximation scaled down by a factor of ten, approximation $a^{[1]}_n$ is about an order of magnitude better than $a^{[0]}_n$

*Unlike the red and green curves which drift away from $0$, 
the leading behavior of the blue curve is some cusp like oscillation, the amplitude doesn't seem to die down as $n$ increases and the period of seems to grow very slowly.
What this means is if one want to go beyond approximation $a^{[2]}_n$,
one need to include corrections other than powers of $n$. 
A classical asymptotic expansion purely in terms of powers of $n$ and $\log(n)$ won't work.
