## Limit of $\frac{1}{n}\sum_{r=1}^n\frac{n\ (\mathrm{mod}\ r)}{r}$

By accident I came across the following,

$$\lim_{n\to\infty}\frac{1}{n}\sum_{r=1}^n\frac{n\ (\mathrm{mod}\ r)}{r}=0.4227\ldots\approx 1-\gamma,$$

where the numerator is the remainder of $n$ divided by $r$. Is it known whether we have equality in the above expression or is it just a numerical coincidence? Has this been studied?

Edit: I'm sorry for all the (important) typos, everything should be fixed now.

-
 Without conditions on n, I have a hard time believing that lim inf of the sum is as large as you claim. I do not think the limit exists. Gerhard "Ask Me About System Design" Paseman, 2012.04.17 – Gerhard Paseman Apr 17 2012 at 14:48 The text is incorrect (should be the remainder of $n$ divided by $r$) – Igor Rivin Apr 17 2012 at 14:56 Can the OP prove this, or is this an experimental fact? – Igor Rivin Apr 17 2012 at 14:56 Further, I see no way of rescuing the problem without making the denominator substantially bigger, as in r^2 or n^2, or making the numerator correspondingly smaller. Gerhard "Ask Me About System Design" Paseman, 2012.04.17 – Gerhard Paseman Apr 17 2012 at 14:57 @Igor: thanks for spotting the typo. And no, I cannot prove this, this is purely experimental. – unknown Apr 17 2012 at 14:59

This follows by elementary computation: we have \begin{align*} \sum_{r=1}^n\frac{n\bmod r}r&=\sum_{r\le n}\frac nr-\sum_{r\le n}\left\lfloor\frac nr\right\rfloor\\ &=nH_n-|\{(r,s)\in\mathbb N^2:1\le rs\le n\}|\\ &=nH_n-2\sum_{r\le\sqrt n}\left\lfloor\frac nr\right\rfloor+\lfloor\sqrt n\rfloor^2\\ &=nH_n-2nH_{\lfloor\sqrt n\rfloor}+n+O(\sqrt n), \end{align*} hence \begin{align*} \frac1n\sum_{r=1}^n\frac{n\bmod r}r&=H_n-2H_{\lfloor\sqrt n\rfloor}+1+O(n^{-1/2})\\ &=\log n+\gamma-2\log\lfloor\sqrt n\rfloor-2\gamma+1+O(n^{-1/2})\\ &=1-\gamma+O(n^{-1/2}). \end{align*}

-
Fir clarity, I would change the indexing rs <= n to set notation that said something like the set of pairs of positive integers (r,s) with r,s <= n. For me that would remove the ambiguity of whether r or s or both are the index, as well as whether negative r and negative s were allowed. Gerhard "Nice Derivation, By The Way" Paseman, 2012.04.17 – Gerhard Paseman Apr 17 2012 at 15:32
You are right, hopefully it is more clear now. – Emil Jeřábek Apr 17 2012 at 15:45
To add to Emil's nice answer: The determination of the OP's limit is implicit in Dirichlet's estimate for the average order of the divisor function, namely $\sum_{k=1}^{n} d(k) = n \log{n} + (2\gamma-1)n + O(\sqrt{n})$. (See section 18.2 in Hardy and Wright, for example.) To see the connection, notice that the sum in question is exactly the number of ordered pairs of natural numbers $(r,s)$ with $rs \leq n$ (and now compare with Emil's answer above). – Anonymous Apr 17 2012 at 16:32
Thank you, this is a great answer. – unknown Apr 17 2012 at 17:17
@Anonymous: Yes, I guess I should have mentioned in the answer that this estimate of $\sum_{r\le n}\lfloor n/r\rfloor$ is a classical fact. – Emil Jeřábek Apr 18 2012 at 16:11