Calcular el inverso de factorial

30

Escriba el código más corto que tomará cualquier número real mayor que 1 como entrada y generará su factorial inverso positivo. En otras palabras, responde a la pregunta "¿qué número factorial es igual a este número?". Use la función Gamma para extender la definición de factorial a cualquier número real como se describe aquí .

Por ejemplo:

input=6 output=3 
input=10 output=3.390077654

porque 3! = 6y3.390077654! = 10

Reglas

  • Está prohibido utilizar funciones factoriales integradas o funciones gamma, o funciones que dependen de estas funciones.
  • El programa debe poder calcularlo con 5 dígitos decimales, con la capacidad teórica de calcularlo con cualquier precisión (debe contener un número que pueda hacerse arbitrario grande o pequeño para obtener una precisión arbitraria)
  • Se permite cualquier idioma, gana el código más corto en caracteres.

Hice un ejemplo de trabajo aquí . Echar un vistazo.

Jens Renders
fuente
2
Esto podría usar algunos casos de prueba más, en particular para cubrir entradas cero y negativas.
Peter Taylor
Edité que la entrada debería ser mayor que 1 porque de lo contrario podría haber múltiples respuestas.
Jens Renders
1
De todos modos, puede haber múltiples respuestas a menos que también agregue un requisito de que la salida debe ser mayor que 1.
Peter Taylor
Su ejemplo de trabajo da 3.99999 cuando se ingresa 24. Entonces, ¿es aceptable tal solución?
rubik
sí, porque esto puede verse como 4, a 5 decimales correcto
Jens Renders

Respuestas:

13

Javascript (116)

¡Magia negra aquí! Da un resultado en pocos milisegundos .
Sólo funciones matemáticas elementales utilizados: ln, pow,exponential

x=9;n=prompt(M=Math);for(i=1e4;i--;)x+=(n/M.exp(-x)/M.pow(x,x-.5)/2.5066/(1+1/12/x+1/288/x/x)-1)/M.log(x);alert(x-1)

Lástima que LaTeX no sea compatible con codegolf, pero básicamente codifiqué un solucionador newton para f(y)=gamma(y)-n=0y x=y-1(porque lo x!es gamma(x+1)) y aproximaciones para funciones gamma y digamma.

La aproximación gamma es la aproximación de Stirling La aproximación
digamma usa la fórmula de Euler Maclaurin
La función digamma es la derivada de la función gamma dividida por la función gamma:f'(y)=gamma(y)*digamma(y)

Sin golf:

n = parseInt(prompt());
x = 9; //first guess, whatever but not too high (<500 seems good)

//10000 iterations
for(i=0;i<10000;i++) {

  //approximation for digamma
  d=Math.log(x);

  //approximation for gamma
  g=Math.exp(-x)*Math.pow(x,x-0.5)*Math.sqrt(Math.PI*2)*(1+1/12/x+1/288/x/x);

  //uncomment if more precision is needed
  //d=Math.log(x)-1/2/x-1/12/x/x+120/x/x/x/x;
  //g=Math.exp(-x)*Math.pow(x,x-0.5)*Math.sqrt(Math.PI*2)*(1+1/12/x+1/288/x/x-139/51840/x/x/x);

  //classic newton, gamma derivative is gamma*digamma
  x-=(g-n)/(g*d);
}

alert(x-1);

Casos de prueba :

10 => 3.390062988090518
120 => 4.99999939151027
720 => 6.00000187248195
40320 => 8.000003557030217
3628800 => 10.000003941731514
Michael M.
fuente
Muy buena respuesta, aunque no cumple con la precisión requerida y solo funciona para números menores que 706
Jens Renders
@JensRenders, bueno, agregué algunas iteraciones del solucionador newton, cambié la suposición inicial y una mejor aproximación para la función gamma. Eso debería ajustarse a las reglas ahora. Dejadme que ahora si está bien :)
Michael M.
Sí, ahora es perfecto, lo voté :)
Jens Renders
1
Podría guardar 1 char:n=prompt(M=Math)
Florent
Intente ejecutar su código en un número grande como $ 10 ^ {10 ^ 6} $, y asegúrese de obtener un resultado entero
David G. Stork
13

Mathematica - 74 54 49

La forma correcta será

f[x_?NumberQ]:=NIntegrate[t^x E^-t,{t,0,∞}]
x/.FindRoot[f@x-Input[],{x,1}]

Si simplemente dejamos la prueba ?NumberQ, todavía funcionaría, pero arrojaría algunas advertencias desagradables, que desaparecerían si cambiamos a la integración simbólica Integrate, pero esto sería ilegal (supongo), porque la función se convertiría automáticamente en Gammafunción. También podemos deshacernos de la función externa de esa manera.

De todas formas

x/.FindRoot[Integrate[t^x E^-t,{t,0,∞}]-Input[],{x,1}]

Para hacer una entrada correcta, solo defina la función (no puede dejar que MatLab gane)

x/.FindRoot[Integrate[t^x E^-t,{t,0,∞}]-#,{x,1}]&

Si se permitiera el factorial incorporado

N@InverseFunction[#!&]@Input[]

Lo anterior no da un número entero (que es el argumento para una verdadera función factorial). Lo siguiente hace:

Floor[InverseFunction[Gamma][n]-1]
silbido
fuente
Ahh todas esas funciones incorporadas! No creo que esto sea vencible, excepto de manera similar.
rubik
44
¡Mathematica es tan injusto para las matemáticas! : D
Michael M.
1
del nombre mismo MATHematica
Dadan
¿Se NumberQrequiere prueba de patrón? O parens en E^(-t)? ¿Está engañando a su vez NIntegratea Integrate? Probablemente ... :)
orion
Se está convirtiendo en un verdadero desafío;)
mmumboss
6

ised: 72 46 caracteres

Esto es casi un ajuste perfecto ... hay un "lenguaje" que parece estar destinado precisamente al golf matemático: ised . Su sintaxis ofuscada lo convierte en un código muy corto (sin variables con nombre, solo ranuras de memoria de enteros y muchos operadores versátiles de caracteres únicos). Al definir la función gamma usando una integral, obtuve 80 caracteres aparentemente aleatorios

@4{:.1*@+{@3[.,.1,99]^x:*exp-$3}:}@6{:@{$4::@5avg${0,1}>$2}$5:}@0,0@1,99;$6:::.

Aquí, la ranura de memoria $ 4 es una función factorial, se espera que la ranura de memoria $ 6 de función de bisección y la ranura de memoria $ 2 se configuren como entrada (antes de obtener este código). Las ranuras $ 0 y $ 1 son los límites de bisección. Ejemplo de llamada (suponiendo que el código anterior esté en el archivo inversefactorial.ised)

bash> ised '@2{556}' --f inversefactorial.ised
556
5.86118

¡Por supuesto, podrías usar el incorporado! operador, en cuyo caso obtienes 45 caracteres

@6{:@{{@5avg${0,1}}!>$2}$5:}@0,0@1,99;$6:::.

Cuidado, la precedencia del operador es extraña a veces.

Editar: recordado en línea las funciones en lugar de guardarlas. ¡Derrota a Mathematica con 72 personajes!

@0,0@1,99;{:@{{:.1*@+{@3[.,.1,99]^x:*exp-$3}:}::@5avg${0,1}>$2}$5:}:::.

Y usando el! Construido obtienes 41.


Un año de actualización atrasada:

Me acabo de dar cuenta de que esto era muy ineficiente. Golfed-down a 60 caracteres:

@0#@1,99;{:@{.1*@3[.,.1,99]^@5avg${0,1}@:exp-$3>$2}$5:}:::.

Si se usa utf-8 (Mathematica también lo hace), llegamos a 57:

@0#@1,99;{:@{.1*@3[.,.1,99]^@5avg${0,1}·exp-$3>$2}$5:}∙.

Una reescritura un poco diferente puede reducirlo a 46 (o 27 si se usa incorporado):

{:x_S{.5@3[.,.1,99]^avgx·exp-$3*.1<$2}:}∙∓99_0

Los dos últimos caracteres se pueden eliminar si está de acuerdo con que la respuesta se imprima dos veces.

Orión
fuente
Me sorprendería ver a alguien superar esto: o
Jens Renders
@JensRenders: acabo de hacerlo;)
mmumboss
Para aclarar la discusión sobre la precisión: se establece en .1 (paso de integración) y 99 (límite de integración). La bisección va a la precisión de la máquina. El límite de bisección @ 1,99 se puede mantener en 99 a menos que desee ingresar números arriba (¡99!).
orion
@mmumboss te consiguió de nuevo :)
orion
5

MATLAB 54 47

Si elijo los desafíos correctos, MATLAB es realmente bueno para jugar al golf :). En mi código encuentro la solución a la ecuación (ux!) = 0 en la que u es la entrada del usuario, y x la variable a resolver. Esto significa que u = 6 conducirá a x = 3, etc.

@(x)fsolve(@(y)u-quad(@(x)x.^y./exp(x),0,99),1)

La precisión se puede cambiar alterando el límite superior de la integral, que se establece en 99. Al bajar esto, se cambiará la precisión de la salida de la siguiente manera. Por ejemplo para una entrada de 10:

upper limit = 99; answer = 3.390077650833145;
upper limit = 20; answer = 3.390082293675363;
upper limit = 10; answer = 3.402035336604546;
upper limit = 05; answer = 3.747303578099607;

etc.

mmumboss
fuente
¡debe especificar la opción de precisión ya que esto es obligatorio en las reglas! "Debe contener un número que se pueda hacer arbitrario grande o pequeño para obtener una precisión arbitraria"
Jens Renders
Tampoco lo veo en las soluciones ised y Mathematica? Pero lo investigaré ..
mmumboss
1
Veo el número 99 en la versión ised, y la versión matemática es superada de todos modos
Jens Renders
Dada la posición en el código, este es probablemente el límite superior para la integral. En mi código esto es inf. Entonces, si cambio este inf a 99, mi respuesta se vuelve menos precisa, lo que significa que este número influye en la precisión y, por lo tanto, cumplo con las reglas. Si lo cambio a 99, incluso
guardo
Pero después de cambiar inf a 99, ¿cumple con la precisión requerida?
rubik
3

Python - 199 caracteres

Ok, entonces necesitarás mucho espacio de apilamiento y mucho tiempo, pero bueno, ¡llegará allí!

from random import *
from math import e
def f(x,n):
    q=randint(0,x)+random()
    z=0
    d=0.1**n
    y=d
    while y<100:
            z+=y**q*e**(-y)*d
            y+=d
    return q if round(z,n)==x else f(x,n)

Aquí hay otro enfoque con aún más recursividad.

from random import *
from math import e
def f(x,n):
    q=randint(0,x)+random()
    return q if round(h(q,0,0.1**n,0),n)==x else f(x,n)
def h(q,z,d,y):
    if y>100:return z
    else:return h(q,z+y**q*e**(-y)*d,d,y+d)

Ambos pueden probarse >>>f(10,1)siempre que establezca el límite de recursión alrededor de 10000. Es probable que más de un decimal de precisión no se complete con ningún límite de recursión realista.

Incorporando los comentarios y algunas modificaciones, hasta 199 caracteres.

from random import*
from math import*
def f(x,n):
    q=random()*x+random()
    z=y=0
    while y<100:
            z+=y**q*e**-y*0.1**n
            y+=0.1**n
    return q if round(z,n)==x else f(x,n)
intx13
fuente
2
Esta es una code-golfpregunta, por lo que debe proporcionar la respuesta más breve, indicando la duración de su solución.
VisioN
Un buen método, pero el problema es que no puede garantizar que alguna vez encontrará la respuesta ... Además, este es codegolf zo, puede intentar minimizar el uso de caracteres.
Jens Renders
1
Python's random () usa un Mersenne Twister que creo que recorre el espacio de las carrozas de Python, por lo que siempre debe terminar si hay una respuesta dentro de la tolerancia.
intx13
¿Quiere decir que devuelve cada valor flotante antes de repetir uno? si ese es el caso, este código sería válido si pudieras superar el desbordamiento de la pila
Jens Renders
2
El código es capaz, es solo que usted y yo no tenemos el tiempo ni los recursos de la computadora para ejecutarlo;)
intx13
3

Python 2.7 - 215 189 caracteres

f=lambda t:sum((x*.1)**t*2.71828**-(x*.1)*.1for x in range(999))
n=float(raw_input());x=1.;F=0;C=99
while 1:
 if abs(n-f(x))<1e-5:print x;break
 F,C,x=f(x)<n and(x,C,(x+C)/2)or(F,x,(x+F)/2)

Uso:

# echo 6 | python invfact_golf.py
2.99999904633
# echo 10 | python invfact_golf.py
3.39007514715
# echo 3628800 | python invfact_golf.py
9.99999685376

Para cambiar la precisión: cambie 1e-5a un número más pequeño para mayor precisión, un número más grande para peor precisión. Para una mejor precisión, probablemente desee dar un mejor valor e.

Esto simplemente implementa la función factorial como f, y luego realiza una búsqueda binaria para afinar el valor más preciso de la inversa de la entrada. Asume que la respuesta es menor o igual a 99 (seguro que no funcionaría para una respuesta de 365, obtengo un error de desbordamiento matemático). Uso de espacio y tiempo muy razonable, siempre termina.

Alternativamente, reemplace if abs(n-f(x))<=10**-5: print x;breakcon print xpara afeitar 50 caracteres . Se repetirá para siempre, brindándote una estimación cada vez más precisa. Sin embargo, no estoy seguro de si esto encajaría con las reglas.

Claudiu
fuente
No conocía ese sitio para contar caracteres. Yo siempre uso cat file | wc -c.
rubik
@rubik: oh bien, no pensé en usar eso. ambos coinciden =)
Claudiu
2

dg - 131 133 bytes

o,d,n=0,0.1,float$input!
for w in(-2..9)=>while(sum$map(i->d*(i*d)**(o+ 10**(-w))/(2.718281**(i*d)))(0..999))<n=>o+=10**(-w)
print o

Como dg produce el bytecode de CPython, esto también debería contar para Python, pero oh ... Algunos ejemplos:

$ dg gam.dg 
10
3.3900766499999984
$ dg gam.dg 
24
3.9999989799999995
$ dg gam.dg 
100
4.892517629999997
$ dg gam.dg 
12637326743
13.27087070999999
$ dg gam.dg  # i'm not really sure about this one :P it's instantaneous though
28492739842739428347929842398472934929234239432948923
42.800660880000066
$ dg gam.dg  # a float example
284253.232359
8.891269689999989

EDITAR: ¡Agregué dos bytes porque no recordaba que también debería aceptar flotantes!

rubik
fuente
¡El mío da 42.8006566063, por lo que coinciden con 5 dígitos de precisión!
Claudiu
¡Eso es genial! No sé dónde está el límite superior, pero debería romperse en alguna parte. Porque 1e100da:, 69.95780520000001para 1e150que salga 96.10586423000002, mientras que para 1e200explota. Pero realmente no sé si esos resultados son confiables ...
rubik
1

R , 92 bytes

Una función, gque toma entradas zy salidas el factorial inverso de ese número

Es casi seguro que se puede sacar más partido de esto, así que si ve algo que pueda mejorar, avíseme.

library(pryr)
g=f(z,uniroot(f(a,integrate(f(x,x^a*exp(-x)),0,Inf)$v-z),c(0,z+1),tol=1e-9)$r)

Pruébalo en línea!

No golfista y comentado

library(pryr)                     # Add pryr to workspace
inv.factorial = f(z,              # Declare function which  
  uniroot(                        # Finds the root of
    f(a, integrate(               # The integral of 
      f(x, x^a*exp(-x))           # The gamma function
        ,0 ,Inf                   # From 0 to Infinity
      )$value-z                   # Minus the input value, `z`
    ), c(0, z+1),                 # On the bound of 0 to z+1
    tol = 1e-323                  # With a specified tolerance
  )$root                          # And outputs the root
)                                 # End function

Pruébalo en línea!

Taylor Scott
fuente
0

Javascript (¡sin usar bucles!)

Para hacer esto, utilicé una aproximación numérica bien conocida de la inversa de la aproximación factorial de Stirling (y también me inspiré en este ... código de tos ... tos de otra persona ...)

function f(n){
    if(n==1) return 1;
    else if(n==2) return 2;
    else if(n==6) return 3;
    else if(n==24) return 4;
    else{
        return Math.round((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))/Math.log((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))))/Math.log((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))/Math.log((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))))))
    }
}
Antonio Ragagnin
fuente