Menu Close

Día: 10 mayo, 2021

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

   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)

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>