algorithm - npr - permutations

Reverse factorial

Question

Bueno, todos sabemos que si se da N, es fácil calcular N !. Pero, ¿y el inverso?

¡NORTE! se da y está a punto de encontrar N - ¿Es eso posible? Soy curioso.

Answer 1

¡norte! es muy fácil de factorizar Entonces sigue dividiendote por 2,3,5,7 ... y revisa los exponentes, cuantas veces puedes dividir.

Ahora la pregunta es si tienes n! ¿Cuál es el exponente de primo p en él?

¡Primero N! puede tener solo primos hasta n, posiblemente incluyendo n si es primo.

Está agregando uno por cada vez que prime p o cualquiera de sus poderes está dentro de n. Cuantas veces verás p. Bueno, tiene que ser el mayor k para el cual

sentido

lo mismo de las principales potencias

El algoritmo sigue.

Supongamos que tenemos 10888869450418352160768000000

Podemos dividirnos con

2, 23 veces

3, 13 veces

5, 6

7, 3

11, 2

13, 2

17, 1

23, 1

no divisible por 29

Esto significa que es un número entre 23 y 29. (Normalmente, el rango es mucho más grande, pero este ejemplo aún es útil).

Ahora podemos usar la búsqueda binaria entre 23 y 29 para obtener el conjunto que puede ser divisible por 2, 23 veces. Tenga en cuenta que solo puede haber dos de esos números. Intentamos 26 y encontramos fácilmente que es

Si este no fuera el caso, continuaríamos el segmento 23 a 26 o 26 a 29 dependiendo del resultado.

Entonces es 26 o 27. Hacemos lo mismo por 3 y el resto hasta que obtengamos el partido para cualquiera de los dos números posibles. Los números tendrán un resultado diferente para al menos uno de los primos dados.

Entonces, si lo anterior es un factorial, es el factorial de 27. Verificar lo mismo que el anterior para 5,7,11,13,17,19 y 23 muestra que todo está bien y que en realidad es 27.

Answer 2

1. Establecer X=1 .
2. Generar F=X!
3. ¿F = la entrada? Si es así, entonces X es N.
4. De lo contrario, configure X=X+1 , luego comience nuevamente en # 2.

Puede optimizar utilizando el resultado previo de F para calcular la nueva F ( new F = new X * old F ).

Es tan rápido como ir en la dirección opuesta, si no más rápido, dado que la división generalmente lleva más tiempo que la multiplicación. Un factorial dado A! se garantiza que tiene todos los enteros menores que A como factores además de A, por lo que gastaría el mismo tiempo en factorizarlos que en computar un factorial en ejecución.

Answer 3

¡Si no sabes si un número M es N! o no, una prueba decente es probar si es divisible por todos los números primos pequeños hasta que la aproximación de Sterling de ese primo sea mayor que M Alternativamente, si tiene una tabla de factoriales pero no va lo suficientemente alto, puede elegir el factorial más grande en su tabla y asegurarse de que M sea ​​divisible por eso.

Answer 4

Bueno, si sabes que M es realmente el factorial de un entero, entonces puedes usar

n! = Gamma(n+1) = sqrt(2*PI) * exp(-n) * n^(n+1/2) + O(n^(-1/2))

Puedes resolver esto (o, realmente, resolver ln(n!) = ln Gamma(n+1) ) y encontrar el entero más cercano. Todavía no es lineal, pero puede obtener una solución aproximada por iteración fácilmente (de hecho, espero que el factor n^(n+1/2) sea ​​suficiente).

Answer 5

Múltiples formas. Use tablas de búsqueda, use búsqueda binaria, use una búsqueda lineal ...

Las tablas de búsqueda son obvias:

for (i = 0; i < MAX; ++i)
Lookup[i!] = i; // you can calculate i! incrementally in O(1)

Podría implementar esto usando tablas hash por ejemplo, o si usa C ++ / C # / Java, tienen sus propios contenedores tipo tabla hash.

Esto es útil si tiene que hacer esto muchas veces y cada vez tiene que ser rápido, pero puede darse el lujo de dedicar algún tiempo a construir esta tabla.

Búsqueda binaria : suponga que el número es m = (1 + N!) / 2 . Es m! más grande que N! ? Si es así, ¡reduzca la búsqueda entre 1 m! , de lo contrario, reducirlo entre m! + 1 m! + 1 y N! . Recursivamente aplica esta lógica.

Por supuesto, estos números pueden ser muy grandes y podrías terminar haciendo muchas operaciones no deseadas. Una mejor idea es buscar entre 1 y sqrt(N!) Utilizando la búsqueda binaria, o tratar de encontrar aproximaciones aún mejores, aunque esto podría no ser fácil. Considera estudiar la función gamma .

Búsqueda lineal : Probablemente lo mejor en este caso. Calcule 1*2*3*...*k hasta que el producto sea igual a N! y salida k .

Answer 6

Sí. Vamos a llamar a su entrada x. Para valores pequeños de x, puedes probar todos los valores de n y ver si n! = x. Para una x más grande, puede buscar binaria sobre n para encontrar la n correcta (si existe). Tenga en cuenta que tenemos n! ≈ e ^ (n ln n - n) (esta es la aproximación de Stirling ), para que sepa aproximadamente dónde mirar.

El problema, por supuesto, es que muy pocos números son factoriales; entonces tu pregunta tiene sentido solo para un pequeño conjunto de entradas. Si su entrada es pequeña (por ejemplo, cabe en un entero de 32 o 64 bits), una tabla de búsqueda sería la mejor solución.

(Por supuesto, podría considerar el problema más general de invertir la función Gamma . De nuevo, la búsqueda binaria sería probablemente la mejor, en lugar de algo analítico. Me alegraría que me mostraran mal aquí).

Editar : en realidad, en el caso de que no esté seguro de que x es un número factorial, no puede obtener tanto (o nada) con la búsqueda binaria usando la aproximación de Stirling o la función Gamma, en lugar de soluciones simples. El factorial inverso crece más lento que el logarítmico (esto es porque el factorial es superexponencial), y tienes que hacer aritmética de precisión arbitraria para encontrar factoriales y multiplicar esos números de todos modos.

Por ejemplo, vea la respuesta de Draco Ater para una idea que (cuando se extiende a la aritmética de precisión arbitraria) funcionará para todo x. Incluso más simple, y probablemente incluso más rápido porque la multiplicación es más rápida que la división, es la respuesta de Dav, que es el algoritmo más natural ... parece que este problema es otro triunfo de la simplicidad. :-)

Answer 7

int p = 1,i;
//assume variable fact_n has the value n!
for(i = 2; p <= fact_n; i++) p = p*i;
//i is the number you are looking for if p == fact_n else fact_n is not a factorial

Sé que no es un pseudocódigo, pero es bastante fácil de entender

Answer 8

Si tienes Q = N! en binario, cuente los ceros finales. Llamar a este número J.

Si N es 2K o 2K + 1, entonces J es igual a 2K menos el número de 1 en la representación binaria de 2K, así que agregue 1 una y otra vez hasta que el número de 1 que ha agregado sea igual al número de 1 en el resultado.

Ahora sabes 2K, y N es 2K o 2K + 1. Para saber cuál es, cuente los factores del primo más grande (o cualquier primo, realmente) en 2K + 1, y úselo para probar Q = (2K + 1) !.

Por ejemplo, supongamos que Q (en binario) es

1111001110111010100100110000101011001111100000110110000000000000000000

(Lo siento, es muy pequeño, pero no tengo herramientas útiles para manipular números más grandes).

Hay 19 ceros al final, que es

10011

Ahora incremente:

1: 10100
2: 10101
3: 10110 bingo!

Entonces N tiene 22 o 23. Necesito un factor primo de 23, y, bueno, tengo que elegir 23 (sucede que 2K + 1 es primo, pero no planeé eso y no es necesario). ¡Entonces 23 ^ 1 debería dividir 23 !, no divide Q, entonces

N=22

Answer 9

inverse_factorial( X )
{
X_LOCAL = X;
ANSWER = 1;
while(1){
if(X_LOCAL / ANSWER == 1)
return ANSWER;
X_LOCAL = X_LOCAL / ANSWER;
ANSWER = ANSWER + 1;
}
}

Answer 10

Comprueba las funciones gamma inversas desde aquí http://functions.wolfram.com/GammaBetaErf/InverseGammaRegularized/ Tienen aproximaciones múltiples

Answer 11

Aquí hay un código de Clojure:

(defn- reverse-fact-help [n div]
(cond (not (= 0 (rem n div))) nil
(= 1 (quot n div)) div
:else (reverse-fact-help (/ n div) (+ div 1))))
(defn reverse-fact [n] (reverse-fact-help n 2))

Supongamos que n = 120, div = 2. 120/2 = 60, 60/3 = 20, 20/4 = 5, 5/5 = 1, retorno 5

Supongamos que n = 12, div = 2. 12/2 = 6, 6/3 = 2, 2/4 = .5, devuelve ''nil''

Answer 12

En C desde mi aplicación Advanced Trigonometry Calculator v1.6.8

 double arcfact(double f) {
double i=1,result=f;
while((result/(i+1))>=1) {
result=result/i;
i++;
}
return result;
}

¿Lo que piensas de eso? Funciona correctamente para enteros de factoriales.

Answer 13

¡Esta función se basa en aproximaciones sucesivas! Lo creé y lo implementé en Advanced Trigonometry Calculator 1.7.0

double arcfact(double f){
double result=0,precision=1000;
int i=0;
if(f>0){
while(precision>1E-309){
while(f>fact(result+precision)&&i<10){
result=result+precision;
i++;
}
precision=precision/10;
i=0;
}
}
else{
result=0;
}
return result;
}

Answer 14

La mayoría de los números no están en el rango de salidas de la función factorial. Si eso es lo que quiere probar, es fácil obtener una aproximación usando la fórmula de Stirling o la cantidad de dígitos del número objetivo, como han mencionado otros, luego realizar una búsqueda binaria para determinar los factores superiores e inferiores al número dado.

Lo que es más interesante es construir el inverso de la función Gamma, que amplía la función factorial a números reales positivos (y también a la mayoría de los números complejos). Resulta que la construcción de un inverso es un problema difícil. Sin embargo, se resolvió explícitamente para la mayoría de los números reales positivos en 2012 en el siguiente documento: http://www.ams.org/journals/proc/2012-140-04/S0002-9939-2011-11023-2/S0002- 9939-2011-11023-2.pdf . La fórmula explícita se da en el Corolario 6 al final del documento.

Tenga en cuenta que implica una integral en un dominio infinito, pero con un análisis cuidadoso creo que se podría construir una implementación razonable. Si eso es mejor que un simple esquema de aproximación sucesiva en la práctica, no lo sé.

Answer 15

Simplemente divida por números positivos, es decir: 5! = 120 - >> 120/2 = 60 || 60/3 = 20 || 20/4 = 5 || 5/5 = 1

Entonces, el último número antes del resultado = 1 es su número.

En el código, podrías hacer lo siguiente:

number = res
for x=2;res==x;x++{
res = res/x
}

o algo así. Este cálculo necesita una mejora para los números no exactos.

Answer 16

int inverse_factorial(int factorial){
int current = 1;
while (factorial > current) {
if (factorial % current) {
return -1; //not divisible
}
factorial /= current;
++current;
}
if (current == factorial) {
return current;
}
return -1;
}

Answer 17

Código C / C ++ para what the factorial ( r es el factorial resultante):

int wtf(int r) {
int f = 1;
while (r > 1)
r /= ++f;
return f;
}

Pruebas de muestra:

Call: wtf(1)
Output: 1
Call: wtf(120)
Output: 5
Call: wtf(3628800)
Output: 10