Menu Close

Exponente de la mayor potencia de x que divide a y

Definir la función

   mayorExponente :: Integer -> Integer -> Integer

tal que mayorExponente a b es el exponente de la mayor potencia de a que divide a b. Por ejemplo,

   mayorExponente 2 8    ==  3
   mayorExponente 2 9    ==  0
   mayorExponente 5 100  ==  2
   mayorExponente 2 60   ==  2

Nota: Se supone que a > 1 y b > 0.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
mayorExponente1 :: Integer -> Integer -> Integer
mayorExponente1 a b
  | rem b a /= 0 = 0
  | otherwise    = 1 + mayorExponente1 a (b `div` a)
 
-- 2ª solución
-- ===========
 
mayorExponente2 :: Integer -> Integer -> Integer
mayorExponente2 a b = aux b 0
  where
    aux c r | rem c a /= 0 = r
            | otherwise    = aux (c `div` a) (r + 1)
 
-- 3ª solución
-- ===========
 
mayorExponente3 :: Integer -> Integer -> Integer
mayorExponente3 a b = head [x-1 | x <- [0..], mod b (a^x) /= 0]
 
-- 4ª solución
-- ===========
 
mayorExponente4 :: Integer -> Integer -> Integer
mayorExponente4 a b =
  fst (until (\ (_,c) -> rem c a /= 0)
             (\ (r,c) -> (r+1, c `div` a))
             (0,b))
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_mayorExponente :: Integer -> Integer -> Property
prop_mayorExponente a b =
  a > 1 && b > 0 ==>
  all (== mayorExponente1 a b)
      [mayorExponente2 a b,
       mayorExponente3 a b,
       mayorExponente4 a b]
 
-- La comprobación es
--    λ> quickCheck prop_mayorExponente
--    +++ OK, passed 100 tests; 457 discarded.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> mayorExponente1 2 (2^(5*10^4))
--    50000
--    (0.12 secs, 179,578,424 bytes)
--    λ> mayorExponente2 2 (2^(5*10^4))
--    50000
--    (0.13 secs, 181,533,376 bytes)
--    λ> mayorExponente3 2 (2^(5*10^4))
--    50000
--    (3.88 secs, 818,319,096 bytes)
--    λ> mayorExponente4 2 (2^(5*10^4))
--    50000
--    (0.13 secs, 181,133,344 bytes)
--
--    λ> mayorExponente1 2 (2^(3*10^5))
--    300000
--    (2.94 secs, 5,762,199,064 bytes)
--    λ> mayorExponente2 2 (2^(3*10^5))
--    300000
--    (2.91 secs, 5,773,829,624 bytes)
--    λ> mayorExponente4 2 (2^(3*10^5))
--    300000
--    (3.70 secs, 5,771,396,824 bytes)

El código se encuentra en GitHub.


Soluciones en Python

from itertools import islice
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import Iterator
 
from hypothesis import given
from hypothesis import strategies as st
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
def mayorExponente1(a: int, b: int) -> int:
    if b % a != 0:
        return 0
    return 1 + mayorExponente1(a, b // a)
 
# 2ª solución
# ===========
 
def mayorExponente2(a: int, b: int) -> int:
    def aux(c: int, r: int) -> int:
        if c % a != 0:
            return r
        return aux(c // a, r + 1)
    return aux(b, 0)
 
# 3ª solución
# ===========
 
# naturales es el generador de los números naturales, Por ejemplo,
#    >>> list(islice(naturales(), 5))
#    [0, 1, 2, 3, 4]
def naturales() -> Iterator[int]:
    i = 0
    while True:
        yield i
        i += 1
 
def mayorExponente3(a: int, b: int) -> int:
    return list(islice((x - 1 for x in naturales() if b % (a**x) != 0), 1))[0]
 
# 4ª solución
# ===========
 
def mayorExponente4(a: int, b: int) -> int:
    r = 0
    while b % a == 0:
        b = b // a
        r = r + 1
    return r
 
# Comprobación de equivalencia
# ============================
 
def prueba1() -> None:
    for x in range(2, 11):
        for y in range(1, 11):
            print(x, y, mayorExponente4(x, y))
 
 
# La propiedad es
@given(st.integers(min_value=2, max_value=10),
       st.integers(min_value=1, max_value=10))
def test_mayorExponente(a: int, b: int) -> None:
    r = mayorExponente1(a, b)
    assert mayorExponente2(a, b) == r
    assert mayorExponente3(a, b) == r
    assert mayorExponente4(a, b) == r
 
# La comprobación es
#    src> poetry run pytest -q exponente_mayor.py
#    1 passed in 0.16s
 
# 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('mayorExponente1(2, 2**(2*10**4))')
#    0.13 segundos
#    >>> tiempo('mayorExponente2(2, 2**(2*10**4))')
#    0.13 segundos
#    >>> tiempo('mayorExponente3(2, 2**(2*10**4))')
#    1.81 segundos
#    >>> tiempo('mayorExponente4(2, 2**(2*10**4))')
#    0.12 segundos
#
#    >>> tiempo('mayorExponente4(2, 2**(2*10**5))')
#    12.19 segundos

El código se encuentra en GitHub.

Haskell y Python

Escribe tu solución

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