Un número semiprimo es un número natural que es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque 26 = 2x13) y 49 también lo es (porque 49 = 7x7).

Definir las funciones

esSemiprimo :: Integer -> Bool
semiprimos  :: [Integer]

tales que + (esSemiprimo n) se verifica si n es semiprimo. Por ejemplo,

esSemiprimo 26          ==  True
esSemiprimo 49          ==  True
esSemiprimo 8           ==  False
esSemiprimo 2019        ==  True
esSemiprimo (21+10^14)  ==  True

• semiprimos es la sucesión de números semiprimos. Por ejemplo,

take 10 semiprimos   ==  [4,6,9,10,14,15,21,22,25,26]
semiprimos !! 579    ==  2019
semiprimos !! 10000  ==  40886

Leer más…

Un número malvado es un número natural cuya expresión en base 2 contiene un número par de unos. Por ejemplo, 6 es malvado porque su expresión en base 2 es 110 que tiene dos unos.

Definir las funciones

esMalvado       :: Integer -> Bool
malvados        :: [Integer]
posicionMalvada :: Integer -> Maybe Int

tales que + (esMalvado n) se verifica si n es un número malvado. Por ejemplo,

esMalvado 6              ==  True
esMalvado 7              ==  False
esMalvado 2019           ==  True
esMalvado (10^70000)     ==  True
esMalvado (10^(3*10^7))  ==  True

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

λ> take 20 malvados
[0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39]
malvados !! 1009    ==  2019
malvados !! 10      ==  20
malvados !! (10^2)  ==  201
malvados !! (10^3)  ==  2000
malvados !! (10^4)  ==  20001
malvados !! (10^5)  ==  200000
malvados !! (10^6)  ==  2000001

• (posicionMalvada n) es justo la posición de n en la sucesión de números malvados, si n es malvado o Nothing, en caso contrario. Por ejemplo,

posicionMalvada 6        ==  Just 3
posicionMalvada 2019     ==  Just 1009
posicionMalvada 2018     ==  Nothing
posicionMalvada 2000001  ==  Just 1000000
posicionMalvada (10^7)   ==  Just 5000000

Leer más…

Un número natural n es apocalíptico si 2^n contiene la secuencia 666. Por ejemplo, 157 es apocalíptico porque 2^157 es 182687704666362864775460604089535377456991567872 que contiene la secuencia 666.

Definir las funciones

esApocaliptico       :: Integer -> Bool
apocalipticos        :: [Integer]
posicionApocaliptica :: Integer -> Maybe Int

tales que

• (esApocaliptico n) se verifica si n es un número apocalíptico. Por ejemplo,

esApocaliptico 157   ==  True
esApocaliptico 2019  ==  True
esApocaliptico 2018  ==  False

• apocalipticos es la lista de los números apocalípticos. Por ejemplo,

take 9 apocalipticos  ==  [157,192,218,220,222,224,226,243,245]
apocalipticos !! 450  ==  2019

• (posicionApocalitica n) es justo la posición de n en la sucesión de números apocalípticos, si n es apocalíptico o Nothing, en caso contrario. Por ejemplo,

posicionApocaliptica 157   ==  Just 0
posicionApocaliptica 2019  ==  Just 450
posicionApocaliptica 2018  ==  Nothing

Leer más…

El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el teorema de Navidad de Fermat.

Definir las funciones

representaciones :: Integer -> [(Integer,Integer)]
primosImparesConRepresentacionUnica :: [Integer]
primos4nM1 :: [Integer]

tales que

• (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo.

representaciones  20           ==  [(2,4)]
representaciones  25           ==  [(0,5),(3,4)]
representaciones 325           ==  [(1,18),(6,17),(10,15)]
representaciones 100000147984  ==  [(0,316228)]
length (representaciones (10^10))    ==  6
length (representaciones (4*10^12))  ==  7

• primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo,

λ> take 20 primosImparesConRepresentacionUnica
[5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

• primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo,

λ> take 20 primos4nM1
[5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

Comprobar con QuickCheck el torema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.

Leer más…

Se dice que A es un subconjunto maximal de B si A ⊂ B y no existe ningún C tal que A ⊂ C y C ⊂ B. Por ejemplo, {2,5} es un subconjunto maximal de {2,3,5], pero {3] no lo es.

El árbol de los subconjuntos de un conjunto A es el árbol que tiene como raíz el conjunto A y cada nodo tiene como hijos sus subconjuntos maximales. Por ejemplo, el árbol de subconjuntos de [2,3,5] es

       [2, 3, 5]
       /   |  \
      /    |   \
     /     |    \
    /      |     \
   /       |      \
 [5,3]   [2,3]   [2,5]
 /  \    /  \    /  \
[3] [5] [3] [2] [5] [2]
 |   |   |   |   |   |
[ ] [ ] [ ] [ ] [ ] [ ]

Usando el tipo de dato

data Arbol = N Integer [Arbol]
  deriving (Eq, Show)

el árbol anterior se representa por

N [2,5,3]
  [N [5,3]
     [N [3]
        [N [] []],
      N [5]
        [N [] []]],
   N [2,3]
     [N [3]
        [N [] []],
      N [2]
        [N [] []]],
   N [2,5]
     [N [5]
        [N [] []],
      N [2]
        [N [] []]]]

Definir las funciones

arbolSubconjuntos :: [Int] -> Arbol
nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int

tales que

• (arbolSubconjuntos x) es el árbol de los subconjuntos de xs. Por ejemplo,

λ> arbolSubconjuntos [2,5,3]
N [2,5,3] [N [5,3] [N [3] [N [] []],N [5] [N [] []]],
           N [2,3] [N [3] [N [] []],N [2] [N [] []]],
           N [2,5] [N [5] [N [] []],N [2] [N [] []]]]

• (nOcurrenciasArbolSubconjuntos xs ys) es el número de veces que aparece el conjunto xs en el árbol de los subconjuntos de ys. Por ejemplo,

nOcurrenciasArbolSubconjuntos []      [2,5,3]  ==  6
nOcurrenciasArbolSubconjuntos [3]     [2,5,3]  ==  2
nOcurrenciasArbolSubconjuntos [3,5]   [2,5,3]  ==  1
nOcurrenciasArbolSubconjuntos [3,5,2] [2,5,3]  ==  1

Comprobar con QuickChek que, para todo entero positivo n, el número de ocurrencia de un subconjunto xs de [1..n] en el árbol de los subconjuntos de [1..n] es el factorial de n-k (donde k es el número de elementos de xs).

Leer más…

Para representar las operaciones binarias en un conjunto finito A con n elementos se pueden numerar sus elementos desde el 0 al n-1. Entonces cada operación binaria en A se puede ver como una lista de listas xss tal que el valor de aplicar la operación a los elementos i y j es el j-ésimo elemento del i-ésimo elemento de xss. Por ejemplo, si A = {0,1,2} entonces las tabla de la suma y de la resta módulo 3 en A son

0 1 2    0 2 1
1 2 0    1 0 2
2 0 1    2 1 0
Suma     Resta

Definir la función

conmutativa :: [[Int]] -> Bool

tal que (conmutativa xss) se verifica si la operación cuya tabla es xss es conmutativa. Por ejemplo,

conmutativa [[0,1,2],[1,0,1],[2,1,0]]  ==  True
conmutativa [[0,1,2],[1,0,0],[2,1,0]]  ==  False
conmutativa [[i+j `mod` 2000 | j <- [0..1999]] | i <- [0..1999]] == True
conmutativa [[i-j `mod` 2000 | j <- [0..1999]] | i <- [0..1999]] == False

Leer más…

Una partición de un conjunto es una división del mismo en subconjuntos disjuntos no vacíos.

Definir la función

esParticion :: Eq a => [[a]] -> Bool

tal que (esParticion xss) se verifica si xss es una partición; es decir sus elementos son listas no vacías disjuntas. Por ejemplo.

esParticion [[1,3],[2],[9,5,7]]  ==  True
esParticion [[1,3],[2],[9,5,1]]  ==  False
esParticion [[1,3],[],[9,5,7]]   ==  False
esParticion [[2,3,2],[4]]        ==  True

Leer más…

Para representar las operaciones binarias en un conjunto finito A con n elementos se pueden numerar sus elementos desde el 0 al n-1. Entonces cada operación binaria en A se puede ver como una lista de listas xss tal que el valor de aplicar la operación a los elementos i y j es el j-ésimo elemento del i-ésimo elemento de xss. Por ejemplo, si A = {0,1,2} entonces las tabla de la suma y de la resta módulo 3 en A son

0 1 2    0 2 1
1 2 0    1 0 2
2 0 1    2 1 0
Suma     Resta

Definir las funciones

tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
tablaSuma      :: Int -> [[Int]]
tablaResta     :: Int -> [[Int]]
tablaProducto  :: Int -> [[Int]]

tales que

• (tablaOperacion f n) es la tabla de la operación f módulo n en [0..n-1]. Por ejemplo,

tablaOperacion (+) 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
tablaOperacion (-) 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
tablaOperacion (-) 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]
tablaOperacion (\x y -> abs (x-y)) 3  ==  [[0,1,2],[1,0,1],[2,1,0]]

• (tablaSuma n) es la tabla de la suma módulo n en [0..n-1]. Por ejemplo,

tablaSuma 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
tablaSuma 4  ==  [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]]

• (tablaResta n) es la tabla de la resta módulo n en [0..n-1]. Por ejemplo,

tablaResta 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
tablaResta 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]

• (tablaProducto n) es la tabla del producto módulo n en [0..n-1]. Por ejemplo,

tablaProducto 3  ==  [[0,0,0],[0,1,2],[0,2,1]]
tablaProducto 4  ==  [[0,0,0,0],[0,1,2,3],[0,2,0,2],[0,3,2,1]]

Comprobar con QuickCheck, si parato entero positivo n de verificar las siguientes propiedades:

• La suma, módulo n, de todos los números de (tablaSuma n) es 0.
• La suma, módulo n, de todos los números de (tablaResta n) es 0.
• La suma, módulo n, de todos los números de (tablaProducto n) es n/2 si n es el doble de un número impar y es 0, en caso contrario.

Leer más…

Definir la función

nDivisoresCompuestos :: Integer -> Integer

tal que (nDivisoresCompuestos x) es el número de divisores de x que son compuestos (es decir, números mayores que 1 que no son primos). Por ejemplo,

nDivisoresCompuestos 30  ==  4
nDivisoresCompuestos (product [1..11])  ==  534
nDivisoresCompuestos (product [1..25])  ==  340022
length (show (nDivisoresCompuestos (product [1..3*10^4]))) == 1948

Leer más…

Definir la función

divisoresCompuestos :: Integer -> [Integer]

tal que (divisoresCompuestos x) es la lista de los divisores de x que son números compuestos (es decir, números mayores que 1 que no son primos). Por ejemplo,

divisoresCompuestos 30  ==  [6,10,15,30]
length (divisoresCompuestos (product [1..11]))  ==  534
length (divisoresCompuestos (product [1..14]))  ==  2585
length (divisoresCompuestos (product [1..16]))  ==  5369
length (divisoresCompuestos (product [1..25]))  ==  340022

Leer más…