Beatty sequence
1. Reference

Beatty sequence

This problem require to calculate $\sum_{i=1}^{n} \lfloor i\sqrt{2} \rfloor$. We must take into consideration the precision and the performance. The $n$ can be very large, up to 101 digits. There several aspect. How to take floor more efficiently? How to deal with big number? After a few search I found that there is a specific algorithm. This type of problem involves a mathematical concept: Beatty sequence. In mathematics, a Beatty sequence is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number.

$$
\mathcal{B}_r = \lfloor r \rfloor ,\ \lfloor 2r \rfloor ,\ \lfloor 3r \rfloor ,\dots
$$

Let $\mathcal{B}_r^{(i)} = \lfloor i*r \rfloor$ for some irrational positive number,

and

$S(r, n) = \sum_{i=1}^{n}{\mathcal{B}_r^{(i)}}$

If $r \ge 2$ we let $s = r - 1$ and we have $S(r, n) = S(s, n) + \sum_{i=1}^{n} i = S(s, n) + \frac{n(n+1)}{2}$

If $1 < r < 2$ there is a theorem that says that if $s$ satisfies $r^{-1} + s^{-1} = 1$, then the sequences $\mathcal{B}_r$ and $\mathcal{B}_s$ for $n \ge 1$ partition $\mathbb{N}$ (not counting 0).

Therefore, $S(r, n) + S(s, \lfloor \frac{\mathcal{B}_r^{(n)}}{s} \rfloor) = \sum_i^{\mathcal{B}_r^{(n)}} i = \frac{\mathcal{B}_r^{(n)}(\mathcal{B}_r^{(n)} + 1)}{2}$

And also $\lfloor \frac{\mathcal{B}_r^{(n)}}{s} \rfloor = \lfloor \mathcal{B}_r^{(n)}(1 - \frac{1}{r}) \rfloor = \mathcal{B}_r^{(n)} - \lceil \frac{\mathcal{B}_r^{(n)}}{r} \rceil = \mathcal{B}_r^{(n)} - n$

Then, letting $n^{\prime} = \lfloor (r - 1)n \rfloor = \mathcal{B}_{r-1}^{n}$

we have $S(r,n) = \frac{\mathcal{B}_r^{(n)}(\mathcal{B}_r^{(n)} + 1)}{2} - S(s, n^{\prime}) = \frac{(n + n^{\prime})(n + n^{\prime} + 1)}{2} - S(s, n^{\prime})$.

Back to the problem, we have $r = \sqrt{2}$, so we start with $s = 2 + \sqrt{2}$. We can get a recurrence formula.

Let $n^{\prime} = \lfloor (\sqrt{2} - 1)n \rfloor$,

$$
\begin{split}
S(\sqrt{2}, n)
&= \frac{(n + n^{\prime})(n + n^{\prime} + 1)}{2} - S(2 + \sqrt{2}, n^{\prime})\\\\
&= \frac{(n + n^{\prime})(n + n^{\prime} + 1)}{2} - (n^{\prime}(n^{\prime} + 1) - S(\sqrt{2}, n^{\prime}))\\\\
&= nn^{\prime} + \frac{n(n+1)}{2} - \frac{n^{\prime}(n^{\prime} + 1)}{2} - S(\sqrt{2}, n^{\prime})
\end{split}
$$

Dodge The Lasers

Beatty sequence

Reference