Cómo simplificar $F(k)=\sum\limits_{n=1}^k\sum\limits_{d|n}\gcd({d},{\frac{n}{d}})$ ?

Question

Tengo el siguiente resumen:

$$F(k)=\sum\limits_{n=1}^k\sum\limits_{d|n}\gcd\left({d},{\frac{n}{d}}\right)$$

Esto es casi imposible de calcular (mediante codificación) para números grandes, debido al tiempo que llevaría.

Se ha sugerido que la suma anterior puede simplificarse a esto:

$$F(k)=\sum_{d=1}^{d^2\leqslant k}\ \sum_{n=1}^{nd\leqslant k}\gcd({d},{n})$$

He intentado probar la simplificación y no funciona. Por ejemplo, F(10) da una salida de 22 en lugar de 32.

¿Cómo simplifico la primera suma?

Las cosas aquí podrían ser relevantes, pero no estoy seguro: Wikipedia: Función Divisor.

EDIT: Algoritmo para la sugerencia de thefunkyjunky:

long k = 10;

    for (long d = 1; d*d <= k; d++) {
        for(long n = 1; n*d <= k; n++) {
            if (d*d <= n) result = result.add(BigInteger.valueOf(GCD(d,n)));
        }
    }

Answer 1

He encontrado otra forma de calcularlo, aunque no respondo realmente a la pregunta de cómo reordenar la suma original.

Empecé por considerar por mí mismo las posibles parejas y los $gcd$ s:

n= 1:  (1,1)                        1                 f( 1)=1   F( 1)= 1
n= 2:  (1,2)  (2,1)                 1  1              f( 2)=2   F( 2)= 3 
n= 3:  (1,3)  (3,1)                 1  1              f( 3)=2   F( 3)= 5
n= 4:  (1,4)  (2,2)  (4,1)          1  2  1           f( 4)=4   F( 4)= 9
n= 5:  (1,5)  (5,1)                 1  1              f( 5)=2   F( 5)=11
n= 6:  (1,6)  (2,3)  (3,2)  (6,1)   1  1  1  1        f( 6)=4   F( 6)=15
n= 7:  (1,7)  (7,1)                 1  2  1           f( 7)=2   F( 7)=17
n= 8:  (1,8)  (2,4)  (4,2)  (8,1)   1  2  2 1         f( 8)=6   F( 8)=23
n= 9:  (1,3)  (3,3)  (9,1)          1  3  1           f( 9)=5   F( 9)=28
n=10: (1,10)  (2,5)  (5,2) (10,1)   1  1  1  1        f(10)=4   F(10)=32

No me pareció obvio lo que ocurría aquí, así que expuse los mismos resultados así:

Me he dado cuenta de que la tabla puede verse como un conjunto de "V" invertidas.

Las entradas para $(1,n)$ y $(n,1)$ hacer una de esas V: con toda la $gcd$ igual a 1.

Las entradas para $(2,\frac n2)$ y $(\frac n2,2)$ hacer otra V (marcada en verde): pero las entradas comienzan con 2 y luego alternan 1, 2, 1, 2, ...

Es importante señalar también que el $i$ El V comienza en $n=i^2$ con un único valor $gcd = i$ y continúa con $2(i-1)$ valores de $gcd=1$ y luego 2 valores de $gcd=i$ y este patrón se repite.

Según mi método tenemos $F(n)=\Sigma_{i=1}^{i={\sqrt n}}V(i,n)$

donde $V(i,n)$ es la suma de los valores del $i$ V y se encuentra mediante este algoritmo:

Encontrar enteros positivos $p$ y $q$ para que $n=pi^2+qi+r$ .

Entonces $V(i,n)=i + 2(p-1)(2i-1)+2q$

Creo que esto podría ser mejor porque no hay necesidad de calcular ningún $gcd$ .

Answer 2

Se puede utilizar el hecho de que si d es un divisor tal que $d<\sqrt{n}$ entonces $\frac{n}{d} > \sqrt{n}$ y $\frac{n}{d}$ también es un divisor de $n$ . Así que $gcd(d, \frac{n}{d})$ forman pares de gcds, lo que significa que se puede calcular para divisores sólo menores que $\sqrt{n}$ y luego multiplicar la suma por $2$ que es (creo) lo suficientemente rápido.

EDITAR: Se me olvidó añadir que hay que hacer un caso especial cuando $n$ es un cuadrado, porque entonces tienes $d$ que $d^2=n$ y el $gcd(d, d)$ El factor debe contarse sólo una vez, no dos.

EDIT2: El algoritmo que tenía en mente era:

long sum = 0;
for(int n = 1; n <= k; n++) {
    for(int d = 1; d <= sqrt(n); d++) {
        if(n % d == 0) {
            if(d * d != n)
                sum += gcd(d, n / d) * 2;
            else
                sum += d; // GCD(d, d) = d
        }
    }

}

Pero creo que el tuyo es más rápido. Lo que haces (si no lo has entendido) en tu algoritmo es simplemente encontrar todos los pares $(x, y)$ tal que $xy \leq k$ lo que significa que su gcd se incluye en la suma como divisores de algún $n = xy$

EDIT3: El algoritmo que has intentado implementar en primer lugar (la suma reescrita) tiene un error. Se puede escribir como(Lo siguiente es una combinación de mi solución y la tuya):

int sum = 0;                                                                                            
for(int x = 1; x * x <= k; x++) {                                                                        
     for(int y = x; x * y <= k; y++) {                                                                    

         if(x != y) sum += 2 * gcd(x, y);                                                                
         else sum += x;                                                                                  

     }                                                                                                   
 }   

¡Por favor, comenten para decirme si pasa (yo también estoy interesado)!