2
$\begingroup$

We have $$\left\lfloor{ac+bd\over k}\right\rfloor-\left\lfloor{ac+bd-1\over k}\right\rfloor=1-\left\lceil{ (ac+bd)\mod{k}\over k}\right\rceil$$ for $a,b,c,d,k$ - integers, $a\geqslant0$, $b\geqslant0$, $c>0$, $d>0$, $k>0$. Next we want to calculate $$\sum\limits_{a=0}^{n}\sum\limits_{b=0}^{m}\left\lfloor{ac+bd\over k}\right\rfloor$$ or $$\sum\limits_{a=0}^{n}\sum\limits_{b=0}^{m}\left\lceil{(ac+bd)\mod{k}\over k}\right\rceil$$ Is there a nice closed form for it?

$\endgroup$
2
$\begingroup$

Here we give a closed form expression for a special case of the double sum indicating that there is no nice formula in the general case.

Let $N, M, c$ be positive integer with \begin{align*} N=&c\left\lfloor\frac{N}{c}\right\rfloor+n\qquad 0\leq n<c\\ M=&c\left\lfloor\frac{M}{c}\right\rfloor+m\qquad 0\leq m<c \end{align*} then the following is valid \begin{align*} \sum_{k=0}^N&\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor\tag{1}\\ &=-\frac{1}{2}c(1-c)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{2c-2}{2}\right\rfloor\\ &\quad+\frac{1}{2}m(m+1)\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{c+m-1}{c}\right\rfloor +\frac{1}{2}n(n+1)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{c+n-1}{c}\right\rfloor\\ &\quad+\left(m+1-\frac{c}{2}\right)(n+1)\left\lfloor\frac{M}{c}\right\rfloor+\left(n+1-\frac{c}{2}\right)(m+1)\left\lfloor\frac{N}{c}\right\rfloor\\ &\quad+\frac{1}{2}(n+1)c\left\lfloor\frac{M}{c}\right\rfloor^2+\frac{1}{2}(m+1)c\left\lfloor\frac{N}{c}\right\rfloor^2\\ &\quad+c(m+n+2-c)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor\\ &\quad+\frac{1}{2}c^2\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor \left(\left\lfloor\frac{M}{c}\right\rfloor+\left\lfloor\frac{N}{c}\right\rfloor\right)\\ &\quad+\left(\frac{1}{2}((m+n)^2+3(m+n)+2)-\left(m+n+\frac{3}{2}\right)c+\frac{1}{2}c^2\right)\left\lfloor\frac{m+n}{c}\right\rfloor\tag{2} \end{align*}

We observe the special case $\left\lfloor\frac{ak+bl}{c}\right\rfloor$ in (1) with $a=b=1$ results in a rather complex formula (2) indicating the general case is also rather complex.

In order to prove (2) we need some preliminary results, namely three types of single sums with floor functions given below.

Let $n,a,c$ be integer $n\geq 0, c>0, 0\leq a <c$.

The following is valid

\begin{align*} \sum_{k=0}^n\left\lfloor\frac{k+a}{c}\right\rfloor &=\left(n+1+a-\frac{c}{2}\right)\left\lfloor\frac{n+a}{c}\right\rfloor-\frac{c}{2}\left\lfloor\frac{n+a}{c}\right\rfloor^2\tag{3}\\ \sum_{k=0}^n k\left\lfloor \frac{k+a}{c}\right\rfloor &=\frac{1}{12}\left(6n(n+1)-6a^2+6a(c-1)-c^2+3c\right)\left\lfloor\frac{n+a}{c}\right\rfloor\\ &\qquad+\frac{c}{4}(2a-c+1)\left\lfloor\frac{n+a}{c}\right\rfloor^2-\frac{c^2}{6}\left\lfloor\frac{n+a}{c}\right\rfloor^3\tag{4}\\ \sum_{k=0}^n\left\lfloor\frac{k+a}{c}\right\rfloor^2 &=\frac{c}{6}\left\lfloor\frac{n+a}{c}\right\rfloor+\left(n+1+a-\frac{c}{2}\right)\left\lfloor\frac{n+a}{c}\right\rfloor^2-\frac{2c}{3}\left\lfloor\frac{n+a}{c}\right\rfloor^3\tag{5} \end{align*}

Ad (3):

Let $n,a,c$ integer $n\geq 0, c>0, 0\leq a <c$. We obtain

\begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{\left\lfloor\frac{k+a}{c}\right\rfloor}\\ &=\sum_{k=0}^n\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[j=\left\lfloor\frac{k+a}{c}\right\rfloor\right]\tag{6}\\ &=\sum_{k=0}^n\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[ j\leq \frac{k+a}{c} < j+1\right]\\ &=\sum_{k=0}^n\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[ cj-a\leq k < c(j+1)-a\right]\\ &=\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j\sum_{k=cj-a}^{c(j+1)-a-1}1 +\left\lfloor\frac{n+a}{c}\right\rfloor\sum_{k=c\left\lfloor\frac{n+a}{c}\right\rfloor-a}^n 1\\ &=c\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j+\left\lfloor\frac{n+a}{c}\right\rfloor\left(n-c\left\lfloor\frac{n+a}{c}\right\rfloor+a+1\right)\\ &=\frac{c}{2}\left(\left\lfloor\frac{n+a}{c}\right\rfloor-1\right)\left\lfloor\frac{n+a}{c}\right\rfloor+\left\lfloor\frac{n+a}{c}\right\rfloor\left(n-c\left\lfloor\frac{n+a}{c}\right\rfloor+a+1\right)\\ &\,\,\color{blue}{=\left(n+a+1-\frac{c}{2}\right)\left\lfloor\frac{n+a}{c}\right\rfloor-\frac{c}{2}\left\lfloor\frac{n+a}{c}\right\rfloor^2} \end{align*}

and (3) follows.

Comment:

Ad (4):

Let $n,a,c$ integer $n\geq 0, c>0, 0\leq a <c$. We obtain

\begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{k\left\lfloor\frac{k+a}{c}\right\rfloor}\\ &=\sum_{k=0}^nk\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[j=\left\lfloor\frac{k+a}{c}\right\rfloor\right]\\ &=\sum_{k=0}^nk\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[ j\leq \frac{k+a}{c} < j+1\right]\\ &=\sum_{k=0}^nk\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[ cj-a\leq k < c(j+1)-a\right]\\ &=\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j\sum_{k=cj-a}^{c(j+1)-a-1}k +\left\lfloor\frac{n+a}{c}\right\rfloor\sum_{k=c\left\lfloor\frac{n+a}{c}\right\rfloor-a}^n k\\ &=\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j\left(\frac{1}{2}\left(c(j+1)-a-1\right)(c(j+1)-a)-\frac{1}{2}\left(cj-a-1\right)(cj-a)\right)\\ &\qquad+\left\lfloor\frac{n+a}{c}\right\rfloor\left(\binom{n+1}{2}-\binom{c\left\lfloor\frac{n+a}{c}\right\rfloor-a}{2}\right)\\ &=\frac{1}{2}\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j(-2ac+2c^2j+c^2-c) +\left\lfloor\frac{n+a}{c}\right\rfloor\left(\binom{n+1}{2}-\binom{c\left\lfloor\frac{n+a}{c}\right\rfloor-a}{2}\right)\\ &=c^2\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j^2+\left(\frac{c^2-c}{2}-ac\right)\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j +\left\lfloor\frac{n+a}{c}\right\rfloor\left(\binom{n+1}{2}-\binom{c\left\lfloor\frac{n+a}{c}\right\rfloor-a}{2}\right)\\ &=\frac{c^2}{6}\left(\left\lfloor\frac{n+a}{c}\right\rfloor-1\right)\left\lfloor\frac{n+a}{c}\right\rfloor\left(2\left\lfloor\frac{n+a}{c}\right\rfloor-1\right)\\ &\qquad+\frac{c}{4}(c-1-2a)\left(\left\lfloor\frac{n+a}{c}\right\rfloor-1\right)\left\lfloor\frac{n+a}{c}\right\rfloor\\ &\qquad+\frac{1}{2}\left(n(n+1)-\left(c\left\lfloor\frac{n+a}{c}\right\rfloor-a\right)\left(c\left\lfloor\frac{n+a}{c}\right\rfloor-a-1\right)\right)\left\lfloor\frac{n+a}{c}\right\rfloor\\ &\,\,\color{blue}{=\frac{1}{12}\left(6n(n+1)-6a^2+6a(c-1)-c^2+3c\right)\left\lfloor\frac{n+a}{c}\right\rfloor}\\ &\qquad\color{blue}{+\frac{c}{4}(2a-c+1)\left\lfloor\frac{n+a}{c}\right\rfloor^2-\frac{c^2}{6}\left\lfloor\frac{n+a}{c}\right\rfloor^3} \end{align*}

and (4) follows.

Ad (5):

The proof of this case is similar to (3) and is omitted.

The main formula (2):

The proof of formula (2) is really cumbersome and somewhat lengthy. Here I will show the first steps and everything else follows by consequently applying (3) to (5).

We obtain \begin{align*} \color{blue}{\sum_{k=0}^N}&\color{blue}{\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor}\\ &=\sum_{k=0}^{c\left\lfloor\frac{N}{c}\right\rfloor+n}\ \sum_{l=0}^{c\left\lfloor\frac{M}{c}\right\rfloor+m}\left\lfloor\frac{k+l}{c}\right\rfloor\\ &=\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}\ \sum_{k_2=0}^{c-1}\ \sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}\ \sum_{l_2=0}^{c-1} \left\lfloor\frac{ck_1+k_2+cl_1+l_2}{c}\right\rfloor\\ &\qquad+\sum_{k_2=0}^n\ \sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}\ \sum_{l_2=0}^{c-1} \left\lfloor\frac{c\left\lfloor\frac{N}{c}\right\rfloor+k_2+cl_1+l_2}{c}\right\rfloor\\ &\qquad+\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}\ \sum_{k_2=0}^{c-1}\ \sum_{l_2=0}^{m} \left\lfloor\frac{ck_1+k_2+c\left\lfloor\frac{M}{c}\right\rfloor+l_2}{c}\right\rfloor\\ &\qquad+\sum_{k_2=0}^n\sum_{l2=0}^n\left\lfloor\frac{c\left\lfloor\frac{N}{c}\right\rfloor+k_2+c\left\lfloor\frac{M}{c}\right\rfloor+l_2}{c}\right\rfloor\\ &=\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}\ \sum_{k_2=0}^{c-1}\ \sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}\ \sum_{l_2=0}^{c-1} \left(\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+k_1+l_1\right)\\ &\qquad+\sum_{k_2=0}^n\ \sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}\ \sum_{l_2=0}^{c-1} \left(\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+\left\lfloor\frac{N}{c}\right\rfloor+l_1\right)\\ &\qquad+\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}\ \sum_{k_2=0}^{c-1}\ \sum_{l_2=0}^{m} \left(\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+k_1+\left\lfloor\frac{M}{c}\right\rfloor\right)\\ &\qquad+\sum_{k_2=0}^n\sum_{l2=0}^n\left(\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+\left\lfloor\frac{N}{c}\right\rfloor+\left\lfloor\frac{M}{c}\right\rfloor\right)\\ &=\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_2=0}^{c-1}\sum_{l_2=0}^{c-1}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor +c^2\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}k_1 +c^2\left\lfloor\frac{N}{c}\right\rfloor\sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}l_1\\ &\qquad+\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_2=0}^n\sum_{l_2=0}^{c-1}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor +(n+1)\left\lfloor\frac{M}{c}\right\rfloor c\left\lfloor\frac{N}{c}\right\rfloor +(n+1)c\sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}l_1\\ &\qquad+\left\lfloor\frac{N}{c}\right\rfloor\sum_{k_2=0}^{c-1}\sum_{l_2=0}^{m}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor +\left\lfloor\frac{N}{c}\right\rfloor c (m+1)\left\lfloor\frac{M}{c}\right\rfloor +c(m+1)\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}k_1\\ &\qquad+\sum_{k_2=0}^{n}\sum_{l_2=0}^m\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+(n+1)(m+1)\left(\left\lfloor\frac{N}{c}\right\rfloor+\left\lfloor\frac{M}{c}\right\rfloor\right)\\ \end{align*} \begin{align*} &=\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_2=0}^{c-1}\sum_{l_2=0}^{c-1}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor\\ &\qquad\qquad+c^2\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor\left(\left\lfloor\frac{N}{c}\right\rfloor-1\right) +c^2\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor\left(\left\lfloor\frac{M}{c}\right\rfloor-1\right)\\ &\qquad+\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_2=0}^n\sum_{l_2=0}^{c-1}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor\\ &\qquad\qquad+(n+1)\left\lfloor\frac{M}{c}\right\rfloor c\left\lfloor\frac{N}{c}\right\rfloor+(n+1)c\left\lfloor\frac{M}{c}\right\rfloor\left(\left\lfloor\frac{M}{c}\right\rfloor-1\right)\\ &\qquad+\left\lfloor\frac{N}{c}\right\rfloor\sum_{k_2=0}^{c-1}\sum_{l_2=0}^{m}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor\\ &\qquad\qquad+\left\lfloor\frac{N}{c}\right\rfloor c (m+1)\left\lfloor\frac{M}{c}\right\rfloor +c(m+1)\left\lfloor\frac{N}{c}\right\rfloor\left(\left\lfloor\frac{N}{c}\right\rfloor-1\right)\\ &\qquad+\sum_{k_2=0}^{n}\sum_{l_2=0}^m\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+(n+1)(m+1)\left(\left\lfloor\frac{N}{c}\right\rfloor+\left\lfloor\frac{M}{c}\right\rfloor\right)\tag{7}\\ \\ &=\cdots\tag{8}\\ \\ &\,\,\color{blue}{=-\frac{1}{2}c(1-c)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{2c-2}{2}\right\rfloor}\\ &\quad\color{blue}{+\frac{1}{2}m(m+1)\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{c+m-1}{c}\right\rfloor +\frac{1}{2}n(n+1)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{c+n-1}{c}\right\rfloor}\\ &\quad\color{blue}{+\left(m+1-\frac{c}{2}\right)(n+1)\left\lfloor\frac{M}{c}\right\rfloor+\left(n+1-\frac{c}{2}\right)(m+1)\left\lfloor\frac{N}{c}\right\rfloor}\\ &\quad\color{blue}{+\frac{1}{2}(n+1)c\left\lfloor\frac{M}{c}\right\rfloor^2+\frac{1}{2}(m+1)c\left\lfloor\frac{N}{c}\right\rfloor^2}\\ &\quad\color{blue}{+c(m+n+2-c)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor}\\ &\quad\color{blue}{+\frac{1}{2}c^2\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor \left(\left\lfloor\frac{M}{c}\right\rfloor+\left\lfloor\frac{N}{c}\right\rfloor\right)}\\ &\quad\color{blue}{+\left(\frac{1}{2}((m+n)^2+3(m+n)+2)-\left(m+n+\frac{3}{2}\right)c+\frac{1}{2}c^2\right)\left\lfloor\frac{m+n}{c}\right\rfloor} \end{align*}

Note: I've checked the formula programmatically for small values of $M,N$ and $c$.

There are in fact some steps which are needed to fill in (8), since we have double sums in (7) which have to be substituted iteratively by (3) to (5). So, the steps up to (7) are rather the beginning of the main calculation.

$\endgroup$
  • $\begingroup$ @user514787: You're welcome. Probably the results of the three single sums will be sometimes useful. As you may have already noticed, I've added this question as addendum to my answer. Regards, $\endgroup$ – Markus Scheuer Feb 16 at 10:12

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.