Suma de múltiplos de 3 o de 5
Los números naturales menores que 10 que son múltiplos de 3 ó 5 son 3, 5, 6 y 9. La suma de estos múltiplos es 23.
Definir la función
sumaMultiplos :: Integer -> Integer
tal que (sumaMultiplos n) es la suma de todos los múltiplos de 3 ó 5 menores que n. Por ejemplo,
sumaMultiplos 10 == 23 sumaMultiplos (10^2) == 2318 sumaMultiplos (10^3) == 233168 sumaMultiplos (10^4) == 23331668 sumaMultiplos (10^5) == 2333316668 sumaMultiplos (10^6) == 233333166668 sumaMultiplos (10^7) == 23333331666668
1. Soluciones en Haskell
module Suma_de_multiplos_de_3_o_de_5 where import Data.List (nub, union) import Test.Hspec (Spec, describe, hspec, it, shouldBe) import Test.QuickCheck (Positive(..), quickCheck) -- 1ª solución -- =========== sumaMultiplos1 :: Integer -> Integer sumaMultiplos1 n = sum [x | x <- [1..n-1], multiplo x 3 || multiplo x 5] -- (multiplo x y) se verifica si x es múltiplo de y. Por ejemplo, -- multiplo 6 3 == True -- multiplo 6 4 == False multiplo :: Integer -> Integer -> Bool multiplo x y = mod x y == 0 -- 2ª solución -- =========== sumaMultiplos2 :: Integer -> Integer sumaMultiplos2 n = sum [x | x <- [1..n-1], gcd x 15 > 1] -- 3ª solución -- =========== sumaMultiplos3 :: Integer -> Integer sumaMultiplos3 n = sum [3,6..n-1] + sum [5,10..n-1] - sum [15,30..n-1] -- 4ª solución -- =========== sumaMultiplos4 :: Integer -> Integer sumaMultiplos4 n = sum (nub ([3,6..n-1] ++ [5,10..n-1])) -- 5ª solución -- =========== sumaMultiplos5 :: Integer -> Integer sumaMultiplos5 n = sum ([3,6..n-1] `union` [5,10..n-1]) -- 6ª solución -- =========== sumaMultiplos6 :: Integer -> Integer sumaMultiplos6 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 10 == 18 -- suma 5 10 == 5 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 -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Integer -> Integer) -> Spec specG sumaMultiplos = do it "e1" $ sumaMultiplos 10 `shouldBe` 23 it "e2" $ sumaMultiplos (10^2) `shouldBe` 2318 spec :: Spec spec = do describe "def. 1" $ specG sumaMultiplos1 describe "def. 2" $ specG sumaMultiplos2 describe "def. 3" $ specG sumaMultiplos3 describe "def. 4" $ specG sumaMultiplos4 describe "def. 5" $ specG sumaMultiplos5 describe "def. 6" $ specG sumaMultiplos6 -- La verificación es -- λ> verifica -- -- 12 examples, 0 failures -- Equivalencia de definiciones -- ============================ -- La propiedad es prop_sumaMultiplos :: Positive Integer -> Bool prop_sumaMultiplos (Positive n) = all (== (sumaMultiplos1 n)) [f n | f <- [sumaMultiplos1, sumaMultiplos2, sumaMultiplos3, sumaMultiplos4, sumaMultiplos5, sumaMultiplos6]] verifica_sumaMultiplos :: IO () verifica_sumaMultiplos = quickCheck prop_sumaMultiplos -- La comprobación es -- λ> verifica_sumaMultiplos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sumaMultiplos1 (5*10^4) -- 583291668 -- (0.05 secs, 21,446,456 bytes) -- λ> sumaMultiplos2 (5*10^4) -- 583291668 -- (0.05 secs, 26,804,944 bytes) -- λ> sumaMultiplos3 (5*10^4) -- 583291668 -- (0.01 secs, 5,136,728 bytes) -- λ> sumaMultiplos4 (5*10^4) -- 583291668 -- (3.05 secs, 7,474,304 bytes) -- λ> sumaMultiplos5 (5*10^4) -- 583291668 -- (5.14 secs, 12,787,717,152 bytes) -- λ> sumaMultiplos6 (5*10^4) -- 583291668 -- (0.01 secs, 108,448 bytes) -- -- λ> sumaMultiplos1 (3*10^6) -- 2099998500000 -- (2.14 secs, 1,281,805,696 bytes) -- λ> sumaMultiplos2 (3*10^6) -- 2099998500000 -- (1.86 secs, 1,603,407,272 bytes) -- λ> sumaMultiplos3 (3*10^6) -- 2099998500000 -- (0.39 secs, 304,681,080 bytes) -- λ> sumaMultiplos6 (3*10^6) -- 2099998500000 -- (0.01 secs, 112,544 bytes) -- -- λ> sumaMultiplos3 (10^7) -- 23333331666668 -- (1.69 secs, 1,015,468,352 bytes) -- λ> sumaMultiplos6 (10^7) -- 23333331666668 -- (0.01 secs, 112,336 bytes)
2. 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 sumaMultiplos1(n: int) -> int: return sum(x for x in range(1, n) if (multiplo(x, 3) or multiplo(x, 5))) # 2ª solución -- # =========== def sumaMultiplos2(n: int) -> int: return sum(x for x in range(1, n) if gcd(x, 15) > 1) # 3ª solución -- # =========== def sumaMultiplos3(n: int) -> int: return sum(range(3, n, 3)) + \ sum(range(5, n, 5)) - \ sum(range(15, n, 15)) # 4ª solución -- # =========== def sumaMultiplos4(n: int) -> int: return sum(set(list(range(3, n, 3)) + list(range(5, n, 5)))) # 5ª solución -- # =========== def sumaMultiplos5(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 sumaMultiplos6(n: int) -> int: return suma(3, n) + suma(5, n) - suma(15, n) # Verificación # ============ def test_sumaMultiplos() -> None: for sumaMultiplos in [sumaMultiplos1, sumaMultiplos2, sumaMultiplos3, sumaMultiplos4, sumaMultiplos5, sumaMultiplos6]: assert sumaMultiplos(10) == 23 assert sumaMultiplos(10**2) == 2318 print("Verificado") # La verificación es # >>> test_sumaMultiplos() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_sumaMultiplos_equiv(n: int) -> None: r = sumaMultiplos1(n) assert sumaMultiplos2(n) == r assert sumaMultiplos3(n) == r assert sumaMultiplos4(n) == r assert sumaMultiplos5(n) == r assert sumaMultiplos6(n) == r # La comprobación es # src> poetry run pytest -q Suma_de_multiplos_de_3_o_de_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('sumaMultiplosa(10**7)') # 1.49 segundos # >>> tiempo('sumaMultiplosb(10**7)') # 0.93 segundos # >>> tiempo('sumaMultiplosc(10**7)') # 0.07 segundos # >>> tiempo('sumaMultiplosd(10**7)') # 0.42 segundos # >>> tiempo('sumaMultiplose(10**7)') # 0.69 segundos # >>> tiempo('sumaMultiplosf(10**7)') # 0.00 segundos # # >>> tiempo('sumaMultiplosc(10**8)') # 0.72 segundos # >>> tiempo('sumaMultiplosf(10**8)') # 0.00 segundos