Algoritmo para encontrar el N más pequeño de forma que N! es divisible por un primado elevado a una potencia

Question

¿Existe un algoritmo eficiente para calcular el entero N más pequeño de forma que N! es divisible por p^k donde p es un número primo relativamente pequeño y k, un número entero muy grande. En otras palabras,

factorial(N) mod p^k == 0 

Si, dado N y P, que quería encontrar cuántas veces p divide en N !, me gustaría utilizar la conocida fórmula-

k = Sum(floor(N/p^i) for i=1,2,... 

que he hecho La fuerza bruta busca valores pequeños de k, pero ese enfoque se rompe muy rápidamente a medida que k aumenta y no parece haber un patrón que pueda extrapolar a valores más grandes.

Editado 6/13/2011

partir de las sugerencias propuestas por fiver y Hammar, que utilizan una búsqueda cuasi binaria para resolver el problema, pero no del todo de la manera que sugirieron. Utilizando una versión truncada de la segunda fórmula anterior, calculé un límite superior en N como el producto de k y p (usando solo el primer término). Usé 1 como límite inferior. Usando el algoritmo de búsqueda binaria clásico, calculé el punto medio entre estos dos valores y calculé qué k estaría usando este valor de punto medio como N en la segunda fórmula, esta vez con todos los términos que se usan.

Si el k calculado era demasiado pequeño, ajusté el límite inferior y lo repetí. Demasiado grande, primero probé para ver si k calculado en el punto medio-1 era más pequeño que el k deseado. Si es así, se devolvió el punto medio como el N más cercano. De lo contrario, ajusté el punto alto y lo repetí.

Si los k calculados fueron iguales, probé si el valor en el punto medio-1 era igual al valor en el punto medio. Si es así, ajusté el punto alto para que fuera el punto medio y lo repitiera. Si el punto medio-1 era menor que el k deseado, el punto medio se devolvió como la respuesta deseada.

Incluso con valores muy grandes para k (10 o más dígitos), este enfoque funciona con velocidades O (n log (n)).

Answer 1

Utilizando la fórmula que ha mencionado, la secuencia de k valores proporcionados p y N = 1,2... fijos no es decreciente. Esto significa que puede usar una variante de búsqueda binaria para encontrar N dado el k deseado.

• Comience con N = 1 y calcule k.
• Doble N hasta k es mayor o igual que su k deseado para obtener un límite superior.
• Haga una búsqueda binaria en el intervalo restante para encontrar su k.

Answer 2

¿Por qué no prueba la búsqueda binaria por la respuesta, usando la segunda fórmula que mencionó?

Solo necesita considerar valores para N, para los cuales p divide a N, porque si no lo hace, entonces N! y (N-1)! están divididos por la misma potencia de p, por lo que N no puede ser el más pequeño.

Answer 3

OK esto es divertido.

Definir f (i) = (p^i - 1)/(p - 1)

Write k en una especie de "base" divertido donde el valor de la posición i es este f (i).

Hace esto desde el dígito más significativo al menos significativo. Entonces, primero, encuentre la j más grande que f (j) < = k. Luego calcule el cociente y el resto de k/f (j). Almacene el cociente como q_j y el resto como r. Ahora calcule el cociente y el resto de r/f (j-1). Almacene el cociente como q_ {j-1} y el resto como r nuevamente. Ahora calcule el cociente y el resto de r/f (j-2). Y así.

Esto genera una secuencia q_j, q_ {j-1}, q_ {j-2}, ..., q_1. (Tenga en cuenta que la secuencia termina en 1, no en 0.) Luego calcule q_j * p^j + q_ {j-1} * p^(j-1) + ... q_1 * p. Esa es su N.

Ejemplo: k = 9, p = 3. Entonces f (i) = (3^i - 1)/2. f (1) = 1, f (2) = 4, f (3) = 13. Entonces la mayor j con f (j) < = 9 es i = 2 con f (2) = 4. Tome el cociente y el resto de 9/4. Ese es un cociente de 2 (que es el dígito en el lugar de nuestro 2) y el resto de 1.

Para ese resto de 1, encuentre el cociente y el resto de 1/f (1). El cociente es 1, el resto es cero, entonces hemos terminado.

Así q_2 = 2, q_1 = 1. 2 * 3^2 + 1 * 3^1 = 21, que es el derecho N.

tengo una explicación sobre el papel de por qué esto funciona, pero yo no estoy seguro de cómo comunicarlo en el texto ... Tenga en cuenta que f (i) responde a la pregunta, "¿cuántos factores de p hay en (p^i)!". Una vez que encuentras el mayor i, j tal que j * f (i) es menor que k, y te das cuenta de que lo que realmente estás haciendo es encontrar el mayor j * p^i menor que N, el resto se cae del lavado . En nuestro ejemplo p = 3, por ejemplo, obtenemos 4 p contribuidas por el producto de 1-9, 4 más contribuidas por el producto de 10-18, y una contribución más por 21. Esas dos primeras son solo múltiplos de p^2; f (2) = 4 nos dice que cada múltiplo de p^2 contribuye con 4 p más al producto.

[Actualización]

Código Siempre ayuda a aclarar. Guarde el siguiente script de Perl como foo.pl y ejecútelo como foo.pl <p> <k>. Tenga en cuenta que ** es el operador de exponenciación de Perl, bdiv calcula un cociente y el resto para BigInts (enteros de precisión ilimitada) y use bigint le dice a Perl que use BigInts en todas partes.

#!/usr/bin/env perl 

use warnings; 
use strict; 
use bigint; 

@ARGV == 2 
    or die "Usage: $0 <p> <k>\n"; 

my ($p, $k) = map { Math::BigInt->new($_) } @ARGV; 

sub f { 
    my $i = shift; 
    return ($p ** $i - 1)/($p - 1); 
} 

my $j = 0; 
while (f($j) <= $k) { 
    $j++; 
} 
$j--; 

my $N = 0; 

my $r = $k; 
while ($r > 0) { 
    my $val = f($j); 
    my ($q, $new_r) = $r->bdiv($val); 
    $N += $q * ($p ** $j); 
    $r = $new_r; 
    $j--; 
} 

print "Result: $N\n"; 

exit 0; 

Answer 4

Considere

I = (p ⁿ)!

e ignorar otros factores principales que no sean p. El resultado se parece

I = p ^{n * pn-1} * p ^n-2 * ... * p * 1
I = p ^{n + (n-1) + (n-2) + ...2 + 1}
I = p ^{(n + n)/2}

Así que estamos tratando de encontrar el más pequeño n tal que

(n + n)/2> = k

que si recuerdo la ecuación cuadrática derecha nos da

N = p ⁿ, donde n> = (Sqrt (1 + 8k) -1)/2


(P.S. ¿Alguien sabe cómo mostrar el símbolo radical en rebajas)

EDIT:?

Esto está mal. Déjame ver si puedo rescatarlo ...