Menu Close

Número de dígitos del factorial

José A. Alonso,

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
Medio
, , , , , , , , , , , , , ,

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

  1. Responder
    belbenzam 
    factorial n = product [1..n] 
digitosFactorial :: Int -> Int 
digitosFactorial 0 = 1
digitosFactorial n = sum ( map digitToInt ( show (factorial n )))
  2. Responder
    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. Responder
    juacasnie 
     
nDigitosFact :: Integer -> Integer
nDigitosFact n  = genericLength (show m)
   where m = fact n 
 
fact :: Integer -> Integer
fact n = product [1..n]
  4. Responder
    monlagare 
     
digitos :: Integer -> [Integer]
digitos x = [read [d]| d <- show x]
 
nDigitosFact :: Integer -> Integer
nDigitosFact n = genericLength (digitos (product [1..n]))
  5. Responder
    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]

    • Responder
      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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.