Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $R(n)$ denote the sum of all positive rational numbers whose numerators and denominators are less than or equal to $n$ and have no common factors. I have estimated this sum to be $$ \begin{align*} R(n)=\sum_{\substack{a,b\leq n\\ (a,b)=1}}\frac{a}{b}&=\sum_{m\leq n}\sum_{\substack{k\leq m\\ (m,k)=1}}\frac{m}{k}+\sum_{m\leq n}\sum_{\substack{k\leq m\\ (m,k)=1}}\frac{k}{m}-1\\ &=\frac{1}{2}n^2\left(\frac{6}{\pi^2}(\log n+\gamma)+A\right)+O(n), \end{align*} $$ using this technique and some well-known facts from analytic number theory. Here $\gamma$ is the Euler-Mascheroni constant and $A=-\sum_{n=1}^\infty\frac{\mu(n)}{n^2}\log n=0.3465...$.

Is there any literature on this sum (or something similar)? And if so, is there an estimate with an error term smaller than $n$?

share|cite|improve this question
For each $n>1$ there are $\phi(n)$ summands and they exactly average to $\frac 12$ because with $\frac an$ you also hav $\frac{n-a}n$. Hence the exact sum is (noting the special case $n=1$) $$ R(n)=\frac12 +\frac12\sum_{k=1}^n \phi(k) $$ – Hagen von Eitzen May 16 '13 at 6:13
@HagenvonEitzen The sum $R(n)$ includes fractions exceeding $1$, so you seem to be missing the reciprocals of those terms. – Erick Wong May 16 '13 at 6:17
A concise way to describe the summands is "positive rationals of height up to $n$". – Erick Wong May 16 '13 at 6:21
@HagenvonEitzen: the proof is a bit too long to post but I'll edit in a general outline. – 77474 May 16 '13 at 6:28
@ErickWong: Ok, that good to know. Thanks! – 77474 May 16 '13 at 6:28

I am not sure if there is anything in the literature, but it can be rephrased in terms of the average of the reciprocals of the Farey sequence. See this related MSE thread for a similar series which yields a nearly identical main term. I include a short proof of your stated result at the bottom - it is better to keep the sum together rather than splitting it up.

Let $F_{k}$ denote the Farey sequence of order $k$, so that when $k=6$ we have $$F_{6}=\left\{ \frac{0}{1},\ \frac{1}{6},\ \frac{1}{5},\ \frac{1}{4},\ \frac{1}{3},\ \frac{2}{5},\ \frac{1}{2},\ \frac{3}{5},\ \frac{2}{3},\ \frac{3}{4},\ \frac{4}{5},\ \frac{5}{6},\ \frac{1}{1}\right\}.$$ In particular, $|F_{k}|=1+\sum_{n\leq k}\phi(n)$. Then your above identity is equivalent to the fact that

$$\mathbb{E}_{y\in F_{N}}\frac{1}{y}=\log N+\gamma-\frac{\zeta'(2)}{\zeta(2)}-\frac{1}{2}+O\left(\frac{\log^{2}N}{N}\right)$$

To see why, notice that $$\sum_{\begin{array}{c} a,b\leq N\\ (a,b)=1 \end{array}}\frac{b}{a}=-1+\sum_{y\in F_{N}}y+\sum_{y\in F_{N}}\frac{1}{y}.$$ As the Farey sequence is symmetry, we can see that $$\sum_{y\in F_{N}}y=\frac{1}{2}|F_{n}|,$$

and since $|F_{N}|=1+\sum_{n\leq N}\phi(n)=\frac{3}{\pi^{2}}N^{2}+O\left(N\log N\right)$, it follows that \begin{eqnarray*} \mathbb{E}_{y\in F_{N}}\frac{1}{y} & = & \frac{1}{|F_{N}|}\sum_{y\in F_{N}}\frac{1}{y}\\ & = & \log N+\gamma-\frac{\zeta'(2)}{\zeta(2)}-\frac{1}{2}+O\left(\frac{\log^{2}N}{N}\right), \end{eqnarray*}

A short proof: Using Möbius inversion, we have that $$ \sum_{\begin{array}{c} a,b\leq N\\ (a,b)=1 \end{array}}\frac{b}{a}=\sum_{a,b\leq N}\frac{b}{a}\sum_{d|a,b}\mu(d)=\sum_{d\leq N}\mu(d)\sum_{a\leq\frac{N}{d}}\sum_{b\leq\frac{N}{d}}\frac{b}{a}. $$ Using the fact that $\sum_{n\leq N}n=\frac{\left[N\right]}{2}\left(\left[N\right]+1\right)$, and the expansion of the harmonic series, this becomes $$ \sum_{d\leq N}\mu(d)\sum_{a\leq\frac{N}{d}}\frac{1}{a}\sum_{b\leq\frac{N}{d}}b=\frac{1}{2}\sum_{d\leq N}\mu(d)\left(\left[\frac{N}{d}\right]^{2}+\left[\frac{N}{d}\right]\right)\left(\log\left(\frac{N}{d}\right)+\gamma+O\left(\frac{d}{N}\right)\right), $$ and carefully dealing with the error terms, we arrive at $$ \frac{N^{2}\log N}{2}\sum_{d\leq N}\frac{\mu(d)}{d^{2}}-\frac{N^{2}}{2}\sum_{d\leq N}\frac{\mu(d)}{d^{2}}\log d+\frac{\gamma N^{2}}{2}\sum_{d\leq N}\frac{\mu(d)}{d^{2}}+O\left(N\log^{2}N\right) $$ which becomes $$ \frac{3N^{2}}{\pi^{2}}\left(\log N+\gamma-\frac{\zeta'(2)}{\zeta(2)}\right)+O\left(N\log^{2}N\right). $$ as desired.

share|cite|improve this answer
Ah, I didn't think about actually using the Farey sequence (even though this little exercise was inspired by it). I think there is a problem with your calculations though, but I'm not sure what. I plotted your estimate, my estimate and the function $R(n)$ in Mathematica. The estimate you provided clearly diverges from the other two. Ex: $R(100)=17559.4$, my estimate $=17585.1$, your estimate $=16140.8$ and for $R(1000)$ your estimate is off by $14$%. – 77474 Jun 3 '13 at 4:54
@Carl: The estimates are identical, I just missed a negative sign. Your constant $A$ equals $-\zeta'(2)/zeta(2)^2$. – Eric Naslund Jun 3 '13 at 16:21
Yes, I see now. The zetas in the denominators are supposed to be squared. Thanks! – 77474 Jun 3 '13 at 16:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.