Esta semana me topé con este problema en una competición de CodeForces. Yo sabía que no se resolvía por fuerza bruta (sí, soy un hacha 😜), pero la pregunta era ¿con qué se resuelve entonces? Primero analicemos el problema y luego os presentaré a la función matemática aliada que nos ayudará en la batalla contra este enunciado.

El enunciado es el siguiente. Tenemos dos números enteros y y el problema nos pide que contemos cuantos valores puede tomar el entero tal que y se cumpla . representa el máximo común divisor (greatest common divisor en inglés).

Greatest common divisor

Lo primero es tener claro el significado de máximo común divisor. El máximo común divisor de dos números cualesquiera es la intersección de los factores primos que forman dichos números. Esta imagen de Wikipedia debería dejar más clara la definición:

máximo común divisor explicado gráficamente
Máximo común divisor explicado gráficamente. La intersección de los factores primos de 48 y 60 es: 2, 2, y 3. Por lo tanto, el \(\gcd(48, 60) = 2 \cdot 2 \cdot 3 = 12\). Dicho de otra forma, 12 es el número máximo que puede dividir de manera exacta a 48 y a 60. (Imagen: Wikipedia)

El máximo común múltiplo se resuelve eficientemente usando un algoritmo conocido desde tiempos de la antigua Grecia. Se trata del algoritmo de Euclides.

Desarrollo del problema

Una vez entendidos todos los elementos que aparecen en el enunciado del problema podemos proceder con su resolución.

Definamos . ¿Qué podemos decir de los valores de que cumplen el requerimiento del enunciado? Sabemos que por la propia definición de dada en el enunciado. ¿Qué más sabemos? Sabemos que entre los factores primos que componen deben encontrarse aquellos que componen , y pueden contener otros factores distintos de aquellos que componen (es decir, los factores que componen excepto aquellos que forman parte del ). Utilicemos los números y del ejemplo de la anterior imagen para aclarar esto último que he dicho. . debe de tener 2, 2, y 3 entre sus factores pero no el 5. Si no tuviera ni 2, 2 o 3 entre sus factores, o si tuviera el 5, sería distinto de 12. Dicho de otra forma, debe de ser un múltiplo de 12 que no contenga el 5 entre sus factores.

Vamos a definir , ¿cuántos valores de no contienen el número 5 entre sus factores? Dicho de otra forma, ¿cuántos números primos relativos a 5 hay? Realmente hay infinitos, pero ¿cuántos hay en el rango ? Los valores que puede tomar son 4, 5, 6, 7 y 8 para que esté en el rango indicado. De todos esos, obviamente el 5 no es primo relativo de 5. Por lo que los valores válidos de son 4.

¿Cómo podemos simplificar ese cálculo? Para ello hay que darse cuenta de una cosa. Para todo valor de . Si esto no te convence haz una pausa y convéncete a ti mismo de que esto es así. Busca recursos sobre el máximo común divisor para entenderlo mejor. Además, como , sabemos que hay valores distintos de . Esto básicamente transforma nuestra pregunta a: ¿cuántos valores de menores de 5 son coprimos de 5?

Euler Phi function o Euler Totient function

¿Cómo podemos automatizar este cálculo? La respuesta directa a esta pregunta la da la función de Euler, también conocida como la función indicatriz de Euler (Totient function en inglés). Esta función devuelve la cantidad de números menores de que son primos relativos de . Justo lo que necesitamos.

Puesto que esta función nos da lo que necesitamos, lo que debemos programar es:

Vamos a ir desgranando el comportamiento de esta función. Empezando con una definición formal, que no viene siendo más que la forma matemática de escribir lo comentado en el párrafo anterior.

es el número de elementos (denotado por ) del conjunto () formado por los números naturales (, no incluye el 0) que son menores de y que son primos relativos o coprimos de (dicho de otra forma, ).

Empecemos con algún ejemplo. Supongamos que queremos obtener todos los números menores de 11 y coprimos a 11. Pues bien, es fácil darse cuenta de que 11 es un número primo, por lo que hay 10 números naturales menores que 11 que no comparten ningún factor primo con él:

Siendo un número primo, la fórmula general es:

¿Qué pasa con ?

8 no es primo, pero puede descomponerse fácilmente en . En lugar de pintarlo como una lista vamos a distribuirlo como una matriz con columnas:

Se observa que la última columna contiene todos los múltiplos de , lo cuál es bastante obvio porque la última columna es la columna . Para extraer la fórmula general de quizás sea útil pintar otro ejemplo. Pintemos :

Puedes pintar algunos casos más si lo deseas, pero yo paso directamente a mostrarte la expresión general. La forma de calcularlo es tomando el total de números y restándole la cantidad de números que hay en la última columna:

Seguimos. ¿Cuánto vale ? 15 no es primo ni es la potencia de un primo, así que la fórmula anteriormente expuesta no sirve. , por lo que cualquier número menor de 15 que esté formado por el factor primo 3 o el factor primo 5 no es coprimo de 15 y no debemos de contarlo.

De nuevo, pintemos en forma de matriz los números:

Esta vez es un poco más difícil de verlo, pero tenemos que . Si calculamos el resto (operación módulo) de cada uno de los valores al dividirlos entre 3, todos los números de una columna dan el mismo resto: la primera columna resto 1, la segunda columna resto 2 y la última columna resto 0. Si calculamos el resto para el 5 obtenemos que en cada columna los restos son todos distintos unos a otros, es decir, que los restos van de 0 a 4. Por ejemplo, en la primera columna de arriba a abajo los restos son: 1, 4, 2, 0 y 3. Todos los números son distintos, y solo el elemento que da de resto 0 es múltiplo de 5.

Esto se puede probar más rigurosamente pero no lo haré en este artículo. En las referencias podrás encontrar otros recursos que profundizan más en el tema.

De forma más general, para cualquier número , siendo el primo que compone y el número de veces que aparece dicho primo en la descomposición, se puede escribir la siguiente expresión general:

Implementación

La implementación no tiene mayor historia, es implementar una factorización y posteriormente una multiplicación de los primos (ignorando el exponente de dichos primos).

La implementación de que usamos es la que está incluida en el módulo estándar de Python math.

def prime_factors(n):
    """Return a list of the prime factors that compose n. """

    # Factorization is defined for natural numbers.
    assert n > 0

    # Base case.
    if n == 1:
        return [1]

    f = []
    # Check 2 first for saving half iterations in the next for loop.
    while n % 2 == 0:
        f.append(2)
        n /= 2
    # Check the odd numbers.
    for i in range(3, int(n**0.5) + 1, 2):
        while n % i == 0:
            f.append(i)
            n /= i

    # Prime number case.
    if n > 1:
        f.append(int(n))

    return f


def eulers_phi_fun(n):
    """Euler's Totient function. """

    f = prime_factors(n)
    val = n
    # Iterate for the unique list of primes.
    for i in set(f):
        val *= 1 - 1 / i
    return int(val)


def solve(a, m):
    """Solve problem for the given a and m. """

    gcd = math.gcd(a, m)
    n = m / gcd
    phi = eulers_phi_fun(n)
    print(phi)

Referencias

Aquí te dejo una lista de enlaces que me ayudaron a entender de qué iba eso de la función de Euler. No solo explican qué es, sino que incluyen muy buenos ejemplos y demostraciones para entenderla en profundidad.

Altamente recomendados estos dos vídeos de Michael Penn:

Otros recursos: