Suma de no múltiplos
El enunciado del 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
1 |
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,
1 2 3 4 |
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
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 |
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) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>