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.
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.