5
$\begingroup$

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

$\endgroup$
2
8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – Solen'ya
    Apr 28 '20 at 5:04
  • $\begingroup$ 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. $\endgroup$ May 27 '20 at 4:16
7
$\begingroup$

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

$\endgroup$
2
  • $\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
  • 1
    $\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
0
$\begingroup$

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

$\endgroup$

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.