Summation of greatest common divisor: $\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n \frac{(i * j)}{\gcd(i,j)^2}$

Question

$\sum_{i = 1}^n \sum_{j = 1}^n \frac{(i * j)}{GCD(i,j)^2}$

I stuck with this summation equation trying to simplify. First I thought is equal to lcm(i,j) but that doesn't solve it. I have till now solved summation with only one variable like n. But how to tackle problem like this.

Answer 1

The only simplification I can see is to write your formula as $$\sum_{i = 1}^n \sum_{j = 1}^n \frac{(i * j)}{\gcd(i,j)}=\sum_{i = 1}^n \sum_{j = 1}^n \operatorname{lcm}(i,j)$$ To see that $\frac{(i * j)}{\gcd(i,j)}=\operatorname{lcm}(i,j)$, consider the factors of some prime that divides $i$ or $j$. $\gcd(i,j)$ includes the minimum power of that prime between $i$ and $j$. $\operatorname{lcm}(i,j)$ contains the maximum power of that prime between $i$ and $j$, so their product has the same power as $ij$ does.

The double sum just says take all possible pairs of $i,j$, evaluate $\operatorname{lcm}(i,j)$ and add them up. If $n=3$ each of $i,j$ ranges from $1$ to $3$ and you have $9$ terms to add. We can put the terms in an array with $i$ being the row and $j$ being the column (but it is symmetric here) and they are $$\begin {array} {r r r}1&2&3\\2&2&6\\3&6&3 \end{array}$$

Adding all these numbers gives $28$, which is the third entry in the linked sequence.

Answer 2

$$ \begin{align} \sum\limits_{i = 1}^n \sum\limits_{j = 1}^n \frac{(i * j)}{\gcd(i,j)^2} &= \sum_{d = 1} ^ n \sum_{\gcd(i,j) = d} \frac{(i * j)}{d^2} \\ &= \sum_{d = 1} ^ n \sum_{\gcd(i,j) = 1} ^ {1 \leq i,j \leq \lfloor \frac{n}{d} \rfloor} ij \end{align} $$ so we may first compute $f(n) = \sum\limits_{\gcd(i,j) = 1} ^ {1 \leq i,j \leq n} ij = \sum\limits_{l=1} ^n \mu(l) \sum\limits_{l|i} i \sum\limits_{l|j} j =\sum\limits_{l=1} ^n \mu(l)l^2 (\lfloor \frac{n}{l} \rfloor)^2 (\lfloor \frac{n}{l} \rfloor + 1)^2 $, where $mu$ is Mobius function. and $$ \sum\limits_{i = 1}^n \sum\limits_{j = 1}^n \frac{(i * j)}{\gcd(i,j)^2} = \sum\limits_{d = 1}^n f(\lfloor \frac{n}{d} \rfloor ) $$

Oh no, you want compute $\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n \frac{(i * j)}{\gcd(i,j)^2}$ but not $\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n \frac{(i * j)}{\gcd(i,j)}$, so the answer blow is not right.

It is easy to see $\sum_{\gcd(i,n)= 1} i = \frac{n \psi(n)}{2} $, where $\psi(n)$ is Euler's totient function.

let us consider $\sum_{i=1} ^n lcm(i,n)$ $$ \begin{align} \sum_{i=1} ^n lcm(i,n) &= \sum_{i=1} ^n \frac{i \cdot n}{\gcd(i,n)} \\ &= n \sum_{d|n} \sum_{\gcd(i,\frac{n}{d})= 1} i \\ &= \frac{n}{2} \sum_{d|n} \frac{n}{d} \psi(\frac{n}{d}) \\ &= \frac{n}{2} \sum_{d|n} d \psi(d) \end{align} $$

so $$ \begin{align} \sum\limits_{i = 1}^n \sum\limits_{j = 1}^n lcm(i,j) &= 2 \sum_{1 \leq i \leq j \leq n} ^ n lcm(i,j) - \sum_{i=1} ^n i \\ &= \sum_{i = 1} ^n i \sum_{d|i} d \psi(d) - \frac{n(n+1)}{2} \\ &= \sum_{d = 1} ^n d \psi(d) \sum_{d|i} i - \frac{n(n+1)}{2} \\ &= \frac{ \sum_{d = 1} ^n d \psi(d) \lfloor \frac{n}{d} \rfloor (\lfloor \frac{n}{d} \rfloor + 1) - n(n+1)}{2} \\ \end{align} $$