12
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Apr 17, 2012 at 14:48
  • $\begingroup$ The text is incorrect (should be the remainder of $n$ divided by $r$) $\endgroup$
    – Igor Rivin
    Commented Apr 17, 2012 at 14:56
  • $\begingroup$ Can the OP prove this, or is this an experimental fact? $\endgroup$
    – Igor Rivin
    Commented Apr 17, 2012 at 14:56
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Apr 17, 2012 at 14:57
  • $\begingroup$ @Igor: thanks for spotting the typo. And no, I cannot prove this, this is purely experimental. $\endgroup$
    – unknown
    Commented Apr 17, 2012 at 14:59

1 Answer 1

Reset to default
19
$\begingroup$

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}

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Apr 17, 2012 at 15:32
  • $\begingroup$ You are right, hopefully it is more clear now. $\endgroup$
    – Emil Jeřábek
    Commented Apr 17, 2012 at 15:45
  • 5
    $\begingroup$ 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). $\endgroup$
    – Anonymous
    Commented Apr 17, 2012 at 16:32
  • 1
    $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Commented Apr 18, 2012 at 16:11

You must log in to answer this question.

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