Ceros finales del factorial
Publicado el 29 de enero de 2024 por José A. Alonso

cerosDelFactorial :: Integer -> Integer

module Ceros_finales_del_factorial where

import Data.List (genericLength)
import Test.QuickCheck (Positive (Positive), quickCheck)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

-- 1ª solución
-- ===========

cerosDelFactorial1 :: Integer -> Integer
cerosDelFactorial1 n = ceros (factorial n)

-- (factorial n) es el factorial n. Por ejemplo,
--    factorial 3  ==  6
factorial :: Integer -> Integer
factorial n = product [1..n]

-- (ceros n) es el número de ceros en los que termina el número n. Por
-- ejemplo,
--    ceros 320000  ==  4
ceros :: Integer -> Integer
ceros n | rem n 10 /= 0 = 0
        | otherwise     = 1 + ceros (div n 10)

-- 2ª solución
-- ===========

cerosDelFactorial2 :: Integer -> Integer
cerosDelFactorial2 = ceros2 . factorial

ceros2 :: Integer -> Integer
ceros2 n = genericLength (takeWhile (=='0') (reverse (show n)))

-- 3ª solución
-- =============

cerosDelFactorial3 :: Integer -> Integer
cerosDelFactorial3 n
  | n < 5     = 0
  | otherwise = m + cerosDelFactorial3 m
  where m = n `div` 5

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> Integer) -> Spec
specG cerosDelFactorial = do
  it "e1" $
    cerosDelFactorial 24 `shouldBe` 4
  it "e2" $
    cerosDelFactorial 25 `shouldBe` 6

spec :: Spec
spec = do
  describe "def. 1" $ specG cerosDelFactorial1
  describe "def. 2" $ specG cerosDelFactorial2
  describe "def. 3" $ specG cerosDelFactorial3

-- La verificación es
--    λ> verifica
--
--    6 examples, 0 failures

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_cerosDelFactorial :: Positive Integer -> Bool
prop_cerosDelFactorial (Positive n) =
  all (== cerosDelFactorial1 n)
      [cerosDelFactorial2 n,
       cerosDelFactorial3 n]

-- La comprobación es
--    λ> quickCheck prop_cerosDelFactorial
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> cerosDelFactorial1 (4*10^4)
--    9998
--    (1.93 secs, 2,296,317,904 bytes)
--    λ> cerosDelFactorial2 (4*10^4)
--    9998
--    (1.57 secs, 1,636,242,040 bytes)
--    λ> cerosDelFactorial3 (4*10^4)
--    9998
--    (0.02 secs, 527,584 bytes)

from itertools import takewhile
from math import factorial
from sys import set_int_max_str_digits
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

set_int_max_str_digits(10**6)

# 1ª solución
# ===========

# ceros(n) es el número de ceros en los que termina el número n. Por
# ejemplo,
#    ceros(320000)  ==  4
def ceros(n: int) -> int:
    r = 0
    while n % 10 == 0 and n != 0:
        r += 1
        n //= 10
    return r

def cerosDelFactorial1(n: int) -> int:
    return ceros(factorial(n))

# 2ª solución
# ===========

def ceros2(n: int) -> int:
    return len(list(takewhile(lambda x: x == '0', reversed(str(n)))))

def cerosDelFactorial2(n: int) -> int:
    return ceros2(factorial(n))

# 3ª solución
# =============

def cerosDelFactorial3(n: int) -> int:
    r = 0
    while n >= 5:
        n = n // 5
        r += n
    return r

# Verificación
# ============

def test_cerosDelFactorial() -> None:
    for cerosDelFactorial in [cerosDelFactorial1,
                              cerosDelFactorial2,
                              cerosDelFactorial3]:
        assert cerosDelFactorial(24) == 4
        assert cerosDelFactorial(25) == 6
    print("Verificado")

# La verificación es
#    >>> test_cerosDelFactorial()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=0, max_value=1000))
def test_cerosDelFactorial_equiv(n: int) -> None:
    r = cerosDelFactorial1(n)
    assert cerosDelFactorial2(n) == r
    assert cerosDelFactorial3(n) == r

# La comprobación es
#    >>> test_cerosDelFactorial_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('cerosDelFactorial1(6*10**4)')
#    2.47 segundos
#    >>> tiempo('cerosDelFactorial2(6*10**4)')
#    0.77 segundos
#    >>> tiempo('cerosDelFactorial3(6*10**4)')
#    0.00 segundos

# Comprobación de todas las propiedades
# =====================================

# La comprobación es
#    src> poetry run pytest -v Ceros_finales_del_factorial.py
#       test_cerosDelFactorial PASSED
#       test_cerosDelFactorial_equiv PASSED