Números compuestos persistentes
Un número compuesto persistente es un número compuesto que no se puede transformar en un número primo cambiando sólo uno de sus dígitos. Por ejemplo,
- 20 no es un compuesto persistente porque cambiando su último dígito por un 3 se transforma en 23 que es primo.
- 25 no es un compuesto persistente porque cambiando su primer dígito por un 0 se transforma en 5 que es primo.
- 200 es un compuesto persistente ya que al cambiar su útimo dígito por un impar se obtienen los números 201, 203, 207, 205 y 209 que no son primos y todos sus demás transformados son pares y, por tanto, tampoco son primos.
Definir las funciones
1 2 |
esCompuestoPersistente :: Integer -> Bool compuestosPersistentes :: [Integer] |
tales que
- (esCompuestoPersistente n) se verifica si n es un número compuesto persistente. Por ejemplo,
1 2 3 |
esCompuestoPersistente 20 == False esCompuestoPersistente 200 == True esCompuestoPersistente 2021 == False |
- compuestosPersistentes es la lista de los números compuestos persistentes. Por ejemplo,
1 2 |
λ> take 10 compuestoPersistentes [200,204,206,208,320,322,324,325,326,328] |
Comprobar con QuickCheck que todos los números de la forma 510+2310*k son números compuestos persistentes.
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 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 |
import Data.Numbers.Primes (isPrime, primes) import Test.QuickCheck (Property, (==>), quickCheck) -- 1ª solución -- =========== esCompuestoPersistente :: Integer -> Bool esCompuestoPersistente n = esCompuesto n && all (not . isPrime) (transformados n) -- (eCompuesto n) se verifica si n es un número compuesto. Por ejemplo, -- esCompuesto 15 == True -- esCompuesto 16 == True -- esCompuesto 17 == False esCompuesto :: Integer -> Bool esCompuesto n = n > 1 && not (isPrime n) -- (transformados n) es la lista delos números obtenidos modificando uno -- de los dígitos de n. Por ejemplo, -- λ> transformados 27 -- [7,17,37,47,57,67,77,87,97,20,21,22,23,24,25,26,28,29] transformados :: Integer -> [Integer] transformados n = map read (aux (show n)) where aux [] = [] aux [x] = [[y] | y <- ['0'..'9'], y /= x] aux (x:xs) = [y:xs | y <- ['0'..'9'], y /= x] ++ [x:ys | ys <- aux xs] compuestosPersistentes :: [Integer] compuestosPersistentes = filter esCompuestoPersistente [1..] -- 2ª solución -- =========== esCompuestoPersistente2 :: Integer -> Bool esCompuestoPersistente2 n = not (any (esTransformadoDe n) (takeWhile (<=10^m-1) primes)) where m = length (show n) -- (esTransformadoDe m n) se verifica si n se puede obtener modificando uno -- de los dígitos de n. Por ejemplo, -- esTransformadoDe 27 47 == True -- esTransformadoDe 27 25 == True -- esTransformadoDe 27 45 == False -- esTransformadoDe 27 7 == True -- esTransformadoDe 27 2 == False esTransformadoDe :: Integer -> Integer -> Bool esTransformadoDe m n = 1 == length (filter (==False) (zipWith (==) xs zs)) where xs = show m ys = show n zs = replicate (length xs - length ys) '0' ++ ys compuestosPersistentes2 :: [Integer] compuestosPersistentes2 = filter esCompuestoPersistente2 [1..] -- 3ª solución -- =========== esCompuestoPersistente3 :: Integer -> Bool esCompuestoPersistente3 n = null (primosTransformados n) -- (primosTransformados n) es la lista de los números primos que se -- puede obtener modificando uno de los dígitos de n. Por ejemplo, -- primosTransformados 27 == [17,23,29,37,47,67,97,7] -- primosTransformados 26 == [23,29] -- primosTransformados 200 == [] -- primosTransformados 202 == [2] primosTransformados :: Integer -> [Integer] primosTransformados n = [x | x <- primosNdigitos p, difierenEnUnaPosicion n x] ++ [x | x <- [read ('0' : tail ns)], isPrime x] where ns = show n p = length ns -- (difierenEnUnaPosicion m n) se verifica si los números m y n difieren -- en una posición (suponiendo que m y n tienen el mismo número de -- dígitos). Por ejemplo, -- difierenEnUnaPosicion 325 375 == True -- difierenEnUnaPosicion 325 357 == False difierenEnUnaPosicion :: Integer -> Integer -> Bool difierenEnUnaPosicion m n = 1 == length (filter (==False) (zipWith (==) (show m) (show n))) -- (primosNdigitos n) es la lista de los primos con n dígitos. Por -- ejemplo, -- λ> primosNdigitos 2 -- [11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] primosNdigitos :: Int -> [Integer] primosNdigitos n = takeWhile (<=10^n-1) (dropWhile (<=10^(n-1)) primes) compuestosPersistentes3 :: [Integer] compuestosPersistentes3 = filter esCompuestoPersistente3 [1..] -- 4ª solución -- =========== esCompuestoPersistente4 :: Integer -> Bool esCompuestoPersistente4 n = null (primosTransformados2 n) -- (primosTransformados2 n) es la lista de los números primos que se -- puede obtener modificando uno de los dígitos de n. Por ejemplo, -- primosTransformados2 27 == [17,23,29,37,47,67,97,7] -- primosTransformados2 26 == [23,29] -- primosTransformados2 200 == [] -- primosTransformados2 202 == [2] primosTransformados2 :: Integer -> [Integer] primosTransformados2 n = [x | x <- primosEntre (menorTransformado n) (mayorTransformado n) , difierenEnUnaPosicion n x] ++ [x | x <- [read ('0' : tail ns)], isPrime x] where ns = show n p = length ns -- (primosEntre x y) lista de números prios mayores o iguales que x y -- menores o iguales que y. Por ejemplo, -- primosEntre 11 41 == [11,13,17,19,23,29,31,37,41] primosEntre ::Integer -> Integer -> [Integer] primosEntre x y = takeWhile (<= y) (dropWhile (< x) primes) -- (menorTransformado x) es el menor número, con la misma cantidad de -- dígitos que x, que se puede obtener modificando uno de los dígitos de -- n. Por ejemplo, -- menorTransformado 375 == 175 -- menorTransformado 14 == 11 -- menorTransformado 4 == 1 -- menorTransformado 1145 == 1115 menorTransformado :: Integer -> Integer menorTransformado x | x <= 9 = 1 | y > '1' = read ('1' : ys) | otherwise = read ('1' : show (menorTransformado (read ys))) where (y:ys) = show x -- (mayorTransformado x) es el mayor número, con la misma cantidad de -- dígitos que x, que se puede obtener modificando uno de los dígitos de -- n. Por ejemplo, -- mayorTransformado 375 == 975 -- mayorTransformado 93 == 99 -- mayorTransformado 4 == 9 -- mayorTransformado 9945 == 9995 mayorTransformado :: Integer -> Integer mayorTransformado x | x <= 9 = 9 | y < '9' = read ('9' : ys) | otherwise = read ('9' : show (mayorTransformado (read ys))) where (y:ys) = show x compuestosPersistentes4 :: [Integer] compuestosPersistentes4 = filter esCompuestoPersistente4 [1..] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> compuestosPersistentes !! 1000 -- 8180 -- (0.54 secs, 1,577,628,232 bytes) -- λ> compuestosPersistentes2 !! 1000 -- 8180 -- (10.13 secs, 15,883,929,392 bytes) -- λ> compuestosPersistentes3 !! 1000 -- 8180 -- (7.09 secs, 14,165,470,304 bytes) -- λ> compuestosPersistentes4 !! 1000 -- 8180 -- (6.54 secs, 13,332,608,480 bytes) -- Propiedad -- ========= -- La propiedad es prop_compuestosPersistentes :: Integer -> Property prop_compuestosPersistentes k = k > 0 ==> esCompuestoPersistente (510 + 2310 * k) -- La comprobación de la propiedad es -- λ> quickCheck prop_compuestosPersistentes -- +++ OK, passed 100 tests. |