Exercitium

Números en potencias de dos

PorJosé A. Alonso 20-enero-202127-enero-2021

Las potencias de dos son

   1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,...

1	1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,...

Se observa que la primera potencia de dos que contiene al 638 es la 14 ya que 2^14 = 16384.

Definir la función

   potenciasContenedoras :: Integer -> [Integer]

1	potenciasContenedoras :: Integer -> [Integer]

tal que (potenciasContenedoras x) es la lista de las potencias de 2 que contienen a x. Por ejemplo,

   λ> head (potenciasContenedoras 638)
   14
   λ> head (potenciasContenedoras 2021)
   452
   λ> take 20 (potenciasContenedoras 4)
   [2,6,10,11,12,14,18,19,20,22,25,26,27,28,30,31,32,33,34,35]
   λ> [head (potenciasContenedoras n) | n <- [0..20]]
   [10,4,1,5,2,8,4,15,3,12,10,40,7,17,18,21,4,27,30,13,11]

λ> head (potenciasContenedoras 638)

λ> head (potenciasContenedoras 2021)

452

λ> take 20 (potenciasContenedoras 4)

[2,6,10,11,12,14,18,19,20,22,25,26,27,28,30,31,32,33,34,35]

λ> [head (potenciasContenedoras n) | n <- [0..20]]

[10,4,1,5,2,8,4,15,3,12,10,40,7,17,18,21,4,27,30,13,11]

Comprobar con QuickCheck si todos los números naturales están contenenidos en alguna potencia de 2.

Soluciones

import Data.List (isInfixOf)
import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª solución
-- ===========

potenciasContenedoras :: Integer -> [Integer]
potenciasContenedoras x =
  [n | n <- [1..], x `estaContenidoEn` (2^n)]

-- (estaContenidoEn x y) se verifica si el número x está contenido en
-- y. Por ejemplo,
--    estaContenidoEn 23 42357  ==  True
--    estaContenidoEn 23 42537  ==  False
estaContenidoEn :: Integer -> Integer -> Bool
estaContenidoEn x y = show x `isInfixOf` show y

-- 2ª solución
-- ===========

potenciasContenedoras2 :: Integer -> [Integer]
potenciasContenedoras2 x =
  [n | (n,y) <- zip [0..] potenciasDeDos, x `estaContenidoEn` y]

-- potenciasDeDos es la lista de las potencias de dos. Por ejemplo,
--    λ> take 12 potenciasDeDos
--    [1,2,4,8,16,32,64,128,256,512,1024,2048]
potenciasDeDos :: [Integer]
potenciasDeDos = iterate (*2) 1

-- Propiedad
-- =========

-- La propiedad es
prop_potenciasContenedoras :: Integer -> Property
prop_potenciasContenedoras n =
  n > 0 ==> not (null (potenciasContenedoras n))

-- La comprobación es
--    λ> quickCheck prop_potenciasContenedoras
--    +++ OK, passed 100 tests.

import Data.List (isInfixOf)

import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª solución

-- ===========

potenciasContenedoras :: Integer -> [Integer]

potenciasContenedoras x =

[n | n <- [1..], x `estaContenidoEn` (2^n)]

-- (estaContenidoEn x y) se verifica si el número x está contenido en

-- y. Por ejemplo,

-- estaContenidoEn 23 42357 == True

-- estaContenidoEn 23 42537 == False

estaContenidoEn :: Integer -> Integer -> Bool

estaContenidoEn x y = show x `isInfixOf` show y

-- 2ª solución

-- ===========

potenciasContenedoras2 :: Integer -> [Integer]

potenciasContenedoras2 x =

[n | (n,y) <- zip [0..] potenciasDeDos, x `estaContenidoEn` y]

-- potenciasDeDos es la lista de las potencias de dos. Por ejemplo,

-- λ> take 12 potenciasDeDos

-- [1,2,4,8,16,32,64,128,256,512,1024,2048]

potenciasDeDos :: [Integer]

potenciasDeDos = iterate (*2) 1

-- Propiedad

-- =========

-- La propiedad es

prop_potenciasContenedoras :: Integer -> Property

prop_potenciasContenedoras n =

n > 0 ==> not (null (potenciasContenedoras n))

-- La comprobación es

-- λ> quickCheck prop_potenciasContenedoras

-- +++ OK, passed 100 tests.

Buenos primos

PorJosé A. Alonso 19-enero-202126-enero-2021

La sucesión de los números primos es

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ...

1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ...

Las parejas de primos equidistantes de 5 en dicha sucesión son (3, 7) y (2, 11). Se observa que el cuadrado de 5 es mayor que el producto de los elementos de dichas parejas; es decir,

   5^2 = 25 > 21 = 3 x 7
   5^2 = 25 > 22 = 2 x 11

1 2	5^2 = 25 > 21 = 3 x 7 5^2 = 25 > 22 = 2 x 11

En cambio, el 7 tiene una pareja de primos equidistantes (la (5, 11)) cuyo producto es mayor que el cuadrado de 7.

   7^2 = 49 < 55 = 5 x 11

1	7^2 = 49 < 55 = 5 x 11

Un buen primo es un número primo cuyo cuadrado es mayor que el producto de dos primos cualesquiera equidistantes de él en la sucesión de primos. Por ejemplo, 5 es un buen primo pero 7 no lo es.

Definir las funciones

   esBuenPrimo  :: Integer -> Bool
   buenosPrimos :: [Integer]

1 2	esBuenPrimo :: Integer -> Bool buenosPrimos :: [Integer]

tales que

(esBuenPrimo n) se verifica si n es un buen primo. Por ejemplo,

     esBuenPrimo 5        ==  True
     esBuenPrimo 7        ==  False
     esBuenPrimo 8746811  ==  True

esBuenPrimo 5 == True

esBuenPrimo 7 == False

esBuenPrimo 8746811 == True

buenosPrimos es la lista de los buenos primos. Por ejemplo,

     λ> take 12 buenosPrimos
     [2,5,11,17,29,37,41,53,59,67,71,97]

1 2	λ> take 12 buenosPrimos [2,5,11,17,29,37,41,53,59,67,71,97]

Comprobar con QuickCheck que la lista de los buenos primos es infinita; es decir, para cualquier entero positivo n existe un número mayor que n que es un buen primo.

Soluciones

import Data.Numbers.Primes (primes)
import Test.QuickCheck (Property, (==>), quickCheck)

esBuenPrimo :: Integer -> Bool
esBuenPrimo n =
  n == y && and [n^2 > x * y | (x, y) <- zip (reverse xs) ys]
  where (xs,y:ys) = span (< n) primes

buenosPrimos :: [Integer]
buenosPrimos = filter esBuenPrimo [2..]

-- La propiedad es
prop_buenosPrimos :: Integer -> Property
prop_buenosPrimos n =
  n > 0 ==> any esBuenPrimo [n+1..]

-- La comprobación es
--    λ> quickCheck prop_buenosPrimos
--    +++ OK, passed 100 tests.

import Data.Numbers.Primes (primes)

import Test.QuickCheck (Property, (==>), quickCheck)

esBuenPrimo :: Integer -> Bool

esBuenPrimo n =

n == y && and [n^2 > x * y | (x, y) <- zip (reverse xs) ys]

where (xs,y:ys) = span (< n) primes

buenosPrimos :: [Integer]

buenosPrimos = filter esBuenPrimo [2..]

-- La propiedad es

prop_buenosPrimos :: Integer -> Property

prop_buenosPrimos n =

n > 0 ==> any esBuenPrimo [n+1..]

-- La comprobación es

-- λ> quickCheck prop_buenosPrimos

-- +++ OK, passed 100 tests.

Números equidigitales

PorJosé A. Alonso 18-enero-202125-enero-2021

Un número equidigital es un número natural que tiene el mismo número de dígitos que el número de dígitos en su factorización prima, incluidos los exponentes mayores que 1. Por ejemplo,

10 es equidigital ya que tiene 2 dígitos al igual que su factorización prima (2 x 5).
25 es equidigital ya que tiene 2 dígitos al igual que su factorización prima (5^2).
121 es equidigital ya que tiene 3 dígitos al igual que su factorización prima (11^2).
175 es equidigital ya que tiene 3 dígitos al igual que su factorización prima (5^2 x 7).
1125 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (3^2 x 5^3).
2021 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (43 x 47).
3072 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (3 x 2^10).

Definir las funciones

   esEquidigital :: Int -> Bool
   equidigitales :: [Int]

1 2	esEquidigital :: Int -> Bool equidigitales :: [Int]

tal que

(esEquidigital x) se verifica si x es un número equidigital. Por ejemplo.

     esEquidigital 10    ==  True
     esEquidigital 11    ==  True
     esEquidigital 2021  ==  True
     esEquidigital 2022  ==  False

esEquidigital 10 == True

esEquidigital 11 == True

esEquidigital 2021 == True

esEquidigital 2022 == False

equidigitales es la lista de los números equidigitales. Por ejemplo,

     λ> take 20 equidigitales
     [2,3,5,7,10,11,13,14,15,16,17,19,21,23,25,27,29,31,32,35]
     λ> equidigitales !! 755
     2021
     λ> equidigitales !! 100000
     405341

λ> take 20 equidigitales

[2,3,5,7,10,11,13,14,15,16,17,19,21,23,25,27,29,31,32,35]

λ> equidigitales !! 755

2021

λ> equidigitales !! 100000

405341

Comprobar con QuickChek que el conjunto de los números equidigitales es infinito; es decir, para cada entero n existe un equidigital mayor que n.

Soluciones

import Data.Numbers.Primes
import Data.List
import Test.QuickCheck

esEquidigital :: Int -> Bool
esEquidigital x =
  nDigitos x == nDigitosFactorizacion x

-- (nDigitos n) es el número de dígitos de n. Por ejemplo,
--    nDigitos 2021  ==  4
nDigitos :: Int -> Int
nDigitos = length . show

-- (nDigitosFactorizacion x) es el número de dígitos en la factorización
-- prima de x, incluyendo los exponentes mayores que 1. Por ejemplo,
--    nDigitosFactorizacion 3000  ==  5
--    nDigitosFactorizacion 2021  ==  4
--    nDigitosFactorizacion 3072  ==  4
nDigitosFactorizacion :: Int -> Int
nDigitosFactorizacion x =
  sum [nDigitos y + aux n | (y,n) <- factorizacion x]
  where aux 1 = 0
        aux n = nDigitos n

-- (factorizacion x) es la factorización prima de x expresada como una
-- lista de pares que son las bases y los exponentes. Por ejemplo,
--    factorizacion 3000  ==  [(2,3),(3,1),(5,3)]
--    factorizacion 2021  ==  [(43,1),(47,1)]
--    factorizacion 3072  ==  [(2,10),(3,1)]
factorizacion :: Int -> [(Int,Int)]
factorizacion x =
  [(y, 1 + length ys) | (y:ys) <- group (primeFactors x)]

equidigitales :: [Int]
equidigitales = filter esEquidigital [1..]

-- La propiedad es
prop_equidigitales :: Int -> Property
prop_equidigitales n =
  n > 0 ==> any esEquidigital [n+1..]

-- La comprobación es
--    λ> quickCheck prop_equidigitales
--    +++ OK, passed 100 tests.

import Data.Numbers.Primes

import Data.List

import Test.QuickCheck

esEquidigital :: Int -> Bool

esEquidigital x =

nDigitos x == nDigitosFactorizacion x

-- (nDigitos n) es el número de dígitos de n. Por ejemplo,

-- nDigitos 2021 == 4

nDigitos :: Int -> Int

nDigitos = length . show

-- (nDigitosFactorizacion x) es el número de dígitos en la factorización

-- prima de x, incluyendo los exponentes mayores que 1. Por ejemplo,

-- nDigitosFactorizacion 3000 == 5

-- nDigitosFactorizacion 2021 == 4

-- nDigitosFactorizacion 3072 == 4

nDigitosFactorizacion :: Int -> Int

nDigitosFactorizacion x =

sum [nDigitos y + aux n | (y,n) <- factorizacion x]

where aux 1 = 0

aux n = nDigitos n

-- (factorizacion x) es la factorización prima de x expresada como una

-- lista de pares que son las bases y los exponentes. Por ejemplo,

-- factorizacion 3000 == [(2,3),(3,1),(5,3)]

-- factorizacion 2021 == [(43,1),(47,1)]

-- factorizacion 3072 == [(2,10),(3,1)]

factorizacion :: Int -> [(Int,Int)]

factorizacion x =

[(y, 1 + length ys) | (y:ys) <- group (primeFactors x)]

equidigitales :: [Int]

equidigitales = filter esEquidigital [1..]

-- La propiedad es

prop_equidigitales :: Int -> Property

prop_equidigitales n =

n > 0 ==> any esEquidigital [n+1..]

-- La comprobación es

-- λ> quickCheck prop_equidigitales

-- +++ OK, passed 100 tests.

Números compuestos persistentes

PorJosé A. Alonso 15-enero-202122-enero-2021

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]

1 2	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

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]

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

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.

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.

Números bigenerados

PorJosé A. Alonso 14-enero-202121-enero-2021

Se dice que y es un generador de x si x es igual a la suma de y los dígitos de y. Por ejemplo, 1996 y 2014 son generadores de 2021 ya que

   2021 = 1996 + 1 + 9 + 9 + 6
   2021 = 2014 + 2 + 0 + 1 + 4

1 2	2021 = 1996 + 1 + 9 + 9 + 6 2021 = 2014 + 2 + 0 + 1 + 4

Un número bigenerado es un número que tiene exactamente 2 generadores. Por ejemplo,

2021 es un número bigenerados y sus generadores son 1996 y 2014
20 no es bigenerador porque no tiene ningún generador
21 no es bigenerador porque tiene sólo un generador (el 15).
101 es el menor número bigenerado ysus generadores son 91 y 100.

Definir las funciones

   esBigenerado :: Integer -> Bool
   bigenerados  :: [Integer]

1 2	esBigenerado :: Integer -> Bool bigenerados :: [Integer]

tales que

(esBigenerado x) se verifica si x es bigenerado. Por ejemplo,

     esBigenerado 2021  ==  True
     esBigenerado 20    ==  False
     esBigenerado 21    ==  False
     esBigenerado 101   ==  True

esBigenerado 2021 == True

esBigenerado 20 == False

esBigenerado 21 == False

esBigenerado 101 == True

bigenerados es la lista de los números bigenerados. Por ejemplo,

     λ> take 12 bigenerados
     [101,103,105,107,109,111,113,115,117,202,204,206]

1 2	λ> take 12 bigenerados [101,103,105,107,109,111,113,115,117,202,204,206]

Comprobar con QuickCheck que la lista de los números bigenerados es infinita; es decir, para cualquier número positivo n existe un y mayor que x que es bigenerado.

Soluciones

import Test.QuickCheck (Property, (==>), quickCheck)

esBigenerado :: Integer -> Bool
esBigenerado x = length (generadores x) == 2

-- (generadores x) es la lista de los generadores de x. Por ejemplo,
--    generadores 2021  ==  [1996,2014]
--    generadores 20    ==  []
--    generadores 21    ==  [15]
--    generadores 101   ==  [91,100]
generadores :: Integer -> [Integer]
generadores x = filter (esGenerador x) [1..x]

-- (esGenerador x y) se verifica si y es un generador de x. Por ejemplo,
--    esGenerador 818 796  ==  True
--    esGenerador 818 805  ==  True
esGenerador :: Integer -> Integer -> Bool
esGenerador x y = x == y + sumaDigitos y

-- (sumaDigitos n) es la suma de los dígitos de n. Por ejemplo,
--    sumaDigitos 2021  ==  5
sumaDigitos :: Integer -> Integer
sumaDigitos = sum . digitos

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 2021  ==  [2,0,2,1]
digitos :: Integer -> [Integer]
digitos x = [read [c] | c <- show x]

bigenerados :: [Integer]
bigenerados = filter esBigenerado [1..]

-- La propiedad es
prop_bigenerados :: Integer -> Property
prop_bigenerados n =
  n >= 0 ==> any esBigenerado [n+1..]

-- La comprobación es
--    λ> quickCheck prop_bigenerados
--    +++ OK, passed 100 tests.

import Test.QuickCheck (Property, (==>), quickCheck)

esBigenerado :: Integer -> Bool

esBigenerado x = length (generadores x) == 2

-- (generadores x) es la lista de los generadores de x. Por ejemplo,

-- generadores 2021 == [1996,2014]

-- generadores 20 == []

-- generadores 21 == [15]

-- generadores 101 == [91,100]

generadores :: Integer -> [Integer]

generadores x = filter (esGenerador x) [1..x]

-- (esGenerador x y) se verifica si y es un generador de x. Por ejemplo,

-- esGenerador 818 796 == True

-- esGenerador 818 805 == True

esGenerador :: Integer -> Integer -> Bool

esGenerador x y = x == y + sumaDigitos y

-- (sumaDigitos n) es la suma de los dígitos de n. Por ejemplo,

-- sumaDigitos 2021 == 5

sumaDigitos :: Integer -> Integer

sumaDigitos = sum . digitos

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 2021 == [2,0,2,1]

digitos :: Integer -> [Integer]

digitos x = [read [c] | c <- show x]

bigenerados :: [Integer]

bigenerados = filter esBigenerado [1..]

-- La propiedad es

prop_bigenerados :: Integer -> Property

prop_bigenerados n =

n >= 0 ==> any esBigenerado [n+1..]

-- La comprobación es

-- λ> quickCheck prop_bigenerados

-- +++ OK, passed 100 tests.

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>

Números en potencias de dos

Soluciones

Buenos primos

Soluciones

Números equidigitales

Soluciones

Números compuestos persistentes

Soluciones

Números bigenerados

Soluciones

Nuevas soluciones

Entradas recientes

Buscar

Correo electrónico