Menu Close

Suma de múltiplos de 3 o de 5

José A. Alonso,

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

Soluciones

import Data.List (nub, union)
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
 
-- 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]]
 
-- 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)

El código se encuentra en GitHub.

Ejercicio
,

Una solución de “Suma de múltiplos de 3 o de 5”

  1. Responder
    j0sejuan

    Generalizando a alguno de N números.

    import Data.List
 
-- múltiplos de 1 coste O(n)
sumaMultiplos1' n m = sum [n,n+n..m-1]
 
-- múltiplos de 1 coste O(1)
sumaMultiplos1 n m = n * j * (j + 1) `div` 2 where j = (m-1) `div` n
 
-- múltiplos de 3 o 5 coste O(n)
sumaMultiplos' m = sumaMultiplos1' 3 m + sumaMultiplos1' 5 m - sumaMultiplos1' 15 m
 
-- múltiplos de 3 o 5 coste O(1)
sumaMultiplos m = sumaMultiplos1 3 m + sumaMultiplos1 5 m - sumaMultiplos1 15 m
 
{-
 
*Main> quickCheck $ m -> m > 0 ==> sumaMultiplos' m == sumaMultiplos m
+++ OK, passed 100 tests; 135 discarded.
(0.02 secs, 4,282,360 bytes)
 
-}
 
-- múltiplos de alguno de la lista con coste O(|ns|·m)
sumaMultiplosples' ns m = sum [z | z <- [1..m-1], any ((0==).(z `mod`)) ns]
 
{-
 
*Main> quickCheck $ m -> m > 0 ==> sumaMultiplos m == sumaMultiplosples' [3, 5] m
+++ OK, passed 100 tests; 113 discarded.
(0.03 secs, 5,497,288 bytes)
 
-}
 
combs [] _ = []
combs ns 1 = return <$> ns
combs (n:ns) m = combs ns m ++ map (n:) (combs ns (m-1))
 
-- múltiplos de alguno de la lista con coste O(2^|ns|)
sumaMultiplosples ns m = rec 1 1
  where sz = length ns
        rec w s
          | w > sz = 0
          | otherwise = rec (w + 1) (-1 * s)
                      + sum [ s * sumaMultiplos1 (foldl1 lcm xs) m
                            | xs <- combs ns w ]
 
{-
 
*Main> quickCheckWith stdArgs {maxSuccess = 100000} $ ns m ->
    all (>0) ns && m > 0 ==> sumaMultiplosples' ns m == sumaMultiplosples ns m
*** Gave up! Passed only 18289 tests; 1000000 discarded tests.
(15.45 secs, 23,303,246,544 bytes)
 
 
*Main> sumaMultiplosples' [11..15] (10^7)
16033948961721
(19.65 secs, 10,135,797,400 bytes)
 
*Main> sumaMultiplosples [11..15] (10^7)
16033948961721
(0.02 secs, 234,208 bytes)
 
-}

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.