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. |
José A. Alonso