Sum of greatest common divisors As usually, let $\gcd(a,b)$ be the greatest common divisor of integer numbers $a$ and $b$.
What is the asymptotics of
$$\frac{1}{n^2} \sum_{i=1}^{i=n} \sum_{j=1}^{j=n} \gcd(i,j)$$
as $n \to \infty?$
 A: The limit should be infinite. A well-known result is that the "probability" of $\gcd(i,j)=1$ is $\frac 6{\pi^2}>\frac12$ for $n$ large enough.
Thus for any $k$ and large enough $n$, the sum (which is the expected value of the $\gcd$) is $$>\frac12\cdot \left(1+2\cdot \frac1{2^2}+3\cdot \frac1{3^2}+\ldots +k\frac1{k^2}\right)=\frac12\left(1+\frac12+\cdots+\frac1k\right)\to\infty$$
A: We can rewrite the sum as 
$$
\begin{align}
S(n)&=\frac{1}{n^2}\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j) \\ &= \frac{1}{n^2}\sum_{g=1}^n\sum_{i\le\lfloor n/g\rfloor}\sum_{\substack{j\le\lfloor n/g\rfloor\\(i,j)=1}} g \\
&= \frac{1}{n^2}\sum_{g=1}^n g\left(-1+2\sum_{i=1}^{\lfloor n/g\rfloor} \varphi(i)\right) \\
&= -\frac{n(n+1)}{2n^2}+\frac{2}{n}\sum_{g=1}^n \frac{g}{n}\sum_{i=1}^{\lfloor n/g\rfloor} \varphi(i)
\end{align}
$$
Write
$$
f(x) = \frac{1}{x}\sum_{i\le x}\varphi(i) = \frac{3x}{\pi^2}+E(x) \\
E(x) = o(\log x)
$$
(see Eric Naslund's exposition) then
$$
\begin{align}
S(n) &= -\frac{1}{2}-\frac{1}{2n}+\frac{2}{n}\sum_{g=1}^{n}f(n/g) \\
&= -\frac{1}{2}-\frac{1}{2n}+\frac{6}{\pi^2}\sum_{g=1}^{n}\frac{1}{g}+\frac{2}{n}\sum_{g=1}^n E(n/g) \\
&= \frac{6}{\pi^2}\log n+\frac{6\gamma}{\pi^2}-\frac{1}{2}+C+o(1) \\
&= \frac{6}{\pi^2}\log n + C' + o(1)
\end{align}
$$
where the constant $C$ arises from
$$
E(x) = o(\log x) \\
\left|\frac{2}{n}\sum_{g=1}^n E(n/g)\right|< \frac{C}{n}\sum_{g=1}^n\log(n/g)=C\left(\log n - \frac{\log n!}{n}\right)=C+o(1)
$$
by Stirling's approximation. Calculations suggest $C=0.39344\cdots, C'=0.24434\cdots$.
A: The limit is infinite. The sum is equal to
$$
\frac{1}{n^2}\sum_{k=1}^n\varphi(k)\left\lfloor\frac nk\right\rfloor^2
$$
and so you're asking about the asymptotic behavior of
$$
\sum_{k=1}^\infty\frac{\varphi(k)}{k^2}
$$
Clearly
$$
\sum_{k<x}\frac{\varphi(k)}{k^2}>\sum_{p<x}\frac{\varphi(p)}{p^2}\sim\log\log x
$$
and
$$
\sum_{k<x}\frac{\varphi(k)}{k^2}<\sum_{k<x}\frac{k-1}{k^2}\sim\log x
$$
so that gives bounds.
A: Of the lattice points $[1,n] \times [1,n], 1-\frac 1{p^2}$ have no factor $p$ in the $\gcd, \frac 1{p^2}-\frac 1{p^4}$ have a factor $p$ in the $\gcd\frac 1{p^4}-\frac 1{p^6}$, have a factor $p^2$ in the $\gcd, \frac 1{p^6}-\frac 1{p^8}$ have a factor $p^3$ in the $\gcd$ and so on.  That means that a prime $p$ contributes a factor $(1-\frac 1{p^2}+p(\frac 1{p^2}-\frac 1{p^4})+p^2({p^4}-\frac 1{p^6})+\dots$ or $\sum_{i=0}^\infty(p^{-i}-p^{-i-2})=\sum_{i=0}^\infty p^{-i}(1-p^{-2})=\frac {1-p^{-2}}{1-p^{-1}}=1+\frac 1p$.  I don't know how to justify the use of the fact that $\gcd$ is multiplicative to turn this into $$\lim_{m \to \infty}\prod_{p \text {prime}}^m(1+\frac 1p)$$ to get the asymptotics, but it seems like it should work by taking, say $m=\sqrt n$ and letting $n \to \infty$ 
