{"id":7425,"date":"2022-10-10T06:00:46","date_gmt":"2022-10-10T04:00:46","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7425"},"modified":"2022-12-14T14:14:34","modified_gmt":"2022-12-14T12:14:34","slug":"suma-de-multiplos-de-3-o-5","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/suma-de-multiplos-de-3-o-5\/","title":{"rendered":"Suma de m\u00faltiplos de 3 \u00f3 5"},"content":{"rendered":"

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

\n   euler1 :: Integer -> Integer\n<\/pre>\n
tal que euler1 n<\/code> es la suma de todos los m\u00faltiplos de 3 \u00f3 5 menores que n<\/code>. Por ejemplo,<\/p>\n
\n   euler1 10      == 23\n   euler1 (10^2)  == 2318\n   euler1 (10^3)  == 233168\n   euler1 (10^4)  == 23331668\n   euler1 (10^5)  == 2333316668\n   euler1 (10^10) == 23333333331666666668\n   euler1 (10^20) == 2333333333333333333316666666666666666668\n   euler1 (10^30) == 233333333333333333333333333333166666666666666666666666666668\n<\/pre>\n
Nota:<\/strong> Este ejercicio est\u00e1 basado en el problema 1<\/a> del Proyecto Euler<\/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 Data.List (nub, union)\nimport qualified Data.Set as S (fromAscList, union)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\neuler1a :: Integer -> Integer\neuler1a n =\n  sum [x | x <- [1..n-1],\n           multiplo x 3 || multiplo x 5]\n\n-- (multiplo x y) se verifica si x es un m\u00faltiplo de y. Por ejemplo.\n--    multiplo 12 3  ==  True\n--    multiplo 14 3  ==  False\nmultiplo :: Integer -> Integer -> Bool\nmultiplo x y = mod x y == 0\n\n-- 2\u00aa soluci\u00f3n                                                        --\n-- ===========\n\neuler1b :: Integer -> Integer\neuler1b n =\n  sum [x | x <- [1..n-1],\n           gcd x 15 > 1]\n\n-- 3\u00aa soluci\u00f3n                                                        --\n-- ===========\n\neuler1c :: Integer -> Integer\neuler1c n =\n  sum [3,6..n-1] + sum [5,10..n-1] - sum [15,30..n-1]\n\n-- 4\u00aa soluci\u00f3n                                                        --\n-- ===========\n\neuler1d :: Integer -> Integer\neuler1d n =\n  sum (nub ([3,6..n-1] ++ [5,10..n-1]))\n\n-- 5\u00aa soluci\u00f3n                                                        --\n-- ===========\n\neuler1e :: Integer -> Integer\neuler1e n =\n  sum ([3,6..n-1] `union` [5,10..n-1])\n\n-- 6\u00aa soluci\u00f3n                                                        --\n-- ===========\n\neuler1f :: Integer -> Integer\neuler1f n =\n  sum (S.fromAscList [3,6..n-1] `S.union` S.fromAscList [5,10..n-1])\n\n-- 7\u00aa soluci\u00f3n                                                      --\n-- ===========\n\neuler1g :: Integer -> Integer\neuler1g n =\n  suma 3 n + suma 5 n - suma 15 n\n\n-- (suma d x) es la suma de los m\u00faltiplos de d menores que x. Por\n-- ejemplo,\n--    suma 3 20  ==  63\nsuma :: Integer -> Integer -> Integer\nsuma d x = (a+b)*n `div` 2\n    where a = d\n          b = d * ((x-1) `div` d)\n          n = 1 + (b-a) `div` d\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_euler1 :: Positive Integer -> Bool\nprop_euler1 (Positive n) =\n  all (== euler1a n)\n      [euler1b n,\n       euler1c n,\n       euler1d n,\n       euler1e n,\n       euler1f n,\n       euler1g n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_euler1\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> euler1a (5*10^4)\n--    583291668\n--    (0.05 secs, 21,895,296 bytes)\n--    \u03bb> euler1b (5*10^4)\n--    583291668\n--    (0.05 secs, 26,055,096 bytes)\n--    \u03bb> euler1c (5*10^4)\n--    583291668\n--    (0.01 secs, 5,586,072 bytes)\n--    \u03bb> euler1d (5*10^4)\n--    583291668\n--    (2.83 secs, 7,922,304 bytes)\n--    \u03bb> euler1e (5*10^4)\n--    583291668\n--    (4.56 secs, 12,787,705,248 bytes)\n--    \u03bb> euler1f (5*10^4)\n--    583291668\n--    (0.01 secs, 8,168,584 bytes)\n--    \u03bb> euler1g (5*10^4)\n--    583291668\n--    (0.02 secs, 557,488 bytes)\n--\n--    \u03bb> euler1a (3*10^6)\n--    2099998500000\n--    (2.72 secs, 1,282,255,816 bytes)\n--    \u03bb> euler1b (3*10^6)\n--    2099998500000\n--    (2.06 secs, 1,531,855,776 bytes)\n--    \u03bb> euler1c (3*10^6)\n--    2099998500000\n--    (0.38 secs, 305,127,480 bytes)\n--    \u03bb> euler1f (3*10^6)\n--    2099998500000\n--    (0.54 secs, 457,358,232 bytes)\n--    \u03bb> euler1g (3*10^6)\n--    2099998500000\n--    (0.01 secs, 560,472 bytes)\n--\n--    \u03bb> euler1c (10^7)\n--    23333331666668\n--    (1.20 secs, 1,015,920,024 bytes)\n--    \u03bb> euler1f (10^7)\n--    23333331666668\n--    (2.00 secs, 1,523,225,648 bytes)\n--    \u03bb> euler1g (10^7)\n--    23333331666668\n--    (0.01 secs, 561,200 bytes)\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom math import gcd\nfrom timeit import Timer, default_timer\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# multiplo(x, y) se verifica si x es un m\u00faltiplo de y. Por ejemplo.\n#    multiplo(12, 3)  ==  True\n#    multiplo(14, 3)  ==  False\ndef multiplo(x: int, y: int) -> int:\n    return x % y == 0\n\ndef euler1a(n: int) -> int:\n    return sum(x for x in range(1, n)\n               if (multiplo(x, 3) or multiplo(x, 5)))\n\n# 2\u00aa soluci\u00f3n                                                        --\n# ===========\n\ndef euler1b(n: int) -> int:\n    return sum(x for x in range(1, n)\n               if gcd(x, 15) > 1)\n\n# 3\u00aa soluci\u00f3n                                                        --\n# ===========\n\ndef euler1c(n: int) -> int:\n    return sum(range(3, n, 3)) + \\\n           sum(range(5, n, 5)) - \\\n           sum(range(15, n, 15))\n\n# 4\u00aa soluci\u00f3n                                                        --\n# ===========\n\ndef euler1d(n: int) -> int:\n    return sum(set(list(range(3, n, 3)) + list(range(5, n, 5))))\n\n# 5\u00aa soluci\u00f3n                                                        --\n# ===========\n\ndef euler1e(n: int) -> int:\n    return sum(set(list(range(3, n, 3))) | set(list(range(5, n, 5))))\n\n# 6\u00aa soluci\u00f3n                                                        --\n# ===========\n\n# suma(d, x) es la suma de los m\u00faltiplos de d menores que x. Por\n# ejemplo,\n#    suma(3, 20)  ==  63\ndef suma(d: int, x: int) -> int:\n    a = d\n    b = d * ((x - 1) \/\/ d)\n    n = 1 + (b - a) \/\/ d\n    return (a + b) * n \/\/ 2\n\ndef euler1f(n: int) -> int:\n    return suma(3, n) + suma(5, n) - suma(15, n)\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_euler1(n: int) -> None:\n    r = euler1a(n)\n    assert euler1b(n) == r\n    assert euler1c(n) == r\n    assert euler1d(n) == r\n    assert euler1e(n) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q suma_de_multiplos_de_3_o_5.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('euler1a(10**7)')\n#    1.49 segundos\n#    >>> tiempo('euler1b(10**7)')\n#    0.93 segundos\n#    >>> tiempo('euler1c(10**7)')\n#    0.07 segundos\n#    >>> tiempo('euler1d(10**7)')\n#    0.42 segundos\n#    >>> tiempo('euler1e(10**7)')\n#    0.69 segundos\n#    >>> tiempo('euler1f(10**7)')\n#    0.00 segundos\n#\n#    >>> tiempo('euler1c(10**8)')\n#    0.72 segundos\n#    >>> tiempo('euler1f(10**8)')\n#    0.00 segundos\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Definir la funci\u00f3n euler1 :: Integer -> Integer tal que euler1 n es la suma de todos los m\u00faltiplos de 3 \u00f3 5 menores que n. Por ejemplo, euler1 10 == 23 euler1 (10^2) == 2318 euler1 (10^3) == 233168 euler1 (10^4) == 23331668 euler1 (10^5) == 2333316668 euler1 (10^10) == 23333333331666666668 euler1 (10^20) ==…<\/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\/7425"}],"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=7425"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7425\/revisions"}],"predecessor-version":[{"id":7675,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7425\/revisions\/7675"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7425"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7425"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7425"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}