¿cómo calcular la suma doble de GCD(i,j)?

Question

Me topé con una pregunta de programación que quería que calculara : $$G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} gcd(i, j).$$ Ahora he escrito un código para resolver este problema, pero se necesita un tiempo polinomial para resolver esto. hice esta pregunta aquí pero creo que necesito más conocimientos matemáticos antes de resolver esto algorítmicamente. Así que alguien me puede decir cómo debo resolver esta ecuación en tiempo sublineal. Creo que este problema tiene que ver algo con dirichlet-convolución, pero no entiendo cómo. Así que por favor me ayude a entender esto.

este es otro

$$S(A,B) = \sum _{a=1}^{A} \sum _{b=1}^{B} {a*b } \ f(gcd(a,b))$$ Aquí, f(n)=n, si n es cuadrado libre de lo contrario 0. También f(1)=1. Para este también pude escribir

  _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

Tal vez haya una forma matemática de reducirlo a un tiempo lineal o sublineal. Por favor, ayúdenme.

Answer 1

Clasificar según el valor $d$ de $\gcd(p,q)$ obtenemos

$$\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).$$

Esto es

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

Por tanto, la respuesta final es

$$-\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).$$

Observación. No se harán más comentarios sobre esta respuesta con el fin de mantener parte del desafío.