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
1 2 |
esMultiploPersistente :: Integer -> Bool multiplosPersistentes :: Int -> [Integer] |
tales que
- (esMultiploPersistente n) se verifica si n es un múltiplo persistente de n. Por ejemplo,
1 2 |
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,
1 2 |
take 2 (multiplosPersistentes 4) == [7000,7007] length (multiplosPersistentes 20) == 524288 |
Usando la función multiplosPersistentes, calcular la respuesta al problema de la Olimpiada.
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
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>