How to find $\sum_{i=1}^n\left\lfloor i\sqrt{2}\right\rfloor$ A001951 A Beatty sequence: a(n) = floor(n*sqrt(2)). A001951 A Beatty sequence: a(n) = floor(n*sqrt(2)).
If $n = 5$ then
$$\left\lfloor1\sqrt{2}\right\rfloor+ \left\lfloor2\sqrt{2}\right\rfloor + \left\lfloor3\sqrt{2}\right\rfloor +\left\lfloor4 \sqrt{2}\right\rfloor+ \left\lfloor5\sqrt{2}\right\rfloor
= 1+2+4+5+7 = 19$$
Sequence from $1$ to $20$ is:
$S=\{1,2,4,5,7,8,9,11,12,14,15,16,18,19,21,22,24,25,26,28\}$
I want to find answer for $n = 10^{100}$.

Let $S(\alpha,n) = \sum_{k=1}^n \lfloor \alpha k \rfloor$ for $\alpha$ some irrationnal positive number.
if $\alpha \ge 2$ we let $\beta = \alpha-1$ and you get
$S(\alpha,n) = S(\beta,n) + \sum_{k=1}^n k \\
= S(\beta,n) + n(n+1)/2$
if $1 < \alpha < 2$, there is a theorem that says if $\beta$ satisfies $\alpha^{-1} + \beta^{-1} = 1$, then the sequences $\lfloor \alpha n \rfloor$ and $\lfloor \beta n \rfloor$ for $n \ge 1$ partition $\Bbb N$ (not counting $0$)
Therefore, letting $m = \lfloor \alpha n \rfloor$, $S(\alpha,n) + S(\beta, \lfloor m/\beta \rfloor) = \sum_{k=1}^m k = m(m+1)/2$
Also, $\lfloor m/ \beta \rfloor = m - \lceil m/\alpha \rceil = m- n = \lfloor (\alpha-1)n \rfloor$.
Then, letting $n' = \lfloor (\alpha-1)n \rfloor $ you have
$S(\alpha,n) = (n+n')(n+n'+1)/2 - S(\beta,n')$
So those two formulas give you a very fast way to compute $S$ if you can compute $n' = \lfloor (\alpha-1) n \rfloor$

In your case, $\alpha = \sqrt 2$, so you begin in the second case where you get $\beta = 2+\sqrt 2$. Since the sequence of $\alpha$s you get is periodic, you can get a recurrence formula :
Let $n' = \lfloor (\sqrt 2 -1) n \rfloor$,
$S(\sqrt 2,n) = (n+n')(n+n'+1)/2 - S(2+\sqrt 2,n') \\
= (n+n')(n+n'+1)/2 - S(\sqrt 2,n') - n'(n'+1) \\
 = nn'+n(n+1)/2-n'(n'+1)/2 - S(\sqrt 2,n')$
For example this tells you that $S(\sqrt 2,5) = 22 - S(\sqrt 2, 2) = 22 - 3 + S(\sqrt 2, 0) = 19.$

Since at each step $n$ is approximately multiplied by $\sqrt 2 - 1$, the arguments decrease exponentially. For $n = 10^{100}$ you need approximately $\lceil {100 \log {10}/\log ({1\over(\sqrt 2-1)})} \rceil = 262$ steps to complete the recursion. This is basically equivalent to computing the powers of $(\sqrt 2-1)$ with enough precision and should be doable quickly on any computer.
