2
$\begingroup$

I found the following problem:

$$\lim_{n\to\infty}\left(\frac{1}{n^2}\sum_{m=1}^{n}n\space\text{mod}\space m\right)$$

and decided to give it a go. I got an answer of $1-\frac{\pi^2}{12}$, but I am not sure if this is correct. It was posted with no source/context, and I wasn't able to find the solution online. I did find that the inner sum is sometimes referred to as the "sum of remainders" function, however.

Does anyone know where this problem comes from, and if my answer is correct?


Edit: Here's my working out:

I first noticed that, for large $n$:

$$n\space\text{mod}\space \left(n-k\right)\equiv k, \space\space\space n-k>\frac{n}{2}$$ $$n\space\text{mod}\space \left(\left[\frac{n}{2}\right]-k\right)\equiv 2k, \space\space\space \left[\frac{n}{2}\right]-k>\frac{n}{3}$$ $$n\space\text{mod}\space \left(\left[\frac{n}{3}\right]-k\right)\equiv 3k, \space\space\space \left[\frac{n}{3}\right]-k>\frac{n}{4}$$

$$\vdots$$

I visualised these as right triangles with base $\frac{n}{m(m+1)}$ and height $\frac{n}{m+1}$, which gave a new expression for the sum for large $n$ as the sum of areas of these triangles: $$\frac{1}{2}\sum_{m=1}^{a}\frac{n^2}{m(m+1)^2}, \space\space\space a=O(\sqrt{n})$$

The new limit is then:

$$\lim_{n\to\infty}\left(\frac{1}{2}\sum_{m=1}^{n}\frac{1}{m(m+1)^2}\right)$$

Partial fraction decomposition into a telescoping sum gave me: $$\frac{1}{2}\sum_{m=1}^{\infty}\frac{1}{m(m+1)^2}=\frac{1}{2}\left(2-\sum_{n=1}^{\infty}\frac{1}{n^2}\right)=1-\frac{\pi^2}{12}$$

$\endgroup$
2
  • 2
    $\begingroup$ It will probably be easier to verify your solution if you given an outline of your proof, rather than just your numeric answer. $\endgroup$ Aug 6, 2019 at 15:56
  • $\begingroup$ @CalvinGodfrey Ok, I'll write up my working $\endgroup$ Aug 6, 2019 at 16:03

2 Answers 2

3
$\begingroup$

Yes, the answer $1-\frac{\pi^2}{12}$ and your proof are correct. As a further reference I suggest the paper The Humble Sum of Remainders Function by Michael Z. Spivey.

This is the sketch of an alternative proof.

1) Show that $$\sum_{m = 1}^{n} n \bmod m = n^{2} - \sum_{k = 1}^{n} \sigma (k)$$ where $\sigma(k)$ is the sum of positive divisors of $k$.

2) Then use $$\sum_{k=1}^n\sigma(k)=\frac{\pi^2}{12}n^2+o(n^2).$$ See Sum of the sum-of-divisors function.

$\endgroup$
2
$\begingroup$

Using $$n\bmod m = n-m\left\lfloor \frac{n}{m}\right\rfloor$$ you get:

$$\sum_{m=1}^{n} n\bmod m = n^2-\sum_{m=1}^{n} m\left\lfloor \frac{n}{m}\right\rfloor$$

or:

$$\frac{1}{n^2}\sum_{m=1}^{n} n\bmod m = 1-\frac{1}{n}\sum_{m=1}^{n} \frac{m}{n}\left\lfloor \frac{n}{m}\right\rfloor$$

But $\frac{1}{n}\sum_{m=1}^{n} \frac{m}{n}\left\lfloor \frac{n}{m}\right\rfloor$ is a Riemann sum for $$\int_{0}^{1}x\lfloor 1/x\rfloor \,dx.$$

You can re-write this integral as:

$$\sum_{n=1}^{\infty}n\int_{1/(n+1)}^{1/n}x\,dx =\frac{1}{2}\sum_{n=1}^{\infty}n\left(\frac{1}{n^2}-\frac{1}{(n+1)^2}\right)\tag{1}$$

More generally, we have $\sum_{n=1}^{\infty} n(f(n)-f(n+1))=\sum_{m=1}^{\infty} f(m),$ when $nf(n+1)\to 0.$

This means that $(1)$ is $\frac{1}{2}\zeta(2)=\frac{\pi^2}{12},$

$\endgroup$
2
  • $\begingroup$ Interesting approach! $\endgroup$ Aug 6, 2019 at 16:47
  • $\begingroup$ (+1) This was the approach I took. It may not be as number theoretic, but it seems very intuitive to me. $\endgroup$
    – robjohn
    Aug 6, 2019 at 21:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .