Menu Close

Número de dígitos del factorial

Definir las funciones

   nDigitosFact :: Integer -> Integer
   graficas     :: [Integer] -> IO ()

tales que

  • (nDigitosFact n) es el número de dígitos de n!. Por ejemplo,
     nDigitosFact 0        ==  1
     nDigitosFact 4        ==  2
     nDigitosFact 5        ==  3
     nDigitosFact 10       ==  7
     nDigitosFact 100      ==  158
     nDigitosFact 1000     ==  2568
     nDigitosFact 10000    ==  35660
     nDigitosFact 100000   ==  456574
     nDigitosFact 1000000  ==  5565709
  • (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

   λ> import System.Random 
   λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
   λ> maximum (map nDigitosFact xs)
   5561492
   λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
   λ> maximum (map nDigitosFact xs)
   5563303

Soluciones

import Data.List (genericLength, genericIndex)
import Graphics.Gnuplot.Simple
 
-- 1ª definición
nDigitosFact1 :: Integer -> Integer
nDigitosFact1 n =
  genericLength (show (product [1..n]))
 
-- 2ª definición (usando logaritmos)
-- =================================
 
-- Basado en
--    nDigitos (n!) = 1 + floor (log (n!))
--                  = 1 + floor (log (1*2*3*...*n))
--                  = 1 + floor (log(1) + log(2) + log(3) +...+ log(n))
 
nDigitosFact2 :: Integer -> Integer
nDigitosFact2 n =
  1 + floor (sum [logBase 10 (fromIntegral k) | k <- [1..n]])
 
-- 3ª definición (usando logaritmos y programación dinámica)
-- =========================================================
 
nDigitosFact3 :: Integer -> Integer
nDigitosFact3 0 = 1
nDigitosFact3 n = 1 + floor ((sumLogs `genericIndex` (n-1)) / log 10)
 
logs :: [Double]
logs = map log [1..]
 
sumLogs :: [Double]
sumLogs = scanl1 (+) logs
 
-- 4ª definición (Usando la fórmula de Kamenetsky)
-- ===============================================
 
-- La fórmula se encuentra en https://oeis.org/A034886
 
nDigitosFact4 :: Integer -> Integer
nDigitosFact4 0 = 1
nDigitosFact4 1 = 1
nDigitosFact4 n =
  1 + floor (m * logBase 10 (m/e) + logBase 10 (2*pi*m)/2)
  where m = fromIntegral n
        e = exp 1
 
--    λ> nDigitosFact1 (4*10^4)
--    166714
--    (5.61 secs, 1,649,912,864 bytes)
--    λ> nDigitosFact2 (4*10^4)
--    166714
--    (0.10 secs, 13,741,360 bytes)
--
--    λ> nDigitosFact2 (7*10^5)
--    3787566
--    (1.86 secs, 187,666,328 bytes)
--    λ> nDigitosFact3 (7*10^5)
--    3787566
--    (0.02 secs, 0 bytes)
--    λ> nDigitosFact3 (7*10^5)
--    3787566
--    (1.01 secs, 238,682,064 bytes)
--    λ> nDigitosFact4 (7*10^5)
--    3787566
--    (0.01 secs, 0 bytes)
-- 
--    λ> import System.Random 
--    λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^2]]
--    λ> maximum (map nDigitosFact3 xs)
--    5565097
--    (11.19 secs, 7,336,595,440 bytes)
--    λ> maximum (map nDigitosFact4 xs)
--    5565097
--    (0.01 secs, 0 bytes)
 
graficas :: [Integer] -> IO ()
graficas xs = 
    plotLists [Key Nothing]
              [p1, p2]
    where p1, p2 :: [(Float, Float)]
          p1 = [(fi k, fi (nDigitosFact4 k)) | k <- xs]
          p2 = [(k',5.5*k') | k <- xs, let k' = fi k]
          fi = fromIntegral

10 soluciones de “Número de dígitos del factorial

  1. belbenzam
    factorial n = product [1..n] 
    digitosFactorial :: Int -> Int 
    digitosFactorial 0 = 1
    digitosFactorial n = sum ( map digitToInt ( show (factorial n )))
  2. javcancif
    factorial :: Integer -> Integer
    factorial 0 = 1
    factorial n = n * factorial (n-1)
     
    digitos :: Integer -> [Integer]
    digitos n = [read [x] | x <- show n]
     
    nDigitosFact :: Integer -> Int
    nDigitosFact n = length (digitos (factorial n))
     
    --He cambiado el tipo de salida de la función.
  3. juacasnie
     
    nDigitosFact :: Integer -> Integer
    nDigitosFact n  = genericLength (show m)
       where m = fact n 
     
    fact :: Integer -> Integer
    fact n = product [1..n]
  4. monlagare
     
    digitos :: Integer -> [Integer]
    digitos x = [read [d]| d <- show x]
     
    nDigitosFact :: Integer -> Integer
    nDigitosFact n = genericLength (digitos (product [1..n]))
  5. albcercid

    — 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]

    • albcercid
      -- 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 (2*pi*x)) + x*logBase 10 (x/2.71828)) + 1
       
      -- Fórmula obtenida observando el crecimiento de (x!)^(1/x).
      -- A partir del factorial de 200 resultaba Infinity, así que no he podido conseguir una mejor aproximación.
      nDigitosFact3 x =
        fromIntegral $ floor (x*logBase 10 (0.36890722289627575*x + 0.6310927771037242)) + 1
       
      graficas2     :: [Double] -> IO ()
      graficas2 xs = plotPaths [Key Nothing] [f1,f2]
        where recta x = x*5.5
              f1 = [(x,fromIntegral (nDigitosFact2 x)) | x <- xs]
              f2 = [(x,5.5*x) | x <- xs]
  6. enrnarbej
    -- Trivial:
     
    nDigitosFactTrivial :: Integer -> Integer
    nDigitosFactTrivial n = (genericLength . show . product) [1..n]
     
    -- Primera función:
     
    nDigitosFact :: Integer -> Integer
    nDigitosFact 0 = 1
    nDigitosFact 1 = 1
    nDigitosFact n = (ceiling . sum) (logBase 10.fromInteger <$> [1..n])
     
    -- Vemos que perdemos tiempo al repetir el cálculo de logaritmos. Definimos una función, de orden linea,O(2n), que nos devuelve un vector(lo cual nos permitirá ahorrarnos tiempo de acceso) con el número de dígitos de los primeros n factoriales.
     
    logBase10 :: [Double]
    logBase10 = logBase 10.fromInteger <$> [1..]
     
    digitosFact :: Int -> V.Vector Integer
    digitosFact n = V.fromList $ take n (((1:) . tail . aux logBase10) 0)
                where
                 aux (x:xs) s = (ceiling (s + x)) : aux xs (s+x)
     
     
    -- Este función, aunque rápida, no cumple los tiempos pedidos
    -- *Ex_23>  V.sum $ digitosFact (10^6)
    -- 2674285603295
    -- (2.85 secs, 1,109,908,312 bytes)
     
    -- Utilizamos la fórmula de Kamenetsky 
     
    nDigitosFactKamenetsky :: Integer -> Integer
    nDigitosFactKamenetsky 0 = 1
    nDigitosFactKamenetsky 1 = 1
    nDigitosFactKamenetsky n = floor ((logBase 10 . sqrt . (2*) . (pi*)) x + ((x*) . logBase 10 . (x/) . exp) 1) + 1
                             where x = fromInteger n
     
    graficas     :: [Integer] -> IO ()
    graficas xs = plotLists [Key Nothing] [nDigitosFactKamenetsky <$> xs]
  7. margarflo5

    fact :: [Integer]

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

    factorial :: Int -> Integer
    factorial n = fact !! n
     
    nDigitosFact n = length (digitos (factorial n))
     
    digitos :: Integer -> [Integer]
    digitos n = [ read [x] | x <- show n ]
  8. margarflo5
    fact :: [Integer]
    fact = 1:scanl1 (*) [1..]
     
    factorial :: Int -> Integer
    factorial n = fact !! n
     
    nDigitosFact n = length (digitos (factorial n))
     
    digitos :: Integer -> [Integer]
    digitos n = [ read [x] | x <- show n ]
  9. cescarde
    nDigitosFact :: Integer -> Int
    nDigitosFact = floor.funxxion
     
    funxxion :: Integer -> Float
    funxxion n | n == 0 = 1
               | n == 1 = 1
               | n == 2 = 1
               | n == 3 = 1
               | otherwise = a + b + (funxxion (n-4))
               where l = logBase 10
                     f = fromIntegral
                     a = l (f n) + l (f $ n-1) 
                     b = l (f $ n-2) + l (f $ n-3)
     
    graficas :: [Integer] -> IO ()
    graficas xs = plotLists [Key Nothing] [[(n,nDigitosFact n) | n <- xs]
                                           [(x,5.5*x) | x <- xs]]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.