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)$. The naive approach of computing term by term takes $O(n)$. However, there is a faster algorithm.

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])$.

The only thing that matters now is whether computing $S(\beta, \lfloor m/\beta \rfloor)$ is simpler than computing $S(\alpha, n)$.

To achieve this, we check whether $\alpha > 2$.

If $\alpha > 2$, use the following reduction to bring $\alpha$ into the range $(1, 2)$:

$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 assume $1 < \alpha < 2$.

From $\alpha^{-1} + \beta^{-1} = 1$, we get $\beta = \frac{\alpha}{\alpha - 1}$.

If $\beta > 2$, we apply the same reduction to bring $\beta$ into $(1, 2)$.

The key observation is that $\lfloor m/\beta \rfloor < n$:

$\lfloor m/\beta \rfloor = \lfloor \lfloor \alpha n \rfloor / \beta \rfloor \le \frac{\alpha n}{\alpha/(\alpha-1)} = (\alpha - 1)n < n$ since $0 < \alpha - 1 < 1$.

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

As a result, it makes problem simpler.

Since the argument to $S$ shrinks by a constant factor at each step, the recursion terminates quickly. This algorithm is therefore much faster than the naive $O(n)$ computation.

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$