Asymptotics for the sequence A094589

Question

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.

Answer 1

I used a CAS to find a fit similar to your formula and this one works great

$p(n)=\left\lceil 0.5 n^2-\dfrac{n\sqrt n}{3}\right\rceil$

Look at this table

$$ \begin{array}{r|r|r} n & \textit{actual value} & p(n)\\ \hline 1000 & 485930 & 489460 \\ 2000 & 1959566 & 1970186 \\ 3000 & 4424886 & 4445228 \\ 4000 & 7885142 & 7915673 \\ 5000 & 12339310 & 12382149 \\ 6000 & 17787118 & 17845081 \\ 7000 & 24231714 & 24304780 \\ 8000 & 31672274 & 31761487 \\ 9000 & 40107314 & 40215396 \\ 10000 & 49540314 & 49666667 \\ \end{array} $$

Edit

I remade fitting computation considering not sequential data but, just to say, every $500$ and I got a much better approximating function

$p_2(n)=\left\lceil 0.497 n^2-17.183 n\right\rceil$

Look at the new table

$$ \begin{array}{r|r|r} n & \textit{actual value} & p_2(n)\\ \hline 1000 & 485930 & 479817 \\ 2000 & 1959566 & 1953634 \\ 3000 & 4424886 & 4421451 \\ 4000 & 7885142 & 7883268 \\ 5000 & 12339310 & 12339085 \\ 6000 & 17787118 & 17788902 \\ 7000 & 24231714 & 24232719 \\ 8000 & 31672274 & 31670536 \\ 9000 & 40107314 & 40102353 \\ 10000 & 49540314 & 49528170 \\ \end{array} $$

Answer 2

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:

1. 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$

2. 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.