Welcome to MathOverflow

Question

5

1

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.

edited Apr 17 2012 at 15:03

asked Apr 17 2012 at 14:28

unknown
53●1●4

	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

show 4 more comments

Emil Jeřábek · Accepted Answer · 2012-04-17 15:43:31Z UTC

13

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*}

edited Apr 17 2012 at 15:43

answered Apr 17 2012 at 15:17

Emil Jeřábek
10.6k●1●24●41

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

4

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.