Suma de no múltiplos
El enunciado de un problema 1 de la Fase Local de la Olimpiada Matemática Española del 2011 es
Dado un entero positivo n, hallar la suma de todos los enteros positivos inferiores a 10n que no son múltiplos de 2 ni de 5.
Definir la función
suma :: Integer -> Integer
tal que (suma n) es la suma de todos los enteros positivos inferiores a 10n que no son múltiplos de 2 ni de 5. Por ejemplo,
suma 7 == 980 length (show (suma (10^(10^5)))) == 200002 length (show (suma (10^(10^6)))) == 2000002 length (show (suma (10^(10^7)))) == 20000002
Soluciones
import Data.List ((\\)) import Test.QuickCheck (Property, (==>), quickCheck) -- 1ª solución -- =========== suma :: Integer -> Integer suma n = sum [x | x <- [1..10*n], x `mod` 2 /= 0, x `mod` 5 /= 0] -- 2ª solución -- =========== suma2 :: Integer -> Integer suma2 n = sum ([1..10*n] \\ ([2,4..10*n] ++ [5,10..10*n])) -- 3ª solución -- =========== -- Observando los siguientes cálculos -- λ> map suma [1..10] -- [20,80,180,320,500,720,980,1280,1620,2000] -- λ> map (`div` 20) it -- [1,4,9,16,25,36,49,64,81,100] suma3 :: Integer -> Integer suma3 n = 20*n^2 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_suma :: Integer -> Property prop_suma n = n > 0 ==> all (== (suma n)) [suma2 n, suma3 n] -- La comprobación es -- λ> quickCheck prop_suma -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> suma (2*10^3) -- 80000000 -- (0.05 secs, 6,671,720 bytes) -- λ> suma2 (2*10^3) -- 80000000 -- (2.63 secs, 7,886,190,192 bytes) -- λ> suma3 (2*10^3) -- 80000000 -- (0.02 secs, 106,736 bytes) -- -- λ> suma (4*10^5) -- 3200000000000 -- (2.31 secs, 1,314,056,144 bytes) -- λ> suma3 (4*10^5) -- 3200000000000 -- (0.02 secs, 106,808 bytes)