7 votos

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

Me topé con una programación pregunta que me quería para calcular : $$G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} gcd(i, j).$$ ahora he escrito un código para resolver este problema, sino que toma el polinomio de tiempo para resolver esto .Hice esta pregunta aquí , pero creo que necesito más matemático de la visión antes de la resolución de este algorithmicly. Así que puede que alguien me diga cómo debo resolver esta ecuación en sublinear tiempo .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 uno anothe

$$S(A,B) = \sum _{a=1}^{A} \sum _{b=1}^{B} {a*b } \ f(gcd(a,b))$$ Aquí, f(n)=n, si n es un cuadrado libre de lo contrario 0. También f(1)=1. para este también era capaz de 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

aquí también, como se puede ver he polinomio tiempo de complejidad .Tal vez hay una manera matemática para reducir este donde es soluble en lineal o sublinear tiempo .Por favor, ayúdenme.

1voto

Marko Riedel Puntos 19255

Clasificación según el valor de $d$ $\gcd(p,q)$ tenemos

$$\sum_{p=1}^n\sum_{p=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).$$

Este 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/p\rfloor} d.$$

La respuesta final es por lo tanto

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

Observación. Sin más comentarios se harán en esta respuesta, así como a mantener un poco de desafío.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X