# 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
Commented Dec 10, 2016 at 6:32
• @Hugh if possible both of them :) Commented 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
Commented 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
Commented 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
Commented 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 Commented Jun 2, 2017 at 11:18
• @IndoUbt um do you have any difficulty when applying the two formulas for $S(e,5)$ ? Commented 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. Commented Jun 2, 2017 at 22:18
• For anyone wondering, the name of the theorem is Rayleigh's theorem. Commented Sep 5, 2020 at 4:22
• @mercio Can you or someone clarify how you say that S(α,n)+S(β,⌊m/β⌋) = ∑_{k=1}^{m} k? And what's the process that leads you to sum those quantities and pick m=⌊αn⌋? I am lost here... Commented Sep 27, 2022 at 16:44

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 Commented 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
Commented Dec 10, 2016 at 15:54
• @HyJu I test formula with real big number comparation:N = 86032128652 The real answer: 5233670046269024148148 your formula answer: 5233670046269023958675.330079366 Commented Dec 11, 2016 at 6:56
• @Sinoheh By the way your "real answer" seems incorrect. The correct one should be 5233670046269023958676. Commented Dec 11, 2016 at 18:00
• A computational evidence suggests that $S(\sqrt{2},N)=\frac{\varphi^2}{3}N^2+\frac{\sqrt{2}-1}{2}N+N\cdot I(N)$, where $|I(N)|<1.1$ and the graph of $I(N)$ looks like that of a Fourier series, see a sample for $1\le n\le 4096$. See the first part of this answer for more. Commented Nov 18, 2017 at 8:08