# Evaluation of the sum $\sum_{k = 0}^{\lfloor a/b \rfloor} \left \lfloor \frac{a - kb}{c} \right \rfloor$

Let $a, b$ and $c$ be positive integers. Recall that the greatest common divisor (gcd) function has the following representation: \begin{eqnarray} \textbf{gcd}(b,c) = 2 \sum_{k = 1}^{c- 1} \left \lfloor \frac{kb}{c} \right \rfloor + b + c - bc \end{eqnarray} as shown by Polezzi, where $\lfloor \cdot \rfloor$ denotes the floor function. In trying to generalize the formula I came across the following summation \begin{eqnarray} \sum_{k = 0}^{\lfloor a/b \rfloor} \left \lfloor \frac{a - kb}{c} \right \rfloor. \end{eqnarray} I can prove the following identity for real $x$, \begin{eqnarray} \sum_{k = 0}^{c-1} \left \lceil \frac{x - kb}{c} \right \rceil = d \left \lceil \frac{x}{d} \right \rceil - \frac{(b-1)(c-1)}{2} - \frac{d-1}{2}, \end{eqnarray} where $\lceil \cdot \rceil$ denotes the ceiling function and $d = \text{gcd}(b,c)$. (Note that in the first summation the upper index is in general independent of $c$.) Ideas or reference suggestions are certainly appreciated. Thanks in advance!

Update I can prove the identity \begin{eqnarray} \sum_{k = 0}^{c-1} \left \lfloor \frac{x - kb}{c} \right \rfloor = d \left \lfloor \frac{x}{d} \right \rfloor - \frac{(b+1)(c-1)}{2} + \frac{d-1}{2}, \end{eqnarray} where $d = \text{gcd}(b,c)$. There is another identity which might be useful. If $n = c \ell +r$ with $0 \leq r < c$, then \begin{eqnarray} \sum_{k = 1}^{n} \left \lfloor \frac{k}{c} \right \rfloor = c \binom{\ell}{2} + (r + 1) \ell. \end{eqnarray}

Update 2 Ok, so I can prove that for real $x, y > 0$, \begin{eqnarray} \sum_{k = 0}^{\lfloor y \rfloor} \left \lfloor x + \frac{k}{y} \right \rfloor = \lfloor xy + (\lceil y \rceil - y) \lfloor x + 1 \rfloor \rfloor + \chi_{\mathbb{N}}(y)(\lfloor x \rfloor + 1), \end{eqnarray} where $\chi_{\mathbb{N}}$ denotes the characteristic function of the positive integers. My original problem (and a nice generalization of it) will be in hand if I can evaluate the following minor generalization: For real $x, y > 0$ and $n \in \mathbb{Z}_{\geq 0}$, \begin{eqnarray} \sum_{k = 0}^{n} \left \lfloor x + \frac{k}{y} \right \rfloor. \end{eqnarray} Again, any help is certainly appreciated!

-

I would like to summarise and extend the results of my previous answer in a new answer as I prefer to keep the original in its current form to prevent it from turning into my magnum opus.

Theorem 1:

For positive integers $a, b$ and $c$ where $d=\text{gcd}(b,c),$ $u=c/d,$ $t= \lfloor a/b \rfloor$ and $a \equiv \lambda \textrm{ mod } d,$ where $0 \le \lambda < d,$ and $u \, | \, (t+1)$ we have

$$\sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} - \frac{c-d}{2} - \lambda \right \rbrace .$$

So far, the above theorem and its proof are included in my previous answer. The rest is new.

Theorem 2:

Along with the definitions in theorem 1, let $a \equiv r \textrm{ mod } c,$ where $0 \le r < c$ and $u \, | \, t$ then

$$\sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} \right \rbrace - \frac{1}{c} \left \lfloor \frac{t+1}{u} \right \rfloor \left \lbrace \frac{u(c-d)}{2} + \lambda u \right \rbrace - \frac{r}{c} .$$

For example, with $a=1019,b=33$ and $c=55$ we have $d=\text{gcd}(33,55)=11,$ $u=c/d=55/11=5,$ $t= \lfloor 1019/33 \rfloor = 30$ and $1019 \equiv 29 \textrm{ mod } 55,$ and $1019 \equiv 7 \textrm{ mod } 11.$ Hence $r = 29$ and $\lambda = 7.$

Note that the condition $u \, | \, t$ is satisfied, and so theorem 2 gives

$$\sum_{k=0}^{30} \left \lfloor \frac{1019 - 33k}{55} \right \rfloor = \frac{31}{55} \left \lbrace 1019 - \frac{ 30 \cdot 33}{2} \right \rbrace - \frac{6}{55} \left \lbrace \frac{5(55-11)}{2} + 7 \cdot 5 \right \rbrace - \frac{29}{55} = 279.$$

This is easily verified with WolframAlpha, or similar.

Both of these theorems are special cases ($\mu=0$ and $\mu=1$) of the general result:

Theorem 3: Along with the previous definitions in theorems 1 and 2, let $t+1 \equiv \mu \textrm{ mod } u,$ where $0 \le \mu < u$ then

$$\sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} \right \rbrace - \frac{1}{c} \left \lfloor \frac{t+1}{u} \right \rfloor \left \lbrace \frac{u(c-d)}{2} + \lambda u \right \rbrace$$ $$- \frac{1}{c} \sum_{k=0}^{\mu - 1} \left \lbrace r+k \left \lbrace \left( \left \lfloor \frac{b}{c} \right \rfloor + 1 \right) c - b \right \rbrace \textrm{ mod } c \right \rbrace .$$

There are $\mu$ terms in the last sum, so this is understood to be zero when $\mu =0.$ The terms in the final summation of the equation are all $\ge 0$ and reduced modulo $c.$

A sketch of the proof runs as follows. On adding up the $t+1$ equations at the start of my previous answer, we add up $\lfloor (t+1)/u \rfloor$ “complete” sets of residues modulo $c$ (not to be confused with a complete residue system modulo $c$) that are congruent to $\lambda$ modulo $c.$ The term $\sum_{k=0}^{\mu - 1} \lbrace r+k \lbrace \cdots \rbrace \textrm{ mod } c \rbrace$ (equivalent, of course, to $\sum_{k=0}^{\mu - 1} \lbrace (r-kb) \textrm{ mod } c \rbrace$ ) is the sum of the “left over residues.”

Rearranging the equation obtained from the summation proves the theorem.

Note: In the text $\lbrace \cdot \rbrace$ is only used for readability and does not indicate fractional part (I find doubled-up curved brackets awkward to read).

Just for fun, here is what we get when we put $\mu = 2$ into theorem 3.

Theorem 2(b): Along with the previous definitions, since $\mu = 2$ our condition here is that $u \, | \, (t-1) .$ Now for $r \ge b$ we obtain

$$\sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} \right \rbrace - \frac{1}{c} \left \lfloor \frac{t+1}{u} \right \rfloor \left \lbrace \frac{u(c-d)}{2} + \lambda u \right \rbrace - \frac{2r-b}{c} . \quad (1)$$

For example, with $a=1037,b=33$ and $c=55$ we have $d=\text{gcd}(33,55)=11,$ $u=c/d=55/11=5,$ $t= \lfloor 1037/33 \rfloor = 31$ and $1037 \equiv 47 \textrm{ mod } 55,$ and $1037 \equiv 3 \textrm{ mod } 11.$ Hence $r = 47$ and $\lambda = 3.$

Note that the condition $u \, | \, (t-1)$ is satisfied, and so theorem 2(b) gives

$$\sum_{k=0}^{31} \left \lfloor \frac{1037 - 33k}{55} \right \rfloor = \frac{32}{55} \left \lbrace 1037 - \frac{ 31 \cdot 33}{2} \right \rbrace - \frac{6}{55} \left \lbrace \frac{5(55-11)}{2} + 3 \cdot 5 \right \rbrace - \frac{2 \cdot 47 - 33}{55} = 291.$$

This is easily verified with WolframAlpha, or similar.

For $r < b$ the final term in $(1)$ would be $- \frac{2r+c-b}{c}.$

(To be continued... time and enthusiasm permitting :-) )

-
@user02138: Please can you say something about the motivation behind your question. Thanks. – Derek Jennings Jan 14 '11 at 12:55
Hi Derek, yes, in trying to derive and generalize the floor representation of the gcd function, I came across the above problem. Should I mention this in the original post? – user02138 Jan 14 '11 at 19:25
@user02138: Yes, that's a good idea and I see that you have already done it. Well done. – Derek Jennings Jan 15 '11 at 9:21
Again, excellent post! I was having some difficulty with the initial version of Theorem 3 but it looks like all kinks have been worked out. Well done! – user02138 Jan 16 '11 at 7:53

This isn't a complete solution but rather a reformulation for a large number of cases involving the problem above. Write $n = m \lfloor y \rfloor + r$, where $0 \leq r < \lfloor y \rfloor$ and $n, m , r \in \mathbb{Z}_{\geq 0}$. Then for real $x, y > 0$, we have \begin{eqnarray} \sum_{k = 0}^{n} \left \lfloor x + \frac{k}{y} \right \rfloor & = & \lfloor x \rfloor + \sum_{\ell = 0}^{m-1} \left \lfloor x y + \ell \lfloor y \rfloor + ( \lceil y \rceil - y) \left \lfloor x + \frac{\ell \lfloor y \rfloor}{y} + 1 \right \rfloor \right \rfloor + \end{eqnarray} \begin{eqnarray} & & \sum_{k = 1}^{r} \left \lfloor x + \frac{m \lfloor y \rfloor}{y} + \frac{k}{y} \right \rfloor + \chi_{\mathbb{N}}(y) \sum_{\ell = 0}^{m-1} \left \lfloor x + \frac{\ell \lfloor y \rfloor}{y} + 1 \right \rfloor - \sum_{\ell = 0}^{m-1} \left \lfloor x + \frac{ \ell \lfloor y \rfloor }{y} \right \rfloor . \end{eqnarray} This was derived by partitioning the interval $[0,n]$ into subintervals and using the last identity in the description of the problem.

For the original problem, write \begin{eqnarray} \sum_{k = 0}^{\lfloor a /b \rfloor} \left \lfloor \frac{a - k b}{c} \right \rfloor = \sum_{k = 0}^{\lfloor a /b \rfloor} \left \lfloor \frac{\text{mod}(a,b) + k b}{c} \right \rfloor \end{eqnarray} where $\text{mod}(a,b) = a - b \lfloor \frac{a}{b} \rfloor$. If $\lfloor \frac{a}{b} \rfloor \gg c$, then use the identity above to vastly reduce the number of terms in the sum.

-

Here is an observation/partial result. For brevity write $t = \lfloor a/b \rfloor .$ When $\text{gcd}(b,c)=1$ and $c \, | \, (t+1)$ we have

$$S = \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} - \frac{c-1}{2} \right \rbrace .$$

Proof:

Suppose

\begin{align} a &= m_0 c + r_0 \\ a- b &= m_1 c + r_1 \\ a - 2b &= m_2 c + r_2 \\ \cdots &= \cdots \\ a - tb &= m_t c + r_t \end{align}

for integer $m_i$ and $r_i$ where $0 \le r_i < c$ then, adding the above equations,

$$(t+1)a - \frac{t(t+1)}{2}b = Sc + \sum_{k=0}^t r_k . \quad (1)$$

Now if $\text{gcd}(b,c)=1$ and $k$ runs over a complete system of residues modulo $c$ then $a-kb,$ where $a$ is any integer, also runs over a complete system of residues modulo $c$. So when $c \, | \, (t+1)$ we have that $a-kb$ runs over $(t+1)/c$ complete residue systems modulo $c$. Hence $$\sum_{k=0}^t r_k = \frac{(t+1)(c-1)}{2}.$$

Substitute this into $(1)$ to obtain the result.

EDIT: Here is a generalisation for the case $\text{gcd}(b,c)>1,$ which reduces to the above when $b$ and $c$ are coprime.

Write $d=\text{gcd}(b,c)$ and suppose $a \equiv \lambda \textrm { mod } d$ where $0 \le \lambda < d.$

Now $a-kb$ runs through all the residues modulo $c$ that are congruent to $\lambda$ modulo $c$ as $k$ runs through $0,1,2,\ldots,u-1$ where $u=c/d.$ When $u \, | \, (t+1)$ we have that $r_0,r_1,\ldots,r_t$ runs through $(t+1)/u$ such residue systems. Hence

$$\sum_{k=0}^t r_k = \frac{t+1}{u} \left \lbrace \frac{du(u-1)}{2} + \lambda u \right \rbrace = (t+1) \left \lbrace \frac{c-d}{2} + \lambda \right \rbrace .$$

And so

$$\sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} - \frac{c-d}{2} - \lambda \right \rbrace .$$

EDIT2: Here are a couple of numerical examples. With $a=91,b=15 \textrm{ and } c=21$ we have $d=\text{gcd}(15,21)=3,$ $t=\lfloor 91/15 \rfloor = 6,$ $u=c/d=21/3=7$ and $91 \equiv 1 \textrm{ mod } 3,$ and so $\lambda=1.$ Note that the condition $u \, | \, (t+1)$ is satisfied. Our formula gives the sum as

$$\frac{7}{21} \left \lbrace 91 - \frac{6 \cdot 15}{2} - \frac{21-3}{2} - 1 \right \rbrace = 12.$$

This is small enough to check by hand.

$$\sum_{k=0}^7 \left \lfloor \frac{91-15k}{21} \right \rfloor = 4+3+2+2+1+0+0=12.$$

With $a=703,b=35 \textrm{ and } c=49$ we have $d=\text{gcd}(35,49)=7,$ $t=\lfloor 703/35 \rfloor = 20,$ $u=c/d=49/7=7$ and $703 \equiv 3 \textrm{ mod } 7,$ and so $\lambda=3.$ Note that the condition $u \, | \, (t+1)$ is satisfied. Our formula gives the sum as

$$\frac{21}{49} \left \lbrace 703 - \frac{20 \cdot 35}{2} - \frac{49-7}{2} - 3 \right \rbrace = 141.$$

One can verify with WolframAlpha, or similar, that

$$\sum_{k=0}^{20} \left \lfloor \frac{703-35k}{49} \right \rfloor = 141.$$

-
Thanks. This is certainly a nice partial result. Is it straightforward to generalize to the case when $b$ and $c$ are not coprime? – user02138 Jan 11 '11 at 17:48
Also, for those interested, the curly braces do not mean "fractional part". – user02138 Jan 11 '11 at 18:09
It's generalises for $\text{gcd}(b,c)>1$ more readily if we have $a \equiv 0 \textrm{ mod } c,$ but it's not a great generalisation as this adds a condition to $a.$ I'll try and give it more thought when I have time. – Derek Jennings Jan 11 '11 at 21:41
@user02138 Thanks for such an interesting question. Sorry I didn't look at it sooner but life's been very busy for me lately. Can you tell me what motivated the question? Thanks. – Derek Jennings Jan 12 '11 at 10:43