¿Cuál sería la forma más eficiente de verificar si un número dado es un factorial de algún número o no?

No estoy realmente seguro de si hay una forma más rápida que calcular el factorial si el número es un factorial de un número. Pero puede hacer una verificación de cordura básica antes de verificar realmente la forma directa de calcular factores sucesivos hasta que toque o cruce el número dado.

Considere un número que pueda encontrar fácilmente el número de ceros al final. Mira ¿Cómo encontramos el número de ceros al final de un factorial? para una forma exacta de encontrar esto.

Para un conjunto dado de números (5k, 5k + 1, 5k + 2, 5k + 3, 5k + 4) el número de ceros finales en sus factoriales es el mismo y cualquier número fuera de este conjunto no puede tener el mismo número de ceros finales en su factorial Cree un mapa inverso de la secuencia A027868 – OEIS para todos los múltiplos de 5. Algo parecido a
0-0
15
2-10
3-15
4-20
6-25
7-30

A partir del número dado, encuentre el número de ceros finales y busque este número en el mapa que creó, si no existe en el mapa, puede decir inmediatamente que el número dado no es factorial de ningún número. Si obtenemos algún número 5k, todo lo que podemos decir es que podría ser el factorial de uno de los números (5k, 5k + 1, 5k + 2, 5k + 3, 5k + 4).

Para cada uno de los cinco números, encuentre el número de dígitos que estaría presente en su representación factorial. Consulte A034886 – OEIS, para un número dado n el valor es [math] \ left \ lfloor log_ {10} (n!) \ Right \ rfloor + 1 [/ math] simplemente puede calcular esto usando un bucle simple haciendo uso de la identidad [math] log_ {b} (xy) = log_ {b} (x) + log_ {b} (y) [/ math]. Si el número de dígitos en el número dado no es igual a ninguno de los cinco valores, puede decir que el número dado no es factorial de ningún número. Dado que los logaritmos usan cálculos de punto flotante, existe la posibilidad de algún error, por lo que tal vez necesitemos un poco de protección para los valores calculados, pero no estoy realmente seguro de cuánto error podría causarse debido a los cálculos de punto flotante.

Si no hemos descartado la posibilidad de que el número sea un factorial de algún número, solo encuentre los factores de los números 5k, 5k + 1, 5k + 2, 5k + 3, 5k + 4 y compárelo con el número dado (si el número dado es estrictamente mayor para algún número, podemos dejar de comparar para los números más grandes).

Contra ejemplos bien construidos, la verificación de la cordura siempre pasaría haciéndonos calcular los factores factoriales siempre, pero para los números elegidos al azar, la verificación de la cordura está destinada a fallar la mayoría de las veces.

El propósito de esta comprobación de cordura es evitar muchos cálculos de enteros grandes siempre que la función factorial crezca bastante rápido. Sí, a medida que los números se hacen más y más grandes, más tiempo tomará para el cálculo de factorial. No estoy convencido, intente ejecutar este código python thon

from math import floor,log10 from time import time targetNumber = 99999 t1 = time() n = 1 for i in range(1,targetNumber+1): n = n*i t2 = time() print "Time taken for computing factorial " + str(t2-t1) s = str(n) print len(s) t1 = time() tZeroes = 0 i = len(s) - 1 while s[i] == '0': tZeroes += 1 i -= 1 print "trailing zeroes in s " + str(tZeroes) targetZeroes = 0 k = 0 while targetZeroes < tZeroes: k += 5 temp = k while temp%5 == 0: targetZeroes += 1 temp /= 5 if targetZeroes == tZeroes: print "Could be factorial of a number in range " + str(k) + " to " + str(k+4) else: print "Not a factorial of any number" x = 0 for i in range(1,targetNumber+1): x = x+log10(i) print floor(x) + 1 t2 = time() print "Time taken for sanity checks " + str(t2-t1) 

¿Aún no estás convencido? Intenta aumentar el valor de targetNumber.

El siguiente código es solo para lenguaje Python

n = int (input (“ingrese un número:”))

i = 1

pro = 1

bandera = 0

mientras que pro

pro = pro * i

si pro == n:

bandera = 1

i = i + 1

si bandera == 1:

print (“el número es un factorial”)

más:

print (“el número no es un factorial”)

Un método más rápido sería seguir multiplicando desde 1,2,3, … hasta algunos k tal que producto = 1 * 2 * 3 … * k> = n. Si producto = n, entonces la respuesta es sí, de lo contrario no. Esto solo requiere k << n operaciones.

Si un número dado n es un factorial de algún número, el (n-1)! = 0 mod n