floor number sum

Question

For $a$ and $n$, there is formula to calculate

$$a + 2a + 3a + \cdots + na = \frac{n(n+1)}{2} a.$$

Is there formula:

$$\lfloor a\rfloor + \lfloor 2a\rfloor + \lfloor 3a\rfloor + \cdots + \lfloor na\rfloor $$

Answer 1

There is a closed form solution to the sum $\sum_{0\le k<n} \left\lfloor \frac {pk} q \right\rfloor$ when $n$ is a multiple of $q$. The sum in question is similar to one in Knuth's The Art of Computer Programming (Section 1.2.4 problem 37). Knuth's suggestion is to focus on the fractional parts instead of the integral parts of the terms. $$ \sum_{0\le k<n} \left\lfloor \frac {pk} q \right\rfloor = \sum_{0\le k<n} \frac {pk} q + \sum_{0\le k<n} \left\lbrace \frac {pk} q \right\rbrace = \frac p q \frac {n(n-1)} 2 + \sum_{0\le k<n} \left\lbrace \frac {pk} q \right\rbrace $$ The fractional part function $\lbrace pk /q\rbrace$ is periodic with period $q/d$, where $d=gcd(p,q)$. We might want $d\ne 1$ because of the restriction that $n$ is a multiple of $q$. $$ \sum_{0\le k<n} \left\lbrace \frac {pk} q \right\rbrace = \frac n q d \sum_{0\le k<q/d} \left\lbrace \frac {pk} q \right\rbrace = \frac n q d \sum_{0\le k<q/d} \left\lbrace \frac {p/d} {q/d} k \right\rbrace $$ There is a bit of number theory required for the next step. $gcd(p/d,q/d)=1$, so $(p/d)k=j\;(\text{mod}\;q/d)$ has a solution, unique modulo $q/d$, for every integer $j$, $0\le j<q/d$. Using this fact, the terms of the sum can be reordered in a way that leads to a radical simplification: $$ \sum_{0\le k<n} \left\lbrace \frac {pk} q \right\rbrace = \frac n q d \sum_{0\le k<q/d} \left\lbrace \frac {1} {q/d} k \right\rbrace = \frac n q d \sum_{0\le k<q/d} \frac {1} {q/d} k = n\left(1-\frac d q \right) $$ Putting the pieces together $$ \sum_{0\le k<n} \left\lfloor \frac {pk} q \right\rfloor = \frac p q \frac {n(n-1)} 2 + n \left(1-\frac d q \right) $$ Changing the limits of summation $$ \sum_{1\le k\le n} \left\lfloor \frac {pk} q \right\rfloor = \frac p q \frac {n(n+1)} 2 + n \left(1-\frac d q \right) $$

Answer 2

There seems no exact formula for the sum, considering that the sum depends highly sensitively on the fraction part of $a$. But we can give an asymptotic formula:

Case 1. If $a$ is rational, write $a = p/q$ where $p$ and $q$ are positive coprime integers. Then $kp \ \mathrm{mod} \ q$ attains every value in $\{0, 1, \cdots, q-1\}$ exactly once whenever $k$ runs through $q$ successive integers. Thus if we write $n = mq + r$,

$$ \begin{align*} \sum_{k=1}^{n} (ka - \lfloor ka \rfloor) &= \sum_{k=1}^{mq} (ka - \lfloor ka \rfloor) + \sum_{k=1}^{r} (ka - \lfloor ka \rfloor) \\ &= \frac{m(q-1)}{2} + O(1) = \frac{n(q-1)}{2q} + O(1). \end{align*}$$

This gives

$$ \sum_{k=1}^{n} \lfloor ka \rfloor = \frac{1}{2}n\left(n+\frac{1}{q}\right) + O(1). $$

Case 2. If $a$ is irrational, then the fractional parts $\langle ka \rangle := ka - \lfloor ka \rfloor$ is equidistributed on $[0, 1]$ by Weyl's criterion. Thus $$ \lim_{n\to\infty} \frac{1}{n} \sum_{k=1}^{n} \langle ka \rangle = \int_{0}^{1} x \, dx = \frac{1}{2} \quad \Longrightarrow \quad \sum_{k=1}^{n} \langle ka \rangle = \frac{n}{2} + o(n) $$ and we have $$ \sum_{k=1}^{n} \lfloor ka \rfloor = \frac{n^2}{2} + o(n). $$

Answer 3

There is also a way to evaluate this sum using Pick´s theorem.

$$\sum_{i=1}^n\left\lfloor \frac{p}{n} i\right\rfloor = \frac{pn+p-n + gcd(p,n)}{2}$$