Número de dígitos del factorial

Definir las funciones

tales que

  • (nDigitosFact n) es el número de dígitos de n!. Por ejemplo,

  • (graficas xs) dibuja las gráficas de los números de dígitos del factorial de k (para k en xs) y de la recta y = 5.5 x. Por ejemplo, (graficas [0,500..10^6]) dibuja
    Numero_de_digitos_del_factorial

Nota: Este ejercicio está basado en el problema How many digits? de Kattis en donde se impone la restricción de calcular, en menos de 1 segundo, el número de dígitos de los factoriales de 10.000 números del rango [0,1.000.000].

Se puede simular como sigue

Soluciones

10 Comentarios

  1. — Definición directa
    nDigitosFact :: Integer -> Integer
    nDigitosFact = genericLength.show.product.list
    where list x = [1..x]

    — Fórmula de Kamenetsky
    nDigitosFact2 0 = 1
    nDigitosFact2 x =
    fromIntegral $ floor (logBase 10 (sqrt (2pix)) + x*logBase 10 (x/2.71828)) + 1

    — Fórmula obtenida observando el crecimiento de (factorial (x))^(1/x).
    — Debido a que a partir del factorial de 200 solo obtenía Infinity, no he podido obtener una mejor aproximación.

    nDigitosFact3 x =
    fromIntegral $ floor (xlogBase 10 (0.36890722289627575x + 0.6310927771037242)) + 1

    graficas2 :: [Double] -> IO ()
    graficas2 xs = plotPaths [Key Nothing] [f1,f2]
    where recta x = x5.5
    f1 = [(x,fromIntegral (nDigitosFact2 x)) | x <- xs]
    f2 = [(x,5.5
    x) | x <- xs]

  2. fact :: [Integer]

    fact = 1:scanl1 (*) [1..]

Leave a Reply to javcancifCancel reply