Menu Close

Último dígito no nulo del factorial

El factorial de 7 es

   7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040

por tanto, el último dígito no nulo del factorial de 7 es 4.

Definir la función

   ultimoNoNuloFactorial :: Integer -> Integer

tal que (ultimoNoNuloFactorial n) es el último dígito no nulo del factorial de n. Por ejemplo,

   ultimoNoNuloFactorial  7  == 4
   ultimoNoNuloFactorial 10  == 8
   ultimoNoNuloFactorial 12  == 6
   ultimoNoNuloFactorial 97  == 2
   ultimoNoNuloFactorial  0  == 1

Comprobar con QuickCheck que si n es mayor que 4, entonces el último dígito no nulo del factorial de n es par.

Soluciones

import Test.QuickCheck
 
-- 1ª definición
-- =============
 
ultimoNoNuloFactorial :: Integer -> Integer
ultimoNoNuloFactorial n = ultimoNoNulo (factorial n)
 
-- (ultimoNoNulo n) es el último dígito no nulo de n. Por ejemplo,
--    ultimoNoNulo 5040  ==  4
ultimoNoNulo :: Integer -> Integer
ultimoNoNulo n
  | m /= 0    = m
  | otherwise = ultimoNoNulo (n `div` 10)
  where m = n `rem` 10
 
-- (factorial n) es el factorial de n. Por ejemplo,
--    factorial 7  ==  5040
factorial :: Integer -> Integer
factorial n = product [1..n]
 
-- 2ª definición
-- =============
 
ultimoNoNuloFactorial2 :: Integer -> Integer
ultimoNoNuloFactorial2 n = ultimoNoNulo2 (factorial n)
 
-- (ultimoNoNulo2 n) es el último dígito no nulo de n. Por ejemplo,
--    ultimoNoNulo 5040  ==  4
ultimoNoNulo2 :: Integer -> Integer
ultimoNoNulo2 n = read [head (dropWhile (=='0') (reverse (show n)))]
 
-- Comprobación
-- ============
 
-- La propiedad es
prop_ultimoNoNuloFactorial :: Integer -> Property
prop_ultimoNoNuloFactorial n = 
  n > 4 ==> even (ultimoNoNuloFactorial n)
 
-- La comprobación es
--    ghci> quickCheck prop_ultimoNoNuloFactorial
--    +++ OK, passed 100 tests.

Pensamiento

Incierto es, lo porvenir. ¿Quién sabe lo que va a pasar? Pero incierto es también lo pretérito. ¿Quién sabe lo que ha pasado? De suerte que ni el porvenir está escrito en ninguna parte, ni el pasado tampoco.

Antonio Machado

Ejercicio

7 soluciones de “Último dígito no nulo del factorial

  1. frahidzam
    -- Definición de la función
     
    factorial :: Integer -> Integer
    factorial n = product [1..n]
     
    ultimoNoNuloFactorial :: Integer -> Integer
    ultimoNoNuloFactorial n =
      read [head (dropWhile (=='0') (reverse (show (factorial n))))]
     
    -- Comprobación de la propiedad con QuickCheck
    prop_ultimoNoNuloFactorial :: Integer -> Property
    prop_ultimoNoNuloFactorial n = n > 4 ==> even (ultimoNoNuloFactorial n)
     
    -- λ> quickCheck prop_ultimoNoNuloFactorial
    -- +++ OK, passed 100 tests.
  2. lucsanand
    ultimoNoNuloFactorial :: Integer -> Integer
    ultimoNoNuloFactorial n = last [x | x <- digitos (factorial n), x /= 0]
     
    factorial :: Integer -> Integer
    factorial 0 = 1
    factorial n = n * factorial (n-1)
     
    digitos :: Integer -> [Integer]
    digitos n  | n < 10    = [n]
               | otherwise = digitos (div n 10) ++ [mod n 10]
     
    -- La propiedad es:
    prop_ultFact :: Integer -> Property
    prop_ultFact n = n > 4 ==> even (ultimoNoNuloFactorial n)
     
    -- Que es correcta:
    --    λ> quickCheck  prop_ultFact
    --    +++ OK, passed 100 tests.
  3. sermurgar
    ultimoNoNuloFactorial :: Integer -> Integer
    ultimoNoNuloFactorial x =
      ultimaCifraNoNula (factorial x)
     
    ultimaCifraNoNula :: Integer -> Integer
    ultimaCifraNoNula n
      | n < 10        = n
      | n == 10       = 1
      | mod n 10 /= 0 = mod n 10
      | otherwise     = ultimaCifraNoNula (div n 10)
     
    factorial :: Integer -> Integer
    factorial m =
      product [c | c <- [m, m-1 .. 1]]
     
    prop_ultimoNoNuloFactorial :: Integer -> Property
    prop_ultimoNoNuloFactorial n =
      n > 4 ==> even (ultimoNoNuloFactorial n)
  4. Luis Proenza Morgado
    ultimoNoNuloFactorial :: Integer -> Integer
    ultimoNoNuloFactorial y =
      mod (div f (10^(maximum [n | n <- [0..length (show f)], mod f (10^n) == 0]))) 10
      where f = product [1..y]
     
    prop_ultimoNoNuloFactorial :: Integer -> Property
    prop_ultimoNoNuloFactorial y =
      y > 4 ==>  even (ultimoNoNuloFactorial y)
  5. angruicam1

    Una primera solución bastante literal

    ultimoNoNuloFactorial' :: Integer -> Integer
    ultimoNoNuloFactorial' n | n < 2     = 1
                             | otherwise = if even b then b else b + 5
      where c0 = sum (tail m1)
            m1 = map (n `div`) (takeWhile (<= n) [5^k | k <- [0..]])
            m2 = aux m1
              where aux (x:y:xs) = (x-y) : aux (y:xs)
                    aux xs       = xs
            r  = map (`mod` 8) m2
            p  = map aux r
              where aux x | x < 5     = product [1..x] `mod` 5
                          | otherwise = 4 * product [1..x-4] `mod` 5
            px = product p `mod` 5
            a  = 2^c0 `mod` 5
            b  = aux px a
              where aux x y | y == 2 || y == 3 = x * (5-y) `mod` 5
                            | otherwise        = x * y `mod` 5

    Una solución basada en las congruencias e inspirada por el artículo Problema. Hallar el último dígito no nulo de 10000!:

    import Test.QuickCheck
     
    -- Equivalencia
    -- ============
     
    -- La propiedad es
    prop_equivalencia :: NonNegative Integer -> Bool
    prop_equivalencia (NonNegative n) =
      ultimoNoNuloFactorial n == ultimoNoNuloFactorial' n
     
    -- La comprobación es
    --    λ> quickCheck prop_equivalencia
    --    +++ OK, passed 100 tests.
     
    -- Eficiencia
    -- ==========
     
    -- λ> ultimoNoNuloFactorial 200000
    -- 4
    -- (17.35 secs, 48,921,109,616 bytes)
    -- λ> ultimoNoNuloFactorial' 200000
    -- 4
    -- (0.01 secs, 124,816 bytes)
     
    -- Propiedad
    -- =========
     
    -- La propiedad es
    prop_ultimoNoNuloFactorial :: Integer -> Property
    prop_ultimoNoNuloFactorial n =
      n > 4 ==> even (ultimoNoNuloFactorial n)
     
    -- La comprobación es
    --    λ> quickCheck prop_ultimoNoNuloFactorial
    --    +++ OK, passed 100 tests.

    Comprobamos la equivalencia de ambas definiciones, comparamos su eficiencia y definimos la propiedad:

    import Test.QuickCheck
     
    -- Equivalencia
    -- ============
     
    -- La propiedad es
    prop_equivalencia :: NonNegative Integer -> Bool
    prop_equivalencia (NonNegative n) =
      ultimoNoNuloFactorial n == ultimoNoNuloFactorial' n
     
    -- La comprobación es
    --    λ> quickCheck prop_equivalencia
    --    +++ OK, passed 100 tests.
     
    -- Eficiencia
    -- ==========
     
    -- λ> ultimoNoNuloFactorial 200000
    -- 4
    -- (17.35 secs, 48,921,109,616 bytes)
    -- λ> ultimoNoNuloFactorial' 200000
    -- 4
    -- (0.01 secs, 124,816 bytes)
     
    -- Propiedad
    -- =========
     
    -- La propiedad es
    prop_ultimoNoNuloFactorial :: Integer -> Property
    prop_ultimoNoNuloFactorial n =
      n > 4 ==> even (ultimoNoNuloFactorial n)
     
    -- La comprobación es
    --    λ> quickCheck prop_ultimoNoNuloFactorial
    --    +++ OK, passed 100 tests.
  6. berarcmat
    ultimoNoNuloFactorial :: Integer -> Integer
    ultimoNoNuloFactorial 0 = 1
    ultimoNoNuloFactorial n = head [ ultimaNoNula (rem f (10^x))
                                   | x <- [0..]
                                   , div f (10^x)     /= 0
                                   , div f (10^(x+1)) == 0]
      where f = product [1..n]
     
    ultimaNoNula :: Integer -> Integer
    ultimaNoNula x | p /= 0      = p
                   | otherwise   = ultimaNoNula (div x 10)
      where p = mod x 10
     
    prop_ultimoNoNuloFactorial :: Integer -> Property
    prop_ultimoNoNuloFactorial n =
      n > 4 ==> even (ultimoNoNuloFactorial n)
     
    -- λ> quickCheck prop_ultimoNoNuloFactorial
    -- +++ OK, passed 100 tests.
  7. javmarcha1
    ultimoNoNuloFactorial :: Integer -> Integer
    ultimoNoNuloFactorial n =
      read [last (show (div (factorial n) (10^numeroCerosFactorial n)))]
     
    factorial :: Integer -> Integer
    factorial n = product [1..n]
     
    numeroCerosFactorial :: Integer -> Integer
    numeroCerosFactorial n = numeroCeros (product [1..n])
     
    numeroCeros :: Integer -> Integer
    numeroCeros x | mod x 10 /= 0 = 0
                  | otherwise     = 1 + numeroCeros (div x 10)
     
    prop_ultimo :: Integer -> Property 
    prop_ultimo n = n > 4 ==> even (ultimoNoNuloFactorial n)
     
    -- λ> quickCheck prop_ultimo
    -- +++ OK, passed 100 tests.

Escribe tu solución

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