Fórmula de Legendre

La fórmula de Legendre determina el exponente de la mayor potencia de un número primo $p que divide (es factor de) el factorial de un 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 a 27!.

La fórmula devuelve la suma de varias fracciones (redondeadas hacia abajo), con $n como numerador y una potencia cada vez mayor de $p como denominador. El proceso se detiene cuando el denominador supera al numerador.

Para ilustrarlo:

$p = 5;
$n = 100;

intdiv($n, $p) + intdiv($n, $p * $p);
// No incluyas intdiv($n, $p * $p * $p), porque 125 > 100.

$p = 2;
$n = 128;

intdiv($n, $p) + intdiv($n, $p * $p) + intdiv($n, $p * $p * $p);
// Continúa hasta intdiv($n, 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 sea mayor que $n, el resultado debe ser 0.