To what number does $ n^{-2} \times \sum_{m=1}^{n-1} n \bmod m$ converge, as $n$ gets large?

Question

I evaluated the expression $$ n^{-2} \times \sum_{m=1}^{n-1} n \bmod m$$ for "large" $n$ values ($10^3$, $10^4$, $10^5$, $...$) and it seems to converge to the number approximately $0.17753188$. I tried to search for this number on the internet, found nothing and I also tried to analyze the expression, but my mathematical knowledge seems to be too small for this problem. Does anybody have an idea what this number could be (if it has a closed form)?

Answer 1

Write $n\bmod m = n -m\cdot\left\lfloor\frac{n}m\right\rfloor$ and hence your partial sums are

\begin{align} s_n &= \sum_{m= 1}^{n-1}\,\frac1n - \frac{m}{n^2}\cdot\left\lfloor\frac{n}m\right\rfloor \\&= 1 - \frac{1}{n} -\frac1{n^2} \left( \sum_{m= 1}^{n-1}\,m \cdot \left\lfloor\frac{n}m\right\rfloor \right). \end{align}

Now, write

\begin{align} c_n = \frac1{n^2} \left( \sum_{m= 1}^{n-1}\,m \cdot \left\lfloor\frac{n}m\right\rfloor \right) &= \sum_{m= 1}^{n-1}\,\left(\frac{m}n \cdot \left\lfloor\frac1{m/n}\right\rfloor \right)\cdot\frac1n \end{align}

so that as $n\to\infty$ we have

$$\lim_{n\to\infty} c_n =\int_0^1\,x\left\lfloor 1/x\right\rfloor\,dx.$$

It follows that $\lim_{n\to\infty}s_n = 1 - \int_0^1\,x\left\lfloor 1/x\right\rfloor\,dx$, so an expression for the limit of your sum hinges on our ability to provide a closed form expression for this integral. The change of variable $x=1/t$ yields

\begin{align} \int_0^1\,x\left\lfloor 1/x\right\rfloor\,dx &= \int_1^\infty\,\frac1{t^3}\left\lfloor t\right\rfloor\,dt \\&= \sum_{n=1}^{\infty}\,n\,\int_n^{n+1}\,t^{-3}\,dt \\&= \sum_{n=1}^{\infty}\,n\,{\left[-\frac12t^{-2}\right]}_n^{n+1} \\&= \sum_{n=1}^{\infty}\,n\,\left(\frac1{2n^2}-\frac1{2(n+1)^2}\right) \\&= \frac12\,\left(\sum_{n=1}^{\infty}\,\frac1n-\frac{n}{(n+1)^2}\right). \end{align}

Observe that

$$\frac{n}{(n+1)^2} = \frac1{n+1}-\frac1{(n+1)^2}$$

to obtain that

$$\int_0^1\,x\left\lfloor 1/x\right\rfloor\,dx = \frac12\,\left(\sum_{n=1}^{\infty}\,\frac1n-\frac1{n+1}+\frac1{(n+1)^2}\right). $$

The first bit we can recognize as a telescoping series and the second bit as the infamous Basel problem, and hence

$$\int_0^1\,x\left\lfloor 1/x\right\rfloor\,dx = \frac12\,\frac{\pi^2}{6}.$$

It follows that our limit sum equals

$$1-\frac{\pi^2}{12} \simeq 0.17753296657588678.$$

Answer 2

Here's a direct approach that is less elegant than @Fimpellizieri's solution but perhaps provides some insight. Consider the sum in reverse order.

The first n/2 terms are 1,2,...n/2-1 with average value of about n/4 so the sum is approximately $n^2/8$.

Then the next n/3-n/2 terms are approximately 1,3,5,...n/3 so the sum is approximately $n^2/36$.

Continuing this, after dividing by $n^2$ we get the sum

$\sum_{k=2}^\infty 1/(2k^2(k-1)) = 1 - \pi^2/12$.

After some manipulation you can turn this into the Basel problem (or just ask wolframalpha!).

Note that this argument is easy to make rigorous.