How to find $\sum_{i=1}^n\left\lfloor i\sqrt{2}\right\rfloor$ A001951 A Beatty sequence: a(n) = floor(n*sqrt(2)).

Question

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

Answer 1

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.

Answer 2

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.