# how to calculate double sum of GCD(i,j)?

I stumbled upon a programming question which wanted me to calculate : $$G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} gcd(i, j).$$ now I wrote a code to solve this problem but it takes polynomial time to solve this .I asked this question here but I think I need more mathematical insight before solving this algorithmicly. So can someone tell me how should I solve this equation in sublinear time .I think this problem has to do something with dirichlet-convolution but I don't understand how .So please help me understand this.

this is anothe one

$$S(A,B) = \sum _{a=1}^{A} \sum _{b=1}^{B} {a*b } \ f(gcd(a,b))$$ Here, f(n)=n, if n is square free otherwise 0. Also f(1)=1. for this one also I was able to write

  _CACHE = {}
def G(a, b):
a = a % DIVISOR
b = b % DIVISOR
key = (a, b) if a > b else (b, a)
if key not in _CACHE:
_CACHE[key] = (a * b * F(fractions.gcd(a, b))) % DIVISOR
return _CACHE[key]

def S(A, B):
s = 0
for a in range(1, A+1):
for b in range(1, B+1):
s += G(a, b)
return s

#there is also a code for checking square free number but I have not posted it ,
Here I just wanted to show the time comlexity of the real code which computes


here also as you can see I have polynomial time complexity .Maybe there is a mathematical way to reduce this where it is solvable in linear or sublinear time .Please help me out.

• How many pairs $(i,j)$ with $1 \leqslant i < j \leqslant k$ and $\gcd(i,j) = d$ are there? (The case $d = 1$ is of special relevance.) – Daniel Fischer Apr 20 '16 at 19:56
• I'm not asking for the first summation. I'm hinting at how this problem may be efficiently attacked. Admittedly, the hint is vague, but I don't want to spoil the challenge. – Daniel Fischer Apr 20 '16 at 20:31
• @DanielFischer I think there are k**2-k(k+1)/2 pairs – sid Apr 20 '16 at 20:48
• Nope, no such easy formula. For a fixed $d$, how many pairs …, the answer must of course depend on $d$ [and on $k$]. – Daniel Fischer Apr 20 '16 at 20:55

Classifying according to the value $d$ of $\gcd(p,q)$ we get

$$\sum_{p=1}^n\sum_{q=p+1}^n \gcd(p, q) = \sum_{d=1}^n d \sum_{q=2}^{\lfloor n/d\rfloor} \varphi(q) = -\frac{1}{2} n(n+1) + \sum_{d=1}^n d \sum_{q=1}^{\lfloor n/d\rfloor} \varphi(q).$$

This is

$$-\frac{1}{2} n(n+1) + \sum_{dq\le n} d\varphi(q) = -\frac{1}{2} n(n+1) + \sum_{q=1}^n \varphi(q) \sum_{d=1}^{\lfloor n/q\rfloor} d.$$

The final answer is therefore

$$-\frac{1}{2} n(n+1) + \frac{1}{2} \sum_{q=1}^n \varphi(q) \lfloor n/q\rfloor (\lfloor n/q\rfloor + 1) \\ = \frac{1}{2} \sum_{q=2}^n \varphi(q) \lfloor n/q\rfloor (\lfloor n/q\rfloor + 1).$$

Remark. No further comments will be made on this answer so as to keep some of the challenge.

• I do not know much about number theory (but would like to know) an so I do not understand what some of the symbols are in your solution .Can you please tell me what should I read first to understand your solution or (hint) – sid Apr 20 '16 at 21:13
• I suggest you consult Wikipedia on the Euler Totient and use that page as a starting point for additional readings. – Marko Riedel Apr 20 '16 at 21:19