Problem

Let’s think about the sequence of $[\alpha k]$ for $k \in \mathcal{Z}^+$ and $\alpha \in \mathcal{R}^+/\mathcal{Q}^+$ and $\alpha > 1$. For example, $[\sqrt{2}] \approxeq 1.414 = 1, [2 \sqrt{2}] \approxeq 2.828 = 2, [3 \sqrt{2}] \approxeq 4.242 = 4, [4 \sqrt{2}] \approxeq 5.656 = 5, [5 \sqrt{2}] \approxeq 7.071 = 7$ for $\alpha = \sqrt{2}$. Let’s define $S(\alpha, n) = \sum\limits_{k = 1}^{n}[\alpha k]$. Then, problem is that compute $S(\alpha, n)$. In general, it can be computed easily by computing one by one which takes $O(n)$. However, there is another algorithm that takes much less time than this.

Algorithm

Then, $S(\alpha, n) + S(\beta, [m/\beta]) = \sum\limits_{k = 1}^{m} k$ with following conditions.

$\alpha^{-1} + \beta^{-1} = 1$
$m = [\alpha n]$

Proof is as follows.

First of all, due to the Rayleigh’s theorem(Beatty’s theorem), it is true that sum of two sequence can cover the interger sequence.

Secondly, it is true that $S(\beta, [m/\beta])$ covers all integers from $1$ to $m$ that exists in the $[\beta k]$ since it ends with $[m/\beta]$.

At the same time, $S(\alpha, n)$ ends with $[\alpha n] = m$. Therefore, it covers all integers from $1$ to $m$.

From the proof above, $S(\alpha, n) + S(\beta, [m/\beta]) = \sum\limits_{k = 1}^{m} k = m(m + 1)/2$

As a result, $S(\alpha, n) = m(m + 1)/2 - S(\beta, [m/\beta])$.

Now, onlything that matter is whether computing $S(\beta, [m/\beta])$ is simpler than computing $S(\alpha, n)$.

To achived this, we need to check whether $\alpha > 2$ or not.

If $\alpha > 2$, use the follwoing equations to reduce $\alpha$.

$S(\alpha, n) = \sum\limits_{k = 1}^{n}[\alpha k] $ $ = \sum\limits_{k = 1}^{n}[((\alpha - 1) + 1) k] $ $ = \sum\limits_{k = 1}^{n}[(\alpha - 1)k + k] $ $ = \sum\limits_{k = 1}^{n}[(\alpha - 1)k] + \sum\limits_{k = 1}^{n}k $ $ = S(\alpha - 1, n) + n(n+1)/2$

Notice that it means $S(\alpha, n) = S(\alpha - k, n) + kn(n+1)/2$ for $k \in \mathcal{Z}^{+}$ such that $k < \alpha - 1$.

Now, let’s assume that $1 < \alpha < 2$.

It is ture that $\beta = \frac{\alpha}{\alpha - 1}$ from $\alpha^{-1} + \beta^{-1} = 1$.

If $\beta$ is bigger than $2$, we can use the same process above to change it exists between $1$ and $2$.

Therefore, only consideration is whether $[m/\beta]$ is smaller than $n$ or not.

And it is true from $[m/\beta] = [[\alpha n]/\beta] = [[\alpha n]/(\alpha/(\alpha - 1))] \le ((\alpha n)/\alpha)(\alpha - 1) = (\alpha - 1) n < n$.

Notice that $ 0 < \alpha - 1 < 1$.

As a result, it makes problem simpler.

Notice that this algorithm is faster since it reduces number to be computed in some ratio.

Therefore, it usually faster than computing it one by one.

Example

For example, $S(\sqrt{2}, 100)$ can be computed as follows. Notice that $\alpha = \sqrt{2}$ then $\beta = \frac{\sqrt{2}}{\sqrt{2} - 1} = 2 + \sqrt{2}$

$S(\sqrt{2}, 100) = 141 * 142 / 2 - S(2 + \sqrt{2}, 41)$ by $m = [\sqrt{2} * 100] = 141, [m/\beta] = 41$.
$S(2 + \sqrt{2}, 41) = S(\sqrt{2}, 41) + 2 * 41 * 42/2$
$S(\sqrt{2}, 41) = 57 * 58 / 2 - S(2 + \sqrt{2}, 16)$ by $m = [\sqrt{2} * 100] = 57, [m/\beta] = 16$.
$S(2 + \sqrt{2}, 16) = S(\sqrt{2}, 16) + 2 * 16 * 17/2$
$S(\sqrt{2}, 16) = 22 * 23 / 2 - S(2 + \sqrt{2}, 6)$ by $m = [\sqrt{2} * 16] = 22, [m/\beta] = 6$.
$S(2 + \sqrt{2}, 6) = S(\sqrt{2}, 6) + 2 * 6 * 7/2$
$S(\sqrt{2}, 6) = 8 * 9 / 2 - S(2 + \sqrt{2}, 2)$ by $m = [\sqrt{2} * 6] = 8, [m/\beta] = 2$.
$S(2 + \sqrt{2}, 2) = S(\sqrt{2}, 2) + 2 * 2 * 3/2$
$S(\sqrt{2}, 2) = 2 * 3 / 2 - S(2 + \sqrt{2}, 0)$ by $m = [\sqrt{2} * 2] = 2, [m/\beta] = 0$.
$S(2 + \sqrt{2}, 0) = 0$
$S(\sqrt{2}, 2) = 2 * 3 / 2 - S(2 + \sqrt{2}, 0) = 3 - 0 = 3$
$S(2 + \sqrt{2}, 2) = S(\sqrt{2}, 2) + 2 * 2 * 3/2 = 3 + 6 = 9$
$S(\sqrt{2}, 6) = 8 * 9 / 2 - S(2 + \sqrt{2}, 2) = 36 - 9 = 27$
$S(2 + \sqrt{2}, 6) = S(\sqrt{2}, 6) + 2 * 6 * 7/2 = 27 + 42 = 69$
$S(\sqrt{2}, 16) = 22 * 23 / 2 - S(2 + \sqrt{2}, 6) = 253 - 69 = 184$
$S(2 + \sqrt{2}, 16) = S(\sqrt{2}, 16) + 2 * 16 * 17/2 = 184 + 272 = 456$
$S(\sqrt{2}, 41) = 57 * 58 / 2 - S(2 + \sqrt{2}, 16) = 1653 - 456 = 1197$
$S(2 + \sqrt{2}, 41) = S(\sqrt{2}, 41) + 2 * 41 * 42/2 = 1197 + 1722 = 2919$
$S(\sqrt{2}, 100) = 141 * 142 / 2 - S(2 + \sqrt{2}, 41) = 10011 - 2919 = 7092$