{"id":7486,"date":"2022-11-01T06:00:41","date_gmt":"2022-11-01T04:00:41","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7486"},"modified":"2022-12-14T12:18:47","modified_gmt":"2022-12-14T10:18:47","slug":"exponente_de-la-mayor-potencia-de-x-que-divide-a-y","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/exponente_de-la-mayor-potencia-de-x-que-divide-a-y\/","title":{"rendered":"Exponente de la mayor potencia de x que divide a y"},"content":{"rendered":"

Definir la funci\u00f3n<\/p>\n

\n   mayorExponente :: Integer -> Integer -> Integer\n<\/pre>\n
tal que mayorExponente a b<\/code> es el exponente de la mayor potencia de a<\/code> que divide a b<\/code>. Por ejemplo,<\/p>\n
\n   mayorExponente 2 8    ==  3\n   mayorExponente 2 9    ==  0\n   mayorExponente 5 100  ==  2\n   mayorExponente 2 60   ==  2\n<\/pre>\n
Nota: Se supone que a > 1 y b > 0.<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmayorExponente1 :: Integer -> Integer -> Integer\nmayorExponente1 a b\n  | rem b a \/= 0 = 0\n  | otherwise    = 1 + mayorExponente1 a (b `div` a)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmayorExponente2 :: Integer -> Integer -> Integer\nmayorExponente2 a b = aux b 0\n  where\n    aux c r | rem c a \/= 0 = r\n            | otherwise    = aux (c `div` a) (r + 1)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmayorExponente3 :: Integer -> Integer -> Integer\nmayorExponente3 a b = head [x-1 | x <- [0..], mod b (a^x) \/= 0]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nmayorExponente4 :: Integer -> Integer -> Integer\nmayorExponente4 a b =\n  fst (until (\\ (_,c) -> rem c a \/= 0)\n             (\\ (r,c) -> (r+1, c `div` a))\n             (0,b))\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_mayorExponente :: Integer -> Integer -> Property\nprop_mayorExponente a b =\n  a > 1 && b > 0 ==>\n  all (== mayorExponente1 a b)\n      [mayorExponente2 a b,\n       mayorExponente3 a b,\n       mayorExponente4 a b]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_mayorExponente\n--    +++ OK, passed 100 tests; 457 discarded.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> mayorExponente1 2 (2^(5*10^4))\n--    50000\n--    (0.12 secs, 179,578,424 bytes)\n--    \u03bb> mayorExponente2 2 (2^(5*10^4))\n--    50000\n--    (0.13 secs, 181,533,376 bytes)\n--    \u03bb> mayorExponente3 2 (2^(5*10^4))\n--    50000\n--    (3.88 secs, 818,319,096 bytes)\n--    \u03bb> mayorExponente4 2 (2^(5*10^4))\n--    50000\n--    (0.13 secs, 181,133,344 bytes)\n--\n--    \u03bb> mayorExponente1 2 (2^(3*10^5))\n--    300000\n--    (2.94 secs, 5,762,199,064 bytes)\n--    \u03bb> mayorExponente2 2 (2^(3*10^5))\n--    300000\n--    (2.91 secs, 5,773,829,624 bytes)\n--    \u03bb> mayorExponente4 2 (2^(3*10^5))\n--    300000\n--    (3.70 secs, 5,771,396,824 bytes)\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom itertools import islice\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import Iterator\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef mayorExponente1(a: int, b: int) -> int:\n    if b % a != 0:\n        return 0\n    return 1 + mayorExponente1(a, b \/\/ a)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef mayorExponente2(a: int, b: int) -> int:\n    def aux(c: int, r: int) -> int:\n        if c % a != 0:\n            return r\n        return aux(c \/\/ a, r + 1)\n    return aux(b, 0)\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\n# naturales es el generador de los n\u00fameros naturales, Por ejemplo,\n#    >>> list(islice(naturales(), 5))\n#    [0, 1, 2, 3, 4]\ndef naturales() -> Iterator[int]:\n    i = 0\n    while True:\n        yield i\n        i += 1\n\ndef mayorExponente3(a: int, b: int) -> int:\n    return list(islice((x - 1 for x in naturales() if b % (a**x) != 0), 1))[0]\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef mayorExponente4(a: int, b: int) -> int:\n    r = 0\n    while b % a == 0:\n        b = b \/\/ a\n        r = r + 1\n    return r\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\ndef prueba1() -> None:\n    for x in range(2, 11):\n        for y in range(1, 11):\n            print(x, y, mayorExponente4(x, y))\n\n\n# La propiedad es\n@given(st.integers(min_value=2, max_value=10),\n       st.integers(min_value=1, max_value=10))\ndef test_mayorExponente(a: int, b: int) -> None:\n    r = mayorExponente1(a, b)\n    assert mayorExponente2(a, b) == r\n    assert mayorExponente3(a, b) == r\n    assert mayorExponente4(a, b) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q exponente_mayor.py\n#    1 passed in 0.16s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('mayorExponente1(2, 2**(2*10**4))')\n#    0.13 segundos\n#    >>> tiempo('mayorExponente2(2, 2**(2*10**4))')\n#    0.13 segundos\n#    >>> tiempo('mayorExponente3(2, 2**(2*10**4))')\n#    1.81 segundos\n#    >>> tiempo('mayorExponente4(2, 2**(2*10**4))')\n#    0.12 segundos\n#\n#    >>> tiempo('mayorExponente4(2, 2**(2*10**5))')\n#    12.19 segundos\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Definir la funci\u00f3n 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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7486"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7486"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7486\/revisions"}],"predecessor-version":[{"id":7658,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7486\/revisions\/7658"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7486"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7486"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7486"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}