floor number sum

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$$

• Have you tried calculating any, looking for patterns? Oct 5 '12 at 7:21
• For rational $a$, your sums come up in some of the early proofs of quadratic reciprocity --- see, e.g., Eisenstein's proof en.wikipedia.org/wiki/Proofs_of_quadratic_reciprocity Oct 5 '12 at 13:19

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

• Hello , I have same problem but n is not a multiple of q and d=1 . How can I modify this equation for that case ? Apr 28 '20 at 5:04
• This was a very helpful and thought provoking answer. So thank you! However, there are a few little things wrong with the arithmetic. The couple I would like to point is that, your first statement itself is wrong, floor = sum - fractional part. The second is that in your summation after radical simplification, you missed out a divide by 2. So, actually the formula should become: $\sum_{0\le k<n} \left\lfloor \frac {pk} q \right\rfloor = \frac p q \frac {n(n-1)} 2 - \frac{n}{2} \left(1-\frac d q \right)$ Also, I believe you can't change limits like you did in the end. May 27 '20 at 4:16

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

• by user HKedia: I am sorry, I dont have enough reputations to comment. @Sangchul Lee what is meant by o(n) in your irrational derivation? Jun 10 '17 at 6:43
• @miracle173 It means a quantity which grows slower than $n$. Formally, if $a_n=o(n)$, then $a_n/n\to0$ as $n\to\infty$.
– Vim
Jun 10 '17 at 6:58

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}$$