Suma de múltiplos de 3 ó 5
Definir la función
1 |
euler1 :: Integer -> Integer |
tal que euler1 n
es la suma de todos los múltiplos de 3 ó 5 menores que n
. Por ejemplo,
1 2 3 4 5 6 7 8 |
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) == 2333333333333333333316666666666666666668 euler1 (10^30) == 233333333333333333333333333333166666666666666666666666666668 |
Nota: Este ejercicio está basado en el problema 1 del Proyecto Euler
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
import Data.List (nub, union) import qualified Data.Set as S (fromAscList, union) import Test.QuickCheck -- 1ª solución -- =========== euler1a :: Integer -> Integer euler1a n = sum [x | x <- [1..n-1], multiplo x 3 || multiplo x 5] -- (multiplo x y) se verifica si x es un múltiplo de y. Por ejemplo. -- multiplo 12 3 == True -- multiplo 14 3 == False multiplo :: Integer -> Integer -> Bool multiplo x y = mod x y == 0 -- 2ª solución -- -- =========== euler1b :: Integer -> Integer euler1b n = sum [x | x <- [1..n-1], gcd x 15 > 1] -- 3ª solución -- -- =========== euler1c :: Integer -> Integer euler1c n = sum [3,6..n-1] + sum [5,10..n-1] - sum [15,30..n-1] -- 4ª solución -- -- =========== euler1d :: Integer -> Integer euler1d n = sum (nub ([3,6..n-1] ++ [5,10..n-1])) -- 5ª solución -- -- =========== euler1e :: Integer -> Integer euler1e n = sum ([3,6..n-1] `union` [5,10..n-1]) -- 6ª solución -- -- =========== euler1f :: Integer -> Integer euler1f n = sum (S.fromAscList [3,6..n-1] `S.union` S.fromAscList [5,10..n-1]) -- 7ª solución -- -- =========== euler1g :: Integer -> Integer euler1g n = suma 3 n + suma 5 n - suma 15 n -- (suma d x) es la suma de los múltiplos de d menores que x. Por -- ejemplo, -- suma 3 20 == 63 suma :: Integer -> Integer -> Integer suma d x = (a+b)*n `div` 2 where a = d b = d * ((x-1) `div` d) n = 1 + (b-a) `div` d -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_euler1 :: Positive Integer -> Bool prop_euler1 (Positive n) = all (== euler1a n) [euler1b n, euler1c n, euler1d n, euler1e n, euler1f n, euler1g n] -- La comprobación es -- λ> quickCheck prop_euler1 -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> euler1a (5*10^4) -- 583291668 -- (0.05 secs, 21,895,296 bytes) -- λ> euler1b (5*10^4) -- 583291668 -- (0.05 secs, 26,055,096 bytes) -- λ> euler1c (5*10^4) -- 583291668 -- (0.01 secs, 5,586,072 bytes) -- λ> euler1d (5*10^4) -- 583291668 -- (2.83 secs, 7,922,304 bytes) -- λ> euler1e (5*10^4) -- 583291668 -- (4.56 secs, 12,787,705,248 bytes) -- λ> euler1f (5*10^4) -- 583291668 -- (0.01 secs, 8,168,584 bytes) -- λ> euler1g (5*10^4) -- 583291668 -- (0.02 secs, 557,488 bytes) -- -- λ> euler1a (3*10^6) -- 2099998500000 -- (2.72 secs, 1,282,255,816 bytes) -- λ> euler1b (3*10^6) -- 2099998500000 -- (2.06 secs, 1,531,855,776 bytes) -- λ> euler1c (3*10^6) -- 2099998500000 -- (0.38 secs, 305,127,480 bytes) -- λ> euler1f (3*10^6) -- 2099998500000 -- (0.54 secs, 457,358,232 bytes) -- λ> euler1g (3*10^6) -- 2099998500000 -- (0.01 secs, 560,472 bytes) -- -- λ> euler1c (10^7) -- 23333331666668 -- (1.20 secs, 1,015,920,024 bytes) -- λ> euler1f (10^7) -- 23333331666668 -- (2.00 secs, 1,523,225,648 bytes) -- λ> euler1g (10^7) -- 23333331666668 -- (0.01 secs, 561,200 bytes) |
El código se encuentra en GitHub.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
from math import gcd from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st # 1ª solución # =========== # multiplo(x, y) se verifica si x es un múltiplo de y. Por ejemplo. # multiplo(12, 3) == True # multiplo(14, 3) == False def multiplo(x: int, y: int) -> int: return x % y == 0 def euler1a(n: int) -> int: return sum(x for x in range(1, n) if (multiplo(x, 3) or multiplo(x, 5))) # 2ª solución -- # =========== def euler1b(n: int) -> int: return sum(x for x in range(1, n) if gcd(x, 15) > 1) # 3ª solución -- # =========== def euler1c(n: int) -> int: return sum(range(3, n, 3)) + \ sum(range(5, n, 5)) - \ sum(range(15, n, 15)) # 4ª solución -- # =========== def euler1d(n: int) -> int: return sum(set(list(range(3, n, 3)) + list(range(5, n, 5)))) # 5ª solución -- # =========== def euler1e(n: int) -> int: return sum(set(list(range(3, n, 3))) | set(list(range(5, n, 5)))) # 6ª solución -- # =========== # suma(d, x) es la suma de los múltiplos de d menores que x. Por # ejemplo, # suma(3, 20) == 63 def suma(d: int, x: int) -> int: a = d b = d * ((x - 1) // d) n = 1 + (b - a) // d return (a + b) * n // 2 def euler1f(n: int) -> int: return suma(3, n) + suma(5, n) - suma(15, n) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_euler1(n: int) -> None: r = euler1a(n) assert euler1b(n) == r assert euler1c(n) == r assert euler1d(n) == r assert euler1e(n) == r # La comprobación es # src> poetry run pytest -q suma_de_multiplos_de_3_o_5.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('euler1a(10**7)') # 1.49 segundos # >>> tiempo('euler1b(10**7)') # 0.93 segundos # >>> tiempo('euler1c(10**7)') # 0.07 segundos # >>> tiempo('euler1d(10**7)') # 0.42 segundos # >>> tiempo('euler1e(10**7)') # 0.69 segundos # >>> tiempo('euler1f(10**7)') # 0.00 segundos # # >>> tiempo('euler1c(10**8)') # 0.72 segundos # >>> tiempo('euler1f(10**8)') # 0.00 segundos |
El código se encuentra en GitHub.