Reverse factorial

Question

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

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

Answer 1

1. Conjunto X=1.
2. Generar F=X!
3. ¿Es F = la entrada? Si es así, entonces X es N.
4. De lo contrario, configure X=X+1, luego vuelva a comenzar en el n. ° 2.

Puede optimizar utilizando el resultado previo de F para calcular el nuevo 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! garantiza tener todos los números enteros menores que A como factores además de A, por lo que pasaría el mismo tiempo descompensando esos factores como lo haría con un factorial en ejecución.

Answer 2

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 3

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 4

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) (esto es Stirling's approximation), para que sepa aproximadamente dónde buscar.

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 bits o de 64 bits), una tabla de búsqueda sería la mejor solución.

(Por supuesto podría considerar el problema más general de la inversión de la Gamma function. Una vez más, la búsqueda binaria sería probablemente la mejor manera, en lugar de algo analítica. Estaría contento de ser mostrado mal aquí.)

Edit: 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 utilizando la aproximación de Stirling o la función Gamma, sobre 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 todas las 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 5

Bueno, si usted sabe que M es realmente el factorial de un entero, entonces se puede utilizar

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

Puede resolver este (o, en realidad, 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 6

Múltiples maneras. Utilice tablas de búsqueda, utilice la búsqueda binaria, utilice una búsqueda lineal ...

Las tablas de consulta es una obvia:

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

podría implementar esto usando hash tables por ejemplo, o si se utiliza C++/C#/Java, tienen sus propios contenedores tipo 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 un tiempo a construir esta tabla.

Búsqueda binaria: asuma que el número es m = (1 + N!)/2. ¿Es m! más grande que N!? En caso afirmativo, reduzca la búsqueda entre 1 y m!, de lo contrario, reduzca entre m! + 1 y N!. Recursivamente aplica esta lógica.

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

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

Answer 7

Si no sabe si un número es MN! o no, una prueba decente es para probar si es divisible por todos los números primos pequeños hasta que la aproximación de ley de que el primer es mayor que M. Alternativamente, si tiene una tabla de factoriales pero no lo suficientemente alta, puede elegir el factorial más grande en su tabla y asegurarse de que M sea divisible por eso.

Answer 8

Si tiene Q = N! en binario, cuente los ceros finales. Llame 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 el número de 1 que ha agregado es 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, Q supongamos que (en binario) es

1111001110111010100100110000101011001111100000110110000000000000000000 

(Siento que sea tan pequeño, pero no tengo herramientas útiles para manipular los números más grandes.)

Hay 19 ceros a la derecha , que es

10011 

Ahora subasta:

1: 10100 
2: 10101 
3: 10110 bingo! 

So 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) Así que 23^1 debe dividir 23 !, no divide Q, por lo

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

funciones gamma Comprobar inversas de aquí http://functions.wolfram.com/GammaBetaErf/InverseGammaRegularized/ Tienen múltiples aproximaciones

Answer 11

Aquí hay un código 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 = 0,5, retorno 'nil'

Answer 12

En C desde mi aplicación avanzada Trigonometría calculadora v1.6.8

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

¿Qué piensa usted de eso ? Funciona correctamente para enteros de factoriales.

Answer 13

¡Esta función se basa en aproximaciones sucesivas! La creé e implementado en Avanzada trigonometría Calculadora 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

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 ejemplo:

Call: wtf(1) 
Output: 1 

Call: wtf(120) 
Output: 5 

Call: wtf(3628800) 
Output: 10 

Answer 15

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

Así que el último número antes del resultado = 1 es su número.

En código que podría hacer lo siguiente:

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

} 

o algo por el estilo. Este cálculo necesita una mejora para los números no exactos.

Answer 16

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 extiende la función factorial a números reales positivos (y también a números más 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 se trata de 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 17

n! 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 para cada vez que prime p o cualquiera de sus potencias esté dentro de n. Cuantas veces verás p. Así que tiene que ser el más grande de k para el que

significa

la misma de los poderes principales

El algoritmo sigue.

Supongamos que tenemos 10888869450418352160768000000

podemos dividir 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 todavía es útil.)

Ahora podemos utilizar 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.Tratamos 26 y encontramos fácilmente que es

Si este no sería el caso tendríamos continuamos el segmento de 23 a 26 o 26 a 29, dependiendo del resultado.

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

Así que si el anterior es un factorial es el factorial de 27. Comprobación de la misma como anteriormente para 5,7,11,13,17,19 y 23 se muestra que todo está bien y de hecho es 27.