Fórmula de Legendre

La fórmula de Legendre encuentra el exponente de la mayor potencia de algún número primo p que divide (es un factor de) el factorial de algún número n.

Ejemplo de la fórmula de Legendre (p = 2 y n = 27):

Por lo tanto, 2^23 es la mayor potencia de 2 que divide 27!.

La fórmula devuelve la suma de muchas fracciones (redondeadas hacia abajo), con n como numerador y una potencia de p que aumenta progresivamente como denominador, deteniéndose cuando el denominador supera al numerador.

Para ilustrarlo:

p = 5
n = 100

int(100/5) + int(100/25)
# No 100/125 because 125 > 100.

p = 2
n = 128

int(128/2) + int(128/4) + int(128/8) + ... + int(128/128)

Dados p y n, devuelve el resultado de la fórmula de Legendre (consulta Recursos).

Ejemplos

legendre(5, 100) ➞ 24

legendre(2, 128) ➞ 127

legendre(3, 50) ➞ 22

Notas

• p y n serán enteros positivos.
• Cuando p supera a n, el resultado debe ser 0.