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

• Clearly $10^{100}$ is large enough for any asymptotic behaviour to take place. Are you looking for an exact value of $a_{10^{100}}$ or an approximation?
– Hugh
Dec 10, 2016 at 6:32
• @Hugh if possible both of them :) Dec 10, 2016 at 6:37
• You said you wanted both exact and asymptotic. It's quite rude to ignore my answer and give a two word response for what more you want
– Hugh
Dec 10, 2016 at 6:47
• Actually, $i\sqrt{2}-[i\sqrt{2}]$ is equidistributed on $[0,1)$, so finding asymptotic behavior is the best we can. The values of averaged sum behaves just like $\frac{\sqrt{2}n+\sqrt{2}-1}{2}$.
– HyJu
Dec 10, 2016 at 6:57
• @Hugh Yes it is. See link. For a proof, read the Fourier analysis textbook written by E.M.Stein and R.Shakarchi.
– HyJu
Dec 10, 2016 at 8:13

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.

• @mercio The same question, how can it be done for say $e$? Could you show an example for it as it's greater than 2 like $S(5,e)$? Thanks Jun 2, 2017 at 11:18
• @IndoUbt um do you have any difficulty when applying the two formulas for $S(e,5)$ ? Jun 2, 2017 at 21:26
• you didn't replace $n$ with $5$ and didn't compute the value of $n'$ ? well $e$'s continued fraction has some regularity (though it is not periodic) so in this case you are in luck that you can have some kind of recursion, but in general, continued fractions can look like anything. Jun 2, 2017 at 22:18
• @mercio What if $0 < \alpha < 1$ ? I got it while I was trying to do $S(e, 5)$. Jun 10, 2017 at 16:47
• For anyone wondering, the name of the theorem is Rayleigh's theorem. Sep 5, 2020 at 4:22

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!!)

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.

• This is work for little numbers. Do you know how to generate this numbers? oeis.org/A194104 also watch this oeis.org/A194102 Dec 10, 2016 at 14:58
• @Sinoheh Actually, I tried numbers no more than you've tested. Try the averaged one at the middle of my answer. This must work for all large values of $N$. Numerical test seems very interesting though. Can you show me the results?
– HyJu
Dec 10, 2016 at 15:54
• For example: input: "23223423" your result is : 381362049543566.61858316753391048249640080000565 with halfUp is : 381362049543567 and the correct answer is :381362049543566. If you want I test with bigger number I must put my server to work until tomorrow to test 10^31. If you think it can help us I will make 1 sample for this question with 10 ^31 number Dec 10, 2016 at 16:08
• It looks like the formula is quite accurate, and the error can be $\pm 1$ and $\pm 2$. For example, if we define error(N) as the value of the last formula - the true value, then $error(72)=1$, $error(35)=-1$, $error(83652)=2$, $error(40390)=-2$. And this numbers looks random for me. I'm wondering whether it is possible to nail down the exact summation value. Dec 11, 2016 at 1:56
• And for N up to 100000, there are 12086 numbers with error=-1 and 14880 numbers with error=1 and 2 numbers with error=-2 and 12 numbers with error=2. Dec 11, 2016 at 2:04