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*}\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*}\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}
Replaced double-backslash-brace pair with single-backslash-brace pair, to fix rendering.
jeq
- 1.2k
- 5
- 16
- 21