Nota: En este ejercicio usaremos las mismas notaciones que en el anterior importando el módulo Evaluacion_de_FNC.

Definir las siguientes funciones

atomosClausula :: Clausula -> [Atomo]
atomosFNC      :: FNC -> [Atomo]

tales que

• (atomosClausula c) es el conjunto de los átomos de la cláusula c. Por ejemplo,

atomosClausula [3,1,-3] == [1,3]

• (atomosFNC f) es el conjunto de los átomos de la FNC f. Por ejemplo,

atomosFNC [[4,5],[1,-2],[-4,-1,-5]]  ==  [1,2,4,5]

Nota: Escribir la solución en el módulo Atomos_de_FNC para poderlo usar en los siguientes ejercicios.

Leer más…

Una FNC (fórmula en forma normal conjuntiva) es una conjunción de cláusulas, donde una cláusula es una disyunción de literales y un literal es un átomo o su negación. Por ejemplo,

(x(1) v -x(3)) & x(2) & (-x(2) v x(3) v x(1))

es una FNC con tres clásulas tales que la primera cláusula tiene 2 literales (x(1) y -x(3)), la segunda tiene 1 (x(2)) y la tercera tiene 3 (-x(2), x(3) y x(1)).

Usaremos las siguientes representaciones:

• Los átomos se representan por enteros positivos. Por ejemplo, 3 representa x(3).
• Los literales se representan por enteros. Por ejemplo, 3 representa el literal positivo x(3) y -5 el literal negativo -x(5).
• Una cláusula es una lista de literales que representa la disyunción se sus literales. Por ejemplo, [3,2,-4] representa a (x(3) v x(2) v -x(4)).
• Una fórmula en forma normal conjuntiva (FNC) es una lista de cláusulas que representa la conjunción de sus cláusulas. Por ejemplo, [[3,2],[-1,2,5]] representa a ((x(3) v x(2)) & (-x(1) v x(2) v x(5))).

Una interpretación I es un conjunto de átomos. Se supone que los átomos de I son verdaderos y los restantes son falsos. Por ejemplo, en la interpretación [2,5]

• el literal x(2) es verdadero (porque 2 ∈ [2,5])
• el literal x(3) es falso (porque 3 ∉ [2,5])
• el literal -x(4) es verdadero (porque 4 ∉ [2,5])
• la cláusula (x(2) v x(3)) es verdadera (porque x(2) es verdadero)
• la cláusula (x(3) v x(4)) es falsa (porque x(3) y x(4) son falsos)
• la FNC ((x(2) v x(5)) & (-x(4) v x(3)) es verdadera porque lo son sus dos cláusulas

En el ejercicio se usarán los siguientes tipos de datos

type Atomo          = Int
type Literal        = Int
type Clausula       = [Literal]
type FNC            = [Clausula]
type Interpretacion = [Atomo]

Definir las siguientes funciones

valorLiteral  :: Interpretacion -> Literal -> Bool
valorClausula :: Interpretacion -> Clausula -> Bool
valor         :: Interpretacion -> FNC -> Bool

tales que

• (valorLiteral i l) es el valor del literal l en la interpretación i. Por ejemplo,

valorLiteral [3,5] 3     ==  True
valorLiteral [3,5] 4     ==  False
valorLiteral [3,5] (-3)  ==  False
valorLiteral [3,5] (-4)  ==  True

• (valorClausula i c) es el valor de la cláusula c en la interpretación i. Por ejemplo,

valorClausula [3,5] [2,3,-5]  ==  True
valorClausula [3,5] [2,4,-1]  ==  True
valorClausula [3,5] [2,4,1]   ==  False

• (valor i f) es el valor de la fórmula en FNC f en la interpretación i. Por ejemplo,

valor [1,3] [[1,-2],[3]]  ==  True
valor [1]   [[1,-2],[3]]  ==  False
valor [1]   []            ==  True

Nota: Escribir la solución en el módulo Evaluacion_de_FNC para poderlo usar en los siguientes ejercicios.

Leer más…

La conjetura de Lemoine afirma que

Todos los números impares mayores que 5 se pueden escribir de la forma p + 2q donde p y q son números primos. Por ejemplo, 47 = 13 + 2 x 17

Definir las funciones

descomposicionesLemoine :: Integer -> [(Integer,Integer)]
graficaLemoine :: Integer -> IO ()

tales que

• (descomposicionesLemoine n) es la lista de pares de primos (p,q) tales que n = p + 2q. Por ejemplo,

descomposicionesLemoine 5   ==  []
descomposicionesLemoine 7   ==  [(3,2)]
descomposicionesLemoine 9   ==  [(5,2),(3,3)]
descomposicionesLemoine 21  ==  [(17,2),(11,5),(7,7)]
descomposicionesLemoine 47  ==  [(43,2),(41,3),(37,5),(13,17)]
descomposicionesLemoine 33  ==  [(29,2),(23,5),(19,7),(11,11),(7,13)]
length (descomposicionesLemoine 2625)  ==  133

• (graficaLemoine n) dibuja la gráfica de los números de descomposiciones de Lemoine para los números impares menores o iguales que n. Por ejemplo, (graficaLemoine n 400) dibuja

Comprobar con QuickCheck la conjetura de Lemoine.

Nota: Basado en Lemoine's conjecture

Leer más…

Sea p un número primo. Toma un número natural positivo, si divisible entre un número primo menor que p divídelo entre el menor de dicho divisores, y en otro caso multiplícalo por p y súmale uno; si el resultado no es igual a uno, repite el proceso. Por ejemplo, para p = 7 y empezando en 42 el proceso es

42
-> 21   [= 42/2]
-> 7    [= 21/3]
-> 50   [= 7*7+1]
-> 25   [= 50/5]
-> 5    [= 25/5]
-> 1    [= 5/5]

La conjetura de Collatz generalizada afirma que este proceso siempre acaba en un número finito de pasos.

Definir la función

collatzGeneral :: Integer -> Integer -> [Integer]

tal que (collatzGeneral p x) es la sucesión de los elementos obtenidos en el proceso anterior para el primo p enpezando en x. Por ejemplo,

take 15 (collatzGeneral 7 42) == [42,21,7,50,25,5,1,8,4,2,1,8,4,2,1]
take 15 (collatzGeneral 3  6) == [6,3,10,5,16,8,4,2,1,4,2,1,4,2,1]
take 15 (collatzGeneral 5  6) == [6,3,1,6,3,1,6,3,1,6,3,1,6,3,1]
take 15 (collatzGeneral 7  6) == [6,3,1,8,4,2,1,8,4,2,1,8,4,2,1]
take 15 (collatzGeneral 9  6) == [6,3,1,10,5,1,10,5,1,10,5,1,10,5,1]

Comprobar con QuickCheck que se verifica la conjetura de Collatz generalizada; es decir, para todos enteros positivos n, x si p es el primo n-ésimo entonces 1 pertenece a (collatzGeneral p x).

Nota: El ejercicio etá basado en el artículo Los primos de la conjetura de Collatz publicado la semana pasada por Francisco R. Villatoro en su blog La Ciencia de la Mula Francis.

Leer más…

Goldbach, el de la famosa conjetura, hizo por lo menos otra conjetura que finalmente resultó ser falsa.

Esta última decía que todo número compuesto impar puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado. Así por ejemplo,

9 =  7 + 2×1^2
15 =  7 + 2×2^2
21 =  3 + 2×3^2
25 =  7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2

Definir las sucesiones

imparesCompuestos :: [Integer]
descomposiciones :: Integer -> [(Integer,Integer)]
contraejemplosGoldbach :: [Integer]

tales que

• imparesCompuestos es la lista de los números impares compuestos. Por ejemplo,

take 9 imparesCompuestos  ==  [9,15,21,25,27,33,35,39,45]

• (descomposiciones n) es la lista de las descomposiciones de n de n como la suma de un número primo más dos veces la suma de un cuadrado. Por ejemplo,

descomposiciones 9     ==  [(7,1)]
descomposiciones 21    ==  [(3,9),(13,4),(19,1)]
descomposiciones 5777  ==  []

Las 3 descomposiciones de 21 son

21 =  3 + 2*9 = 21 + 2*3^2
21 = 13 + 2*4 = 13 + 2*3^2
21 = 19 + 2*1 = 19 + 2*1^2

• contraejemplosGoldbach es la lista de los contraejemplos de la anterior conjetura de Goldbach; es decir, los números impares compuestos que no pueden expresarse como la suma de un número primo más dos veces la suma de un cuadrado. Por ejemplo,

take 2 contraejemplosGoldbach  ==  [5777,5993]

Comprobar con QuickCheck que la conjetura de Golbach se verifica a partir de 5993; es decir, todo número compuesto impar mayor que 5993 puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado.

Nota: Basado en el artículo La menos conocida de las conjeturas de Goldbach de Claudio Meller en el blog Números y algo más.

Leer más…

El triángulo de Bell es el triángulo numérico, cuya primera fila es [1] y en cada fila, el primer elemento es el último de la fila anterior y el elemento en la posición j se obtiene sumando el elemento anterior de su misma fila y de la fila anterior. Sus primeras filas son

1
1   2
2   3   5
5   7  10  15
15 20  27  37  52
52 67  87 114 151 203

Definir la función

trianguloDeBell :: [[Integer]]

tal que trianguloDeBell es la lista con las filas de dicho triángulo. Por ejemplo

λ> take 5 trianguloDeBell
[[1],[1,2],[2,3,5],[5,7,10,15],[15,20,27,37,52]]

Comprobar con QuickCheck que los números que aparecen en la primera + columna del triángulo coinciden con los números de Bell; es decir, el primer elemento de la n-ésima fila es el n-ésimo número de Bell.

Leer más…

Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:

{{1}, {2}, {3}}
{{1,2}, {3}}
{{1,3}, {2}}
{{1}, {2,3}}
{{1,2,3}}

El n-ésimo número de Bell, B(n), es el número de particiones de un conjunto de n elementos. Por lo visto anteriormentem B(3) = 5.

Definir las funciones

particiones :: [a] -> [[[a]]]
bell :: Integer -> Integer

tales que

• (particiones xs) es el conjunto de las particiones de xs. Por ejemplo,

λ> particiones [1,2]
[[[1,2]],[[1],[2]]]
λ> particiones [1,2,3]
[[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[2],[1,3]],[[1],[2],[3]]]
λ> particiones "abcd"
[["abcd"],["a","bcd"],["ab","cd"],["b","acd"],["abc","d"],["bc","ad"],
["ac","bd"],["c","abd"],["a","b","cd"],["a","bc","d"],["a","c","bd"],
["ab","c","d"],["b","ac","d"],["b","c","ad"],["a","b","c","d"]]

• (bell n) es el n-ésimo número de Bell. Por ejemplo,

λ> bell 3
5
λ> map bell [0..10]
[1,1,2,5,15,52,203,877,4140,21147,115975]

Comprobar con QuickCheck que (bell n) es equivalente a la función B(n) definida por

• B(0) = 1
• \(B(n) = \Sigma_{k=0}^{n-1} \binom{n-1}{k} B(k)\)

Leer más…

Definir la función

maximoConsecutivosIguales :: Eq a => a -> [a] -> Int

tal que (maximoConsecutivosIguales x xs) es el mayor número de elementos consecutivos en xs iguales a x. Por ejemplo,

maximoConsecutivosIguales 'b' "abbcccbbbd"    ==  3
maximoConsecutivosIguales 'b' "abbbbcccbbbd"  ==  4
maximoConsecutivosIguales 'e' "abbcccbbbd"    ==  0

Leer más…

Se dice que un número entero está entre potencias sucesivas de n si x-1 es una potencia n-ésima y x+1 es una potencia (n+1)-ésima; es decir, si existen a y b tales que x-1 es a^n y x+1 es b^(n+1). Por ejemplo,

2 está entre potencias sucesivas de 0, ya que 1 = 1^0 y 3 = 3^1
15 está entre potencias sucesivas de 1, ya que 14 = 14^1 y 16 = 4^2
26 está entre potencias sucesivas de 2, ya que 25 = 5^2 y 27 = 3^3

Definir las funciones

entrePotencias :: Integer -> Integer -> Bool
pares :: [(Integer,Integer)]
paresEntrePotencias :: [(Integer,Integer)]

tales que

• (entrePotencias n x) se verifica si x está entre potencias sucesivas de n. Por ejemplo,

entrePotencias 0 2   ==  True
entrePotencias 1 15  ==  True
entrePotencias 2 26  ==  True

• pares es la lista de los números enteros ordenados por su suma y primer elemento. Por ejemplo,

λ> take 11 pares
[(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0),(0,4)]

• paresEntrePotencias es la lista de los pares (n,x) tales que x está entre potencias sucesivas de n. Por ejemplo,

λ> take 10 paresEntrePotencias
[(1,0),(0,2),(1,3),(1,8),(1,15),(1,24),(2,26),(1,35),(1,48),(1,63)]

Comprobar con QuickCheck que 26es el único número que está entre potencias sucesivas con exponentes mayor que 1; es decir, que el único par (n,x) tal que x está entre potencias sucesivas de n y n > 1 es el (2,26).

Nota: Este ejercicio está basado en el artículo El número 26 ... ¡un número especial! de Amadeo Artacho en MatematicasCercanas.

Leer más…

El primorial de un número natural n es el producto de todos los números primos menores o iguales a n. Por ejemplo, el primorial de 5 es 30 porque el producto de los primos menores o iguales que 5 es

2 * 3 * 5 = 30

La propiedad de Erdös de acotación de los primoriales afirma que

Para todo número natural n, su primorial es menor o igual que 4ⁿ.

Definir las funciones

primorial :: Integer -> Integer
primoriales :: [Integer]

tales que

• (primorial n) es el primorial de n. Por ejemplo,

primorial 3  ==  6
primorial 5  ==  30
primorial 8  ==  210

• primoriales es la sucesión de los primoriales. Por ejemplo,

λ> take 15 primoriales
[1,1,2,6,6,30,30,210,210,210,210,2310,2310,30030,30030]

Comprobar con QuickCheck la propiedad de Erdös de acotación de los primoriales.

Leer más…