Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am looking to evaluate the sum $$\sum_{1\leq k\leq mn}\left\{ \frac{k}{m}\right\} \left\{ \frac{k}{n}\right\} .$$

Using matlab, and experimenting around, it seems to be $\frac{(m-1)(n-1)}{4}$ when $m,n$ are relatively prime. How can we prove this, and what about the case where they are not relatively prime?

Conjecture: Numerically, it seems that for any $m,n$ we have $$\sum_{1\leq k\leq mn}\left\{ \frac{k}{m}\right\} \left\{ \frac{k}{n}\right\} =\frac{(m-1)(n-1)}{4}+C(\gcd(m,n))$$ where $C(\gcd(m,n))$ is some constant depending only on the $\gcd(m,n)$.

Additionally: Can we sum this even when it is not a complete interval? Suppose that $0<a<b<mn,$ do we have an exact form for $$\sum_{a\leq k\leq b}\left\{ \frac{k}{m}\right\} \left\{ \frac{k}{n}\right\}.$$

Remark: In the one variable case we have $$\sum_{1\leq k\leq n}\left\{ \frac{k}{n}\right\} =\frac{n-1}{2}$$ the sum over an interval $a,b$ has an explicit form.

share|cite|improve this question
When $m=n$ your sum seems to be $(n-1)(2n-1)/6$. – Robert Israel May 3 '12 at 18:08
@RobertIsrael: That seems to be right since we are counting the interval $[1,n]$ exactly $n$ times. That is we have $$\sum_{1\leq k\leq n^2}\left\{ \frac{k}{n}\right\}^2=n\sum_{1\leq k\leq n-1}\frac{k^2}{n^2}=\frac{1}{n}\sum_{k=1}^{n-1}k^2=\frac{(n-1)(2n-1)}{6}.$$ – Eric Naslund May 3 '12 at 18:26
More generally, we could ask about $$\sum_{k=0}^{f-1}\left\{a_1\frac{k}{f}\right\}\cdots\left\{a_r\frac{k}{f}\right‌​\}.$$ This case corresponds to $f=mn,~r=2;~~a_1=m,~a_2=n$. – anon May 3 '12 at 22:55
@anon: I think your idea almost gives the general solution I am looking for. We know that for some choices of $k$ modulo $mn$ we have $$\left(\sum_{1\leq k\leq m}\left\{ \frac{k}{m}\right\} \right)\left(\sum_{1\leq k\leq n}\left\{ \frac{k}{n}\right\} \right)=\sum_{k\text{ mod }mn}\left\{ \frac{k}{n}\right\} \left\{ \frac{k}{m}\right\} $$ but then we just need to remove duplicates and such so that the right hand side is my desired sum above. The left hand side is easily calculated to be $\frac{(m-1)(n-1)}{4}$, so if we can remove and calculate the additional terms, this gives the result. – Eric Naslund May 3 '12 at 23:05
I am not yet convinced that enough "numerical evidence" has been looked at. – Phira May 5 '12 at 0:48
up vote 8 down vote accepted

Let's call your sum $f(m,n)$. The ordinary generating function of $f(\cdot,n)$ appears to be of the form $$g(z,n) = \frac{z^2 p_n(z)}{6 (1-z)(1-z^n)}$$ where $p_n$ is a polynomial of degree $n-1$ (except for $n=2$ where it has degree $0$): $$\eqalign{ p_{{2}}&=3\cr p_{{3}}&=-{z}^{2}+7\,z+3\cr p_{{4}}&=-3\,{z}^{3}+12\,{z}^{2}+3\,z+6\cr p_{{5}}&=-6\,{z}^{4}+18\,{z}^{3}+6\,{z}^{2}+6\,z+6\cr p_{{6}}&=-10\,{z}^{5}+25\,{z}^{4}+6\,{z}^{3}+5\,{z}^{2}+10\,z+9\cr p_{{7}}&=-15\,{z}^{6}+33\,{z}^{5}+9\,{z}^{4}+9\,{z}^{3}+9\,{z}^{2}+9\,z +9\cr p_{{8}}&=-21\,{z}^{7}+42\,{z}^{6}+9\,{z}^{5}+12\,{z}^{4}+3\,{z}^{3}+18 \,{z}^{2}+9\,z+12\cr p_{{9}}&=-28\,{z}^{8}+52\,{z}^{7}+12\,{z}^{6}+8\,{z}^{5}+16\,{z}^{4}+12 \,{z}^{3}+8\,{z}^{2}+16\,z+12\cr p_{{10}}&=-36\,{z}^{9}+63\,{z}^{8}+12\,{z}^{7}+15\,{z}^{6}+12\,{z}^{5}+ 3\,{z}^{4}+24\,{z}^{3}+15\,{z}^{2}+12\,z+15\cr p_{{11}}&=-45\,{z}^{10}+75\,{z}^{9}+15\,{z}^{8}+15\,{z}^{7}+15\,{z}^{6} +15\,{z}^{5}+15\,{z}^{4}+15\,{z}^{3}+15\,{z}^{2}+15\,z+15\cr p_{{12}}&=-55\,{z}^{11}+88\,{z}^{10}+15\,{z}^{9}+14\,{z}^{8}+13\,{z}^{7 }+24\,{z}^{6}-{z}^{5}+34\,{z}^{4}+9\,{z}^{3}+20\,{z}^{2}+19\,z+18\cr}$$

EDIT: This seems to come from the fact that $$f(m+n,n) - f(m,n) =\frac{n^2-n}{4}$$ for all $m$ and $n$.

EDIT: Let $g(m,n) = f(m,n) - \dfrac{(m-1)(n-1)}{4}$. From $f(m+n,n) - f(m,n) = \dfrac{n^2-n}{4}$ we get $g(m+n,n) = g(m,n)$. By following the Euclidean algorithm, we get $$g(m,n) = g(d,d) = \dfrac{(d-1)(2d-1)}{6} - \dfrac{(d-1)^2}{4} = \frac{d^2-1}{12}$$ where $d = \gcd(m,n)$. That is, $$ f(m,n) = \frac{\gcd(m,n)^2-1}{12} + \dfrac{(m-1)(n-1)}{4} $$

share|cite|improve this answer
Perfect, that is exactly what I was looking for. Thank you! – Eric Naslund May 4 '12 at 0:53

The fractional parts depend only on the values modulo $n$ and $m$, respectively.

Since you take $m$ and $n$ relatively prime, you can simply let the two instances of $k$ run through all residue classes modulo $m$ and $n$ independently (Chinese remainder theorem). This reduces your question immediately to the product of the one-variable case for $m$ and $n$.

The one-variable case is a direct consequence of the summation formula for the first $n$ integers.

Edited to add: This means, of course, that an arbitrary interval is not a very good condition on the pair of residues and there is no reason to expect a general closed expression.

share|cite|improve this answer

For the relatively prime case. Split the summation into classes $k \equiv 0 \mod m$, $k \equiv 1 \mod m$, $k \equiv 2 \mod m$ and so on. For $k \equiv r \mod m$, and $1 \leq k \leq mn$ each $k$ leaves a distinct remainder when divided by $n$ since $m$ and $n$ are relatively prime. Hence, the summation is $$\displaystyle \frac{\sum_{r=0}^{n-1} r}{m} \times \frac{\sum_{r=0}^{m-1} r}{n} = \frac{n(n-1)}{2m} \frac{m(m-1)}{2n}$$

EDIT Consider the class say $k \equiv r \bmod m$. If $(m,n)=1$, then $r,m+r,2m+r,\cdots,(n-1)m+r$ leave different remainders when divided by $n$. If not then $n | (k_1 - k_2)m$ for some $0 \leq k_1,k_2 <n$. Since $(m,n) = 1$, $n|(k_1-k_2)$. Not possible. Hence, summing all the remainders in the class $k \equiv r \bmod m$ gives us $\frac{n(n-1)}{2}$. Hence, the sum of all the fractional parts is $\displaystyle \frac{n(n-1)}{2m}$.

share|cite|improve this answer
This seems good. Maybe something like this along with a mobius type inclusion exclusion will give the general case. – Eric Naslund May 3 '12 at 23:09
@EricNaslund Yes using Chinese remainder theorem sort of argument to get the solution when $(m,n) \neq 1$. I just noticed that Phira has also said the same thing. – user17762 May 3 '12 at 23:16

Your Answer


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.