Cantidad de divisores / suma de divisores

En este artículo discutimos cómo calcular la cantidad de divisores $d(n)$ y la suma de divisores $\sigma(n)$ de un número dado $n$ .

Cantidad de divisores

Debería ser obvio que la factorización prima de un divisor $d$ tiene que ser un subconjunto de la factorización prima de $n$ ; p. ej. $6 = 2 \cdot 3$ es un divisor de $60 = 2^2 \cdot 3 \cdot 5$ . Así que solo hay que hallar todos los subconjuntos distintos de la factorización prima de $n$ .

Usualmente la cantidad de subconjuntos es $2^x$ para un conjunto con $x$ elementos. Sin embargo esto ya no es cierto si hay elementos repetidos en el conjunto. En nuestro caso algunos factores primos pueden aparecer varias veces en la factorización prima de $n$ .

Si un factor primo $p$ aparece $e$ veces en la factorización prima de $n$ , entonces podemos usar el factor $p$ hasta $e$ veces en el subconjunto. Lo que significa que tenemos $e+1$ elecciones.

Por lo tanto, si la factorización prima de $n$ es $p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ , donde los $p_i$ son números primos distintos, entonces la cantidad de divisores es:

$d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)$

Una forma de pensarlo es la siguiente:

Si hay un solo divisor primo distinto $n = p_1^{e_1}$ , entonces obviamente hay $e_1 + 1$ divisores ( $1, p_1, p_1^2, \dots, p_1^{e_1}$ ).
Si hay dos divisores primos distintos $n = p_1^{e_1} \cdot p_2^{e_2}$ , entonces se pueden disponer todos los divisores en forma de tabla.

$\begin{array}{cccccc} 1 & p_{2} & p_{2}^{2} & \dots & p_{2}^{e_{2}} \\ 1 & 1 & p_{2} & p_{2}^{2} & \dots & p_{2}^{e_{2}} \\ p_{1} & p_{1} & p_{1} \cdot p_{2} & p_{1} \cdot p_{2}^{2} & \dots & p_{1} \cdot p_{2}^{e_{2}} \\ p_{1}^{2} & p_{1}^{2} & p_{1}^{2} \cdot p_{2} & p_{1}^{2} \cdot p_{2}^{2} & \dots & p_{1}^{2} \cdot p_{2}^{e_{2}} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ p_{1}^{e_{1}} & p_{1}^{e_{1}} & p_{1}^{e_{1}} \cdot p_{2} & p_{1}^{e_{1}} \cdot p_{2}^{2} & \dots & p_{1}^{e_{1}} \cdot p_{2}^{e_{2}} \end{array}$

Así, la cantidad de divisores es trivialmente $(e_1 + 1) \cdot (e_2 + 1)$ .

Se puede hacer un argumento similar si hay más de dos factores primos distintos.


long long numberOfDivisors(long long num) {
    long long total = 1;
    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            int e = 0;
            do {
                e++;
                num /= i;
            } while (num % i == 0);
            total *= e + 1;
        }
    }
    if (num > 1) {
        total *= 2;
    }
    return total;
}

Suma de divisores

Podemos usar el mismo argumento de la sección anterior.

Si hay un solo divisor primo distinto $n = p_1^{e_1}$ , entonces la suma es:

$1 + p_1 + p_1^2 + \dots + p_1^{e_1} = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1}$

Si hay dos divisores primos distintos $n = p_1^{e_1} \cdot p_2^{e_2}$ , entonces podemos hacer la misma tabla que antes. La única diferencia es que ahora queremos calcular la suma en lugar de contar los elementos. Es fácil ver que la suma de cada combinación se puede expresar como:

$\left(1 + p_1 + p_1^2 + \dots + p_1^{e_1}\right) \cdot \left(1 + p_2 + p_2^2 + \dots + p_2^{e_2}\right)$

$= \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1}$

En general, para $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ obtenemos la fórmula:

$\sigma(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{e_k + 1} - 1}{p_k - 1}$


long long SumOfDivisors(long long num) {
    long long total = 1;
 
    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            int e = 0;
            do {
                e++;
                num /= i;
            } while (num % i == 0);
 
            long long sum = 0, pow = 1;
            do {
                sum += pow;
                pow *= i;
            } while (e-- > 0);
            total *= sum;
        }
    }
    if (num > 1) {
        total *= (1 + num);
    }
    return total;
}

Funciones multiplicativas

Una función multiplicativa es una función $f(x)$ que satisface

$f(a \cdot b) = f(a) \cdot f(b)$

si $a$ y $b$ son coprimos.

Tanto $d(n)$ como $\sigma(n)$ son funciones multiplicativas.

Las funciones multiplicativas tienen una enorme variedad de propiedades interesantes, que pueden ser muy útiles en problemas de teoría de números. Por ejemplo, la convolución de Dirichlet de dos funciones multiplicativas también es multiplicativa.

Cantidad de divisores / suma de divisores