Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

up vote 6 down vote accepted
+25

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

share|improve this answer
    
@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
1  
@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

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

share|improve this answer
    
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
1  
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
    
Please read my comment on your last answer. Thanks. –  user02138 Jan 14 '11 at 19:25

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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