Ir al contenido principal

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

esCompuestoPersistente :: Integer -> Bool
compuestosPersistentes :: [Integer]

tales que

  • (esCompuestoPersistente n) se verifica si n es un número compuesto persistente. Por ejemplo,
esCompuestoPersistente 20    ==  False
esCompuestoPersistente 200   ==  True
esCompuestoPersistente 2021  ==  False
  • compuestosPersistentes es la lista de los números compuestos persistentes. Por ejemplo,
λ> 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

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.