For any real number $a$ and a positive integer $n$, there is a concise formula to calculate

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

The proof for the same is given in Mathematical literature.

Is there any such formula to calculate:

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


$$\lceil a\rceil + \lceil 2a\rceil + \lceil 3a\rceil + \cdots + \lceil na\rceil $$

for any whole number $n$ and $ 0 < a < 1$ ? Also, provide the proof for the same.

  • 1
    $\begingroup$ Have you tried calculating any, looking for patterns? $\endgroup$ – Gerry Myerson Oct 5 '12 at 7:21
  • $\begingroup$ Yes, tried calculating for both things. There is a pattern for particular numbers like 0.2, 0.4, 0.8. But, how to generalize the pattern for any real number like 0.39856, 0.0009843, etc? Of course, finding general patterns helps in providing a formula. There doesn't seem having a general pattern among all real numbers. $\endgroup$ – soery Oct 5 '12 at 7:45
  • $\begingroup$ 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 $\endgroup$ – Gerry Myerson Oct 5 '12 at 13:19

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

  • $\begingroup$ 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? $\endgroup$ – miracle173 Jun 10 '17 at 6:43
  • $\begingroup$ @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$. $\endgroup$ – Vim Jun 10 '17 at 6:58

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.