Is there a fast algorithm to compute the sum of first $n$ terms of the Beatty sequence $e$? That is, I want to compute
$$\lfloor e\rfloor+\lfloor 2e\rfloor+\lfloor 3e\rfloor+\lfloor 4e\rfloor+\lfloor 5e\rfloor+\cdots+\lfloor ne\rfloor$$
for very large $n$. Here $n$ can have up to $4000$ digits.
OEIS: http://oeis.org/A184976
I think that the most reasonable way for tackling such problem is to exploit the fact that the continued fraction of $e$ is well-known, so they are the convergents of the continued fraction of $e$: $$ e=[2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,\ldots] \tag{1} $$ $$ \frac{3}{1},\quad \frac{8}{3},\quad \frac{11}{4},\quad \frac{19}{7},\quad \frac{87}{32},\quad \frac{106}{39},\quad \frac{193}{71},\quad \frac{1264}{465},\quad\ldots\tag{2} $$ and the convergent $\frac{p_m}{q_m}$ allows to exactly compute $\left\lfloor e\right\rfloor+\left\lfloor 2 e\right\rfloor+\ldots+\left\lfloor M e\right\rfloor$ up to $M=q_m$ by just replacing $e$ with its $m$-th convergent.
Anyway, since you should know that every positive integer number can be represented either as $\left\lfloor e a \right\rfloor $ for some $a\in\mathbb{N}$ or as $\left\lfloor \frac{e}{e-1}b\right\rfloor$ for some $b\in\mathbb{N}$, the asymptotic behaviour of $\left\lfloor e\right\rfloor+\left\lfloor 2 e\right\rfloor+\ldots+\left\lfloor n e\right\rfloor$ is pretty clear, and I honestly doubt that you really need to compute such sum exactly. If so, for which purpose?