enero 2021 – Página 3

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 cíclicos

PorJosé A. Alonso 13-enero-202120-enero-2021

La indicatriz de Euler (también llamada función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo,

φ(15) = 8 ya que los números menores o iguales a 36 y coprimos con 36 son ocho: 1, 2, 4, 7, 8, 11, 13 y 14.
φ(21) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 y 20.

Un número n es un número cíclico si n y φ(n) no tiene ningún divisor primo común. Por ejemplo, el número 15 es cíclico ya que 15 y 8 (que es φ(15)) no tiene ningún divisor primo común; en cambio, el número 21 no es cíclico ya 21 y 12 (que es φ(21)) son divisibles por 3.

Definir las funciones

   esCiclico :: Integer -> Bool
   ciclicos  :: [Integer]

1 2	esCiclico :: Integer -> Bool ciclicos :: [Integer]

tales que

(esCiclico n) se verifica si n es un número cíclico. Por ejemplo,

     esCiclico 15    ==  True
     esCiclico 16    ==  False
     esCiclico 2021  ==  True
     esCiclico (product [1..10^4])  ==  False

esCiclico 15 == True

esCiclico 16 == False

esCiclico 2021 == True

esCiclico (product [1..10^4]) == False

ciclicos es la lista de los números cíclicos. Por ejemplo,

     λ> take 20 ciclicos
     [2,3,5,7,11,13,15,17,19,23,29,31,33,35,37,41,43,47,51,53]
     λ> ciclicos !! (10^5)
     336059

λ> take 20 ciclicos

[2,3,5,7,11,13,15,17,19,23,29,31,33,35,37,41,43,47,51,53]

λ> ciclicos !! (10^5)

336059

Comprobar con QuickCheck que todos los números primos mayores que 2 son cíclicos.

Soluciones

module Numeros_ciclicos where

import Data.List (genericLength, group)
import Data.Numbers.Primes (primeFactors, primes)
import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª definición
-- =============

ciclicos1 :: [Integer]
ciclicos1 = filter esCiclico1 [2..]

esCiclico1 :: Integer -> Bool
esCiclico1 n = gcd n (phi1 n) == 1

-- (phi1 n) es igual a φ(n). Por ejemplo,
--    phi1 15    ==  8
--    phi1 21    ==  12
--    phi1 2021  ==  1932
phi1 :: Integer -> Integer
phi1 n = genericLength [x | x <- [1..n], gcd x n == 1]

-- 2ª definición
-- =============

ciclicos2 :: [Integer]
ciclicos2 = filter esCiclico2 [2..]

esCiclico2 :: Integer -> Bool
esCiclico2 n = gcd n (phi2 n) == 1

-- (phi2 n) es igual a φ(n). Por ejemplo,
--    phi2 15    ==  8
--    phi2 21    ==  12
--    phi2 2021  ==  1932
phi2 :: Integer -> Integer
phi2 n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n]

-- (factorizacion n) es la descomposición de n en factores primos como
-- una lista de pares donde los primeros elementos son la base y los
-- segundo son los exponentes. Por ejemplo,
--    factorizacion 3000  ==  [(2,3),(3,1),(5,3)]
-- ya que 3000 = 2^3*3*5^3
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  [(head xs,genericLength xs) | xs <- group (primeFactors n)]

-- 3ª definición
-- =============

ciclicos3 :: [Integer]
ciclicos3 = filter esCiclico3 [2..]

esCiclico3 :: Integer -> Bool
esCiclico3 n = gcd n (phi3 n) == 1

-- (phi3 n) es igual a φ(n). Por ejemplo,
--    phi3 15    ==  8
--    phi3 21    ==  12
--    phi3 2021  ==  1932
phi3 :: Integer -> Integer
phi3 n =
  product [(x-1) * product xs | (x:xs) <- group (primeFactors n)]

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> esCiclico1 (4*10^6)
--    False
--    (3.64 secs, 4,448,223,616 bytes)
--    λ> esCiclico2 (4*10^6)
--    False
--    (0.01 secs, 116,144 bytes)
--    λ> esCiclico3 (4*10^6)
--    False
--    (0.01 secs, 111,336 bytes)
--
--    λ> esCiclico2 (product [1..3*10^4])
--    False
--    (2.49 secs, 5,846,361,904 bytes)
--    λ> esCiclico3 (product [1..3*10^4])
--    False
--    (2.50 secs, 5,947,164,552 bytes)


-- Verificación de la propiedad
-- ============================

-- La propiedad es
prop_ciclicos :: Int -> Property
prop_ciclicos n =
    n > 1 ==> esCiclico3 (primes !! n)

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

verificacion :: IO ()
verificacion = quickCheck prop_ciclicos

100

module Numeros_ciclicos where

import Data.List (genericLength, group)

import Data.Numbers.Primes (primeFactors, primes)

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

-- 1ª definición

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

ciclicos1 :: [Integer]

ciclicos1 = filter esCiclico1 [2..]

esCiclico1 :: Integer -> Bool

esCiclico1 n = gcd n (phi1 n) == 1

-- (phi1 n) es igual a φ(n). Por ejemplo,

-- phi1 15 == 8

-- phi1 21 == 12

-- phi1 2021 == 1932

phi1 :: Integer -> Integer

phi1 n = genericLength [x | x <- [1..n], gcd x n == 1]

-- 2ª definición

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

ciclicos2 :: [Integer]

ciclicos2 = filter esCiclico2 [2..]

esCiclico2 :: Integer -> Bool

esCiclico2 n = gcd n (phi2 n) == 1

-- (phi2 n) es igual a φ(n). Por ejemplo,

-- phi2 15 == 8

-- phi2 21 == 12

-- phi2 2021 == 1932

phi2 :: Integer -> Integer

phi2 n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n]

-- (factorizacion n) es la descomposición de n en factores primos como

-- una lista de pares donde los primeros elementos son la base y los

-- segundo son los exponentes. Por ejemplo,

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

-- ya que 3000 = 2^3*3*5^3

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

factorizacion n =

[(head xs,genericLength xs) | xs <- group (primeFactors n)]

-- 3ª definición

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

ciclicos3 :: [Integer]

ciclicos3 = filter esCiclico3 [2..]

esCiclico3 :: Integer -> Bool

esCiclico3 n = gcd n (phi3 n) == 1

-- (phi3 n) es igual a φ(n). Por ejemplo,

-- phi3 15 == 8

-- phi3 21 == 12

-- phi3 2021 == 1932

phi3 :: Integer -> Integer

phi3 n =

product [(x-1) * product xs | (x:xs) <- group (primeFactors n)]

-- Comparación de eficiencia

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

-- La comparación es

-- λ> esCiclico1 (4*10^6)

-- False

-- (3.64 secs, 4,448,223,616 bytes)

-- λ> esCiclico2 (4*10^6)

-- False

-- (0.01 secs, 116,144 bytes)

-- λ> esCiclico3 (4*10^6)

-- False

-- (0.01 secs, 111,336 bytes)

-- λ> esCiclico2 (product [1..3*10^4])

-- False

-- (2.49 secs, 5,846,361,904 bytes)

-- λ> esCiclico3 (product [1..3*10^4])

-- False

-- (2.50 secs, 5,947,164,552 bytes)

-- Verificación de la propiedad

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

-- La propiedad es

prop_ciclicos :: Int -> Property

prop_ciclicos n =

n > 1 ==> esCiclico3 (primes !! n)

-- La comprobación es

-- λ> quickCheck prop_ciclicos

-- +++ OK, passed 100 tests.

verificacion :: IO ()

verificacion = quickCheck prop_ciclicos

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 duffinianos

PorJosé A. Alonso 12-enero-202119-enero-2021

Los números duffinianos, llamados así por Richard Duffy, son los números compuestos n que son coprimos con la suma de sus divisores; es decir, n y la suma de los divisores de n no tienen ningún factor primo común.

Por ejemplo, 35 es un número duffiniano ya que la suma de sus divisores es 1 + 5 + 7 + 35 = 48 que es coprimo con 35.

Definir las funciones

   esDuffiniano :: Integer -> Bool
   duffinianos :: [Integer]

1 2	esDuffiniano :: Integer -> Bool duffinianos :: [Integer]

tales que

(esDuffiniano n) se verifica si n es duffiniano. Por ejemplo,

     esDuffiniano 35    ==  True
     esDuffiniano 2021  ==  True
     esDuffiniano 11    ==  False
     esDuffiniano 12    ==  False
     esDuffiniano (product [1..2*10^4])  ==  False

esDuffiniano 35 == True

esDuffiniano 2021 == True

esDuffiniano 11 == False

esDuffiniano 12 == False

esDuffiniano (product [1..2*10^4]) == False

duffinianos es la sucesión de los números duffinianos. Por ejemplo,

     take 12 duffinianos  ==  [4,8,9,16,21,25,27,32,35,36,39,49]
     length (takeWhile (< 10^5) duffinianos)  ==  24434

1 2	take 12 duffinianos == [4,8,9,16,21,25,27,32,35,36,39,49] length (takeWhile (< 10^5) duffinianos) == 24434

Comprobar con QuickCheck que los números de la forma p^k, con p un primo mayor que 2 y k un entero mayor que 1, son duffinianos.

Soluciones

import Data.List (genericLength, group)
import Data.Numbers.Primes (isPrime, primeFactors, primes)
import Test.QuickCheck (Property, (==>), quickCheck)

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

duffinianos :: [Integer]
duffinianos = filter esDuffiniano [1..]

esDuffiniano :: Integer -> Bool
esDuffiniano n =
  n > 1 &&
  not (isPrime n) &&
  gcd n (sumaDivisores n) == 1

-- (sumaDivisores n) es la suma de los divisores de n. Por ejemplo.
--      sumaDivisores 35  ==  48
sumaDivisores :: Integer -> Integer
sumaDivisores = sum . divisores

-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--      divisores 35  ==  [1,5,7,35]
divisores :: Integer -> [Integer]
divisores n = [x | x <- [1..n]
                 , n `mod` x == 0]

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

duffinianos2 :: [Integer]
duffinianos2 = filter esDuffiniano2 [1..]

esDuffiniano2 :: Integer -> Bool
esDuffiniano2 n =
  n > 1 &&
  not (isPrime n) &&
  gcd n (sumaDivisores2 n) == 1

-- Si la descomposición de x en factores primos es
--    x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)
-- entonces la suma de los divisores de x es
--    p(1)^(e(1)+1) - 1     p(2)^(e(2)+1) - 1       p(n)^(e(2)+1) - 1
--   ------------------- . ------------------- ... -------------------
--        p(1)-1                p(2)-1                  p(n)-1
-- Ver la demostración en http://bit.ly/2zUXZPc

-- (sumaDivisores2 n) es la suma de los divisores de n. Por ejemplo.
--      sumaDivisores2 35  ==  48
sumaDivisores2 :: Integer -> Integer
sumaDivisores2 x =
  product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x]

-- (factorizacion x) es la lista de las bases y exponentes de la
-- descomposición prima de x. Por ejemplo,
--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion = map primeroYlongitud . group . primeFactors

-- (primeroYlongitud xs) es el par formado por el primer elemento de xs
-- y la longitud de xs. Por ejemplo,
--    primeroYlongitud [3,2,5,7] == (3,4)
primeroYlongitud :: [a] -> (a,Integer)
primeroYlongitud (x:xs) = (x, 1 + genericLength xs)
primeroYlongitud _      = error "No tiene elementos"

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> esDuffiniano (product [1..11])
--    False
--    (14.09 secs, 7,983,535,608 bytes)
--    λ> esDuffiniano2 (product [1..11])
--    False
--    (0.01 secs, 125,760 bytes)
--
--    λ> head (dropWhile (<10^4) duffinianos)
--    10000
--    (13.45 secs, 8,872,967,976 bytes)
--    λ> head (dropWhile (<10^4) duffinianos2)
--    10000
--    (0.15 secs, 280,668,240 bytes)
--
--    λ> length (takeWhile (<10^4) duffinianos)
--    2370
--    (13.43 secs, 8,966,138,016 bytes)
--    λ> length (takeWhile (<10^4) duffinianos2)
--    2370
--    (0.15 secs, 286,120,048 bytes)

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

-- La propiedad es
prop_duffinianos :: Int -> Int -> Property
prop_duffinianos n k =
  n >= 0 && k > 1 ==> esDuffiniano2 (p^k)
  where p = primes !! n

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

100

101

102

103

import Data.List (genericLength, group)

import Data.Numbers.Primes (isPrime, primeFactors, primes)

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

-- 1ª solución

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

duffinianos :: [Integer]

duffinianos = filter esDuffiniano [1..]

esDuffiniano :: Integer -> Bool

esDuffiniano n =

n > 1 &&

not (isPrime n) &&

gcd n (sumaDivisores n) == 1

-- (sumaDivisores n) es la suma de los divisores de n. Por ejemplo.

-- sumaDivisores 35 == 48

sumaDivisores :: Integer -> Integer

sumaDivisores = sum . divisores

-- (divisores n) es la lista de los divisores de n. Por ejemplo,

-- divisores 35 == [1,5,7,35]

divisores :: Integer -> [Integer]

divisores n = [x | x <- [1..n]

, n `mod` x == 0]

-- 2ª solución

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

duffinianos2 :: [Integer]

duffinianos2 = filter esDuffiniano2 [1..]

esDuffiniano2 :: Integer -> Bool

esDuffiniano2 n =

n > 1 &&

not (isPrime n) &&

gcd n (sumaDivisores2 n) == 1

-- Si la descomposición de x en factores primos es

-- x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)

-- entonces la suma de los divisores de x es

-- p(1)^(e(1)+1) - 1 p(2)^(e(2)+1) - 1 p(n)^(e(2)+1) - 1

-- ------------------- . ------------------- ... -------------------

-- p(1)-1 p(2)-1 p(n)-1

-- Ver la demostración en http://bit.ly/2zUXZPc

-- (sumaDivisores2 n) es la suma de los divisores de n. Por ejemplo.

-- sumaDivisores2 35 == 48

sumaDivisores2 :: Integer -> Integer

sumaDivisores2 x =

product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x]

-- (factorizacion x) es la lista de las bases y exponentes de la

-- descomposición prima de x. Por ejemplo,

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

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

factorizacion = map primeroYlongitud . group . primeFactors

-- (primeroYlongitud xs) es el par formado por el primer elemento de xs

-- y la longitud de xs. Por ejemplo,

-- primeroYlongitud [3,2,5,7] == (3,4)

primeroYlongitud :: [a] -> (a,Integer)

primeroYlongitud (x:xs) = (x, 1 + genericLength xs)

primeroYlongitud _ = error "No tiene elementos"

-- Comparación de eficiencia

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

-- La comparación es

-- λ> esDuffiniano (product [1..11])

-- False

-- (14.09 secs, 7,983,535,608 bytes)

-- λ> esDuffiniano2 (product [1..11])

-- False

-- (0.01 secs, 125,760 bytes)

-- λ> head (dropWhile (<10^4) duffinianos)

-- 10000

-- (13.45 secs, 8,872,967,976 bytes)

-- λ> head (dropWhile (<10^4) duffinianos2)

-- 10000

-- (0.15 secs, 280,668,240 bytes)

-- λ> length (takeWhile (<10^4) duffinianos)

-- 2370

-- (13.43 secs, 8,966,138,016 bytes)

-- λ> length (takeWhile (<10^4) duffinianos2)

-- 2370

-- (0.15 secs, 286,120,048 bytes)

-- Propiedad

-- =========

-- La propiedad es

prop_duffinianos :: Int -> Int -> Property

prop_duffinianos n k =

n >= 0 && k > 1 ==> esDuffiniano2 (p^k)

where p = primes !! n

-- La comprobación es

-- λ> quickCheck prop_duffinianos

-- +++ 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>

Meses: enero 2021

Números compuestos persistentes

Soluciones

Números bigenerados

Soluciones

Nuevas soluciones

Números cíclicos

Soluciones

Nuevas soluciones

Números duffinianos

Soluciones

Nuevas soluciones

Entradas recientes

Buscar

Correo electrónico