Suma de múltiplos de 3 ó 5
Definir la función
euler1 :: Integer -> Integer
tal que euler1 n es la suma de todos los múltiplos de 3 ó 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) == 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.
Soluciones en Haskell
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.
Soluciones en Python
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.