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}$.
 A: It is clear that, because the sequence $\{<n\sqrt{2}>\}$(the fractional part) is equidistributed over the interval $[0,1)$, we have
$$\tag{1}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{N(N+1)\sqrt{2}}{2}-\sum_{n=1}^N <n\sqrt{2}>\label{1}$$
and for the latter sum, 
$$\tag{2}\frac{1}{N}\sum_{n=1}^N <n\sqrt{2}> \to \frac{1}{2}\label{2}$$
as $N \to \infty$.
In other words, we have
$$\tag{3}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{N(N+1)\sqrt{2}}{2}-\frac{N}{2}+o(N)\label{3}$$
as $N \to \infty$.
So , in average, we have
$$\tag{4}\frac{1}{N}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{(N+1)\sqrt{2}}{2}-\frac{1}{2}+o(1)\label{4}$$
and in fact the remainder term is smaller than $1/2$.
So we conclude that $\frac{1}{N}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor$(which is not an integer) is very close to the nearest integer to the number $\frac{N\sqrt{2}+\sqrt{2}-1}{2}$.
One interesting thing I observed is that we in fact have more nice decay of the error term, that is,
$$\tag{5}\frac{1}{N}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{(N+1)\sqrt{2}}{2}-\frac{1}{2}+o(\frac{1}{N}),\label{5}$$
so, return to our original problem, we come up with
$$\tag{6}\sum_{n=1}^N \lfloor n\sqrt{2} \rfloor = \frac{N(N+1)\sqrt{2}}{2}-\frac{N}{2}+o(1)\label{6}$$
and in fact the error term is again smaller than 1/2. So the sum is the nearest integer to the number
$$\tag{7}\label{7}\frac{N(N+1)\sqrt{2}}{2}-\frac{N}{2}=\frac{N(N\sqrt{2}+\sqrt{2}-1)}{2}$$.
But the proof could possibly require more nice approximation than just the equidistribution of the sequence.
(And there seems even more faster decay of the error term!!)
++Added))
What always true in the above discussion is $\eqref{3}$ or the equivalent form $\eqref{4}$. So we can exactly figure out the average value of the Beatty sequence of $\sqrt{2}$, that is, the division of $\eqref{1}$ by $N$.
However, for the exact computation of the value of the sum $\eqref{1}$, we need more precise approximation on the error term like $\eqref{5}$ or $\eqref{6}$. Unfortunately, $\eqref{5}$ is not true and so is $\eqref{7}$.
I think the best we can do is this: For any irrational $\gamma$, let $L(\gamma)=1-|1-2<\gamma>|$. Then we have
$$\left\vert \sum_{n=1}^N \lfloor n\gamma \rfloor - \left(\frac{N(N+1)\gamma}{2}-\frac{N}{2}\right) \right\vert \leq \frac{c}{L(\gamma)}$$
with $c$ a constant irrelevant to $\gamma$ and $N$($c=2$ would actually work)
This essentially asserts that the randomness of the distribution of the sequence $\{<n\gamma>\}$ in $[0,1)$ depends on how close $<\gamma>$ is to $0$ or $1$(Note that $L(\gamma)/2$ is the minimum distance from $<\gamma>$ to $0$ and to $1$. Of course this is really a naive approximation, need to be adjusted in many ways.
A: 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.
