Menu Close

Día: 6 mayo, 2021

Múltiplos persistentes de siete

El enunciado del problema 1 de la Fase Local de la Olimpiada Matemática Española del 2021 es

Determinar todos los números de cuatro cifras tales que al insertar un dígito 0 en cualquier posición se obtiene un múltiplo de 7.

Un número n se dice que es un múltiplo persistente de 7 si al insertar el dígito 0 en cualquier posición de n se obtiene un múltiplo de 7.

Definir las funciones

   esMultiploPersistente :: Integer -> Bool
   multiplosPersistentes :: Int -> [Integer]

tales que

  • (esMultiploPersistente n) se verifica si n es un múltiplo persistente de n. Por ejemplo,
     esMultiploPersistente 7007  ==  True
     esMultiploPersistente 7107  ==  False
  • (multiplosPersistentes k) es la lista de los números con k dígitos que son múltiplos persistentes de 7. Por ejemplo,
     take 2 (multiplosPersistentes 4)   ==  [7000,7007]
     length (multiplosPersistentes 20)  ==  524288

Usando la función multiplosPersistentes, calcular la respuesta al problema de la Olimpiada.

Soluciones

import Data.List (sort)
 
-- 1ª definición de esMultiploPersistente
-- ======================================
 
esMultiploPersistente :: Integer -> Bool
esMultiploPersistente n =
  and [x `mod` 7 == 0 | x <- insertados n]
 
-- (insertados n) es la lista de los números obtenidos insertando un 0
-- en cualquier posición de n. Por ejemplo,
--    insertados 3264  ==  [3264,30264,32064,32604,32640]
insertados :: Integer -> [Integer]
insertados n =
  [read (xs ++ "0" ++ ys) | k <- [0..length ns],
                            let (xs,ys) = splitAt k ns]
  where ns = show n
 
-- 1ª definición de multiplosPersistentes
-- ======================================
 
multiplosPersistentes :: Int -> [Integer]
multiplosPersistentes n =
  filter esMultiploPersistente [10^(n-1)..10^n-1]
 
-- 2ª definición de multiplosPersistentes
-- ======================================
 
multiplosPersistentes2 :: Int -> [Integer]
multiplosPersistentes2 n =
  filter esMultiploPersistente [7*10^(n-1),7*10^(n-1)+7..7*((10^n-1) `div` 9)]
 
-- 3ª definición de esMultiploPersistente
-- ======================================
 
-- Observando los cálculos
--    multiplosPersistentes2 1  ==  [7]
--    multiplosPersistentes2 2  ==  [70,77]
--    multiplosPersistentes2 3  ==  [700,707,770,777]
--    multiplosPersistentes2 4  ==  [7000,7007,7070,7077,7700,7707,7770,7777]
 
esMultiploPersistente2 :: Integer -> Bool
esMultiploPersistente2 n =
  all (`elem` "07") (show n)
 
-- 3ª definición de multiplosPersistentes
-- ======================================
 
multiplosPersistentes3 :: Int -> [Integer]
multiplosPersistentes3 n =
  filter esMultiploPersistente2 [7*10^(n-1),7*10^(n-1)+7..7*((10^n-1) `div` 9)]
 
-- 4ª definición de multiplosPersistentes
-- ======================================
 
multiplosPersistentes4 :: Int -> [Integer]
multiplosPersistentes4 k =
  sort [read (reverse cs) | cs <- aux k]
  where aux 1 = ["7"]
        aux n = map ('0':) xs ++ map ('7':) xs
          where xs = aux (n-1)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_multiplosPresistentes :: Int -> Bool
prop_multiplosPresistentes n =
  all (== (multiplosPersistentes n))
      [multiplosPersistentes2 n,
       multiplosPersistentes3 n,
       multiplosPersistentes4 n]
 
-- La comprobación es
--    λ> all prop_multiplosPresistentes [1..6]
--    True
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (multiplosPersistentes 6)
--    32
--    (3.35 secs, 7,378,373,000 bytes)
--    λ> length (multiplosPersistentes2 6)
--    32
--    (0.12 secs, 171,735,992 bytes)
--    λ> length (multiplosPersistentes3 6)
--    32
--    (0.03 secs, 9,290,744 bytes)
--    λ> length (multiplosPersistentes4 6)
--    32
--    (0.01 secs, 294,584 bytes)
--
--    λ> length (multiplosPersistentes2 8)
--    128
--    (7.76 secs, 18,659,185,520 bytes)
--    λ> length (multiplosPersistentes3 8)
--    128
--    (0.73 secs, 1,007,383,168 bytes)
--    λ> length (multiplosPersistentes4 8)
--    128
--    (0.01 secs, 960,808 bytes)
--
--    λ> length (multiplosPersistentes3 9)
--    256
--    (6.82 secs, 10,517,232,576 bytes)
--    λ> length (multiplosPersistentes4 9)
--    256
--    (0.01 secs, 1,912,136 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>