Definir las funciones

minimasDistancias             :: Matrix Int -> Matrix Int
sumaMinimaDistanciasIdentidad :: Int -> Int

tales que

• (mininasDistancias a) es la matriz de las mínimas distancias de cada elemento de a hasta alcanzar un 1 donde un paso es un movimiento hacia la izquierda, derecha, arriba o abajo. Por ejemplo,

λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]])
( 1 0 0 )
( 2 1 0 )
λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]])
( 1 1 0 )
( 0 1 1 )
λ> minimasDistancias (identity 5)
( 0 1 2 3 4 )
( 1 0 1 2 3 )
( 2 1 0 1 2 )
( 3 2 1 0 1 )
( 4 3 2 1 0 )

• (sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las mínimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo,

sumaMinimaDistanciasIdentidad 5       ==  40
sumaMinimaDistanciasIdentidad (10^2)  ==  333300
sumaMinimaDistanciasIdentidad (10^4)  ==  333333330000
sumaMinimaDistanciasIdentidad (10^6)  ==  333333333333000000

Leer más…

Definir la función

tieneCombinacionDivisible :: [Int] -> Int -> Bool

tal que (tieneCombinacionDivisible xs m) se verifica si existe alguna forma de combinar todos los elementos de la lista (con las operaciones suma o resta) de forma que el resultado sea divisible por m. Por ejemplo,

tieneCombinacionDivisible [1,3,4,6] 4  ==  True
tieneCombinacionDivisible [1,3,9]   2  ==  False

En el primer ejemplo, 1 - 2 + 3 + 4 + 6 = 12 es una combinación divisible por 4. En el segundo ejemplo, las combinaciones de [1,3,9] son

 1 + 3 + 9 =  13
-1 + 3 + 9 =  11
 1 - 3 + 9 =   7
-1 - 3 + 9 =   5
 1 + 3 - 9 =  -5
-1 + 3 - 9 =  -7
 1 - 3 - 9 = -11
-1 - 3 - 9 = -13

y ninguna de las 4 es divisible por 2.

Leer más…

Los segmentos iniciales de [3,1,2,5] son [3], [3,1], [3,1,2] y [3,1,2,5]. Sus sumas son 3, 4, 6 y 9, respectivamente. La suma de dichas sumas es 24.

Definir la función

sumaSegmentosIniciales :: [Integer] -> Integer

tal que (sumaSegmentosIniciales xs) es la suma de las sumas de los segmentos iniciales de xs. Por ejemplo,

sumaSegmentosIniciales [3,1,2,5]     ==  24
sumaSegmentosIniciales3 [1..3*10^6]  ==  4500004500001000000

Comprobar con QuickCheck que la suma de las sumas de los segmentos iniciales de la lista formada por n veces el número uno es el n-ésimo número triangular; es decir que

sumaSegmentosIniciales (genericReplicate n 1)

es igual a

n * (n + 1) `div` 2

Leer más…

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol = N Int [Arbol]
     deriving Show

Por ejemplo, los árboles

     1             1             1
    /  \          / \           / \
   /    \        8   3         8   3
  2      6          /|\       /|\  |
 / \    / \        4 2 6     4 5 6 2
4   5  5   7

se representan por

ej1, ej2, ej3 :: Arbol
ej1 = N 1 [N 2 [N 4 [], N 5 []], N 6 [N 5 [], N 7 []]]
ej2 = N 1 [N 8 [], N 3 [N 4 [], N 2 [], N 6 []]]
ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 2 []]]

Definir la función

hojasEnNoDecreciente :: Arbol -> [Int]

tal que (hojasEnNoDecreciente a) es el conjunto de las hojas de a que se encuentran en alguna rama no decreciente. Por ejemplo,

hojasEnNoDecreciente ej1  ==  [4,5,7]
hojasEnNoDecreciente ej2  ==  [4,6,8]
hojasEnNoDecreciente ej3  ==  []

Leer más…

Las matrices de Hadamard se definen recursivamente como sigue

λ> hadamard 0
( 1 )

λ> hadamard 1
(  1  1 )
(  1 -1 )

λ> hadamard 2
(  1  1  1  1 )
(  1 -1  1 -1 )
(  1  1 -1 -1 )
(  1 -1 -1  1 )

λ> hadamard 3
(  1  1  1  1  1  1  1  1 )
(  1 -1  1 -1  1 -1  1 -1 )
(  1  1 -1 -1  1  1 -1 -1 )
(  1 -1 -1  1  1 -1 -1  1 )
(  1  1  1  1 -1 -1 -1 -1 )
(  1 -1  1 -1 -1  1 -1  1 )
(  1  1 -1 -1 -1 -1  1  1 )
(  1 -1 -1  1 -1  1  1 -1 )

En general, la n-ésima matriz de Hadamard, H(n), es

( H(n-1)  H(n-1) )
( H(n-1) -H(n-1) )

Definir la función

hadamard :: Int -> Matrix Int

tal que (hadamard n) es la n-ésima matriz de Hadamard.

Comprobar con QuickCheck que para todo número natural n, el producto de la n-ésima matriz de Hadamard y su traspuesta es igual al producto de 2^n por la matriz identidad de orden 2^n.

Leer más…

Definir la función

menorNoSuma :: [Integer] -> Integer

tal que (menorNoSuma xs) es el menor número que no se puede escribir como suma de un subconjunto de xs, donde se supone que xs es un conjunto de números enteros positivos. Por ejemplo,

menorNoSuma [6,1,2]    ==  4
menorNoSuma [1,2,3,9]  ==  7
menorNoSuma [5]        ==  1
menorNoSuma [1..20]    ==  211
menorNoSuma [1..10^6]  ==  500000500001

Comprobar con QuickCheck que para todo n,

menorNoSuma [1..n] == 1 + sum [1..n]

Leer más…

El orden de divisibilidad de un número x es el mayor n tal que para todo i menor o igual que n, los i primeros dígitos de n es divisible por i. Por ejemplo, el orden de divisibilidad de 74156 es 3 porque

7       es divisible por 1
74      es divisible por 2
741     es divisible por 3
7415 no es divisible por 4

Definir la función

ordenDeDivisibilidad :: Integer -> Int

tal que (ordenDeDivisibilidad x) es el orden de divisibilidad de x. Por ejemplo,

ordenDeDivisibilidad 74156                      ==  3
ordenDeDivisibilidad 3608528850368400786036725  ==  25

Leer más…

Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.

Definir la función

ausente :: Integral a => [a] -> a

tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,

ausente [3,7,9,11]               ==  5
ausente [3,5,9,11]               ==  7
ausente [3,5,7,11]               ==  9
ausente ([1..9]++[11..])         ==  10
ausente ([1..10^6] ++ [2+10^6])  ==  1000001

Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay un término de la progresión aritmética que no está en la lista.

Leer más…

En 1999, L.J. Lange publicó el artículo An elegant new continued fraction for π.

En el primer teorema del artículo se demuestra la siguiente expresión de π mediante una fracción continua

La primeras aproximaciones son

a(1) = 3+1                = 4.0
a(2) = 3+(1/(6+9))        = 3.066666666666667
a(3) = 3+(1/(6+9/(6+25))) = 3.158974358974359

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: [Int] -> IO ()

tales que

• (aproximacionPi n) es la n-ésima aproximación de pi con la fracción continua de Lange. Por ejemplo,

aproximacionPi 1     ==  4.0
aproximacionPi 2     ==  3.066666666666667
aproximacionPi 3     ==  3.158974358974359
aproximacionPi 10    ==  3.141287132741557
aproximacionPi 100   ==  3.141592398533554
aproximacionPi 1000  ==  3.1415926533392926

• (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..10]) dibuja (grafica [10..100]) dibuja y (grafica [100..200]) dibuja

Leer más…

En el artículo El desarrollo más bello de Pi como suma infinita, Miguel Ángel Morales comenta el desarrollo de pi publicado por Leonhard Euler en su libro "Introductio in Analysis Infinitorum" (1748).

El desarrollo es el siguiente y se obtiene a partir de la serie armónica modificando sólo el signo de algunos términos según el siguiente criterio:

• Dejamos un + cuando el denominador de la fracción sea un 2 o un primo de la forma 4m-1.
• Cambiamos a - si el denominador de la fracción es un primo de la forma 4m+1.
• Si el número es compuesto ponemos el signo que quede al multiplicar los signos correspondientes a cada factor.

Por ejemplo,

• la de denominador 3 = 4x1-1 lleva un +,
• la de denominador 5 = 4x1+1 lleva un -,
• la de denominador 13 = 4x3+1 lleva un -,
• la de denominador 6 = 2x3 lleva un + (porque los dos llevan un +),
• la de denominador 10 = 2x5 lleva un - (porque el 2 lleva un + y el 5 lleva un -) y
• la de denominador 50 = 5x5x2 lleva un + (un - por el primer 5, otro - por el segundo 5 y un + por el 2).

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: Int -> IO ()

tales que

• (aproximacionPi n) es la aproximación de pi obtenida sumando los n primeros términos de la serie de Euler. Por ejemplo.

aproximacionPi 1        ==  1.0
aproximacionPi 10       ==  2.3289682539682537
aproximacionPi 100      ==  2.934318000847734
aproximacionPi 1000     ==  3.0603246224585128
aproximacionPi 10000    ==  3.1105295744825403
aproximacionPi 100000   ==  3.134308801935256
aproximacionPi 1000000  ==  3.1395057903490806

• (grafica n) dibuja la gráfica de las aproximaciones de pi usando k sumando donde k toma los valores de la lista [100,110..n]. Por ejemplo, al evaluar (grafica 4000) se obtiene

Leer más…

Se pueden generar los dígitos de Pi, como se explica en el artículo Unbounded spigot algorithms for the digits of pi c0on la función digitosPi definida por

digitosPi :: [Integer]
digitosPi = g(1,0,1,1,3,3) where
g (q,r,t,k,n,l) =
if 4*q+r-t < n*t
then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)
else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

Por ejemplo,

λ> take 25 digitosPi
[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3]

La distribución de los primeros 25 dígitos de pi es [0,2,3,5,3,3,3,1,2,3] ya que el 0 no aparece, el 1 ocurre 2 veces, el 3 ocurre 3 veces, el 4 ocurre 5 veces, ...

Usando digitosPi, definir las siguientes funciones

distribucionDigitosPi :: Int -> [Int]
frecuenciaDigitosPi   :: Int -> [Double]

tales que

• (distribucionDigitosPi n) es la distribución de los n primeros dígitos de pi. Por ejemplo,

λ> distribucionDigitosPi 10
[0,2,1,2,1,2,1,0,0,1]
λ> distribucionDigitosPi 100
[8,8,12,12,10,8,9,8,12,13]
λ> distribucionDigitosPi 1000
[93,116,103,103,93,97,94,95,101,105]
λ> distribucionDigitosPi 5000
[466,531,496,460,508,525,513,488,492,521]

• (frecuenciaDigitosPi n) es la frecuencia de los n primeros dígitos de pi. Por ejemplo,

λ> frecuenciaDigitosPi 10
[0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0]
λ> frecuenciaDigitosPi 100
[8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0]
λ> frecuenciaDigitosPi 1000
[9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5]
λ> frecuenciaDigitosPi 5000
[9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

Leer más…

La fórmula de Gregory-Leibniz para calcular pi es

y la de Beeler es

Definir las funciones

aproximaPiGL     :: Int -> Double
aproximaPiBeeler :: Int -> Double
graficas         :: [Int] -> IO ()

tales que

• (aproximaPiGL n) es la aproximación de pi con los primeros n términos de la fórmula de Gregory-Leibniz. Por ejemplo,

aproximaPiGL 1       ==  4.0
aproximaPiGL 2       ==  2.666666666666667
aproximaPiGL 3       ==  3.466666666666667
aproximaPiGL 10      ==  3.0418396189294032
aproximaPiGL 100     ==  3.1315929035585537
aproximaPiGL 1000    ==  3.140592653839794
aproximaPiGL 10000   ==  3.1414926535900345
aproximaPiGL 100000  ==  3.1415826535897198

• (aproximaPiBeeler n) es la aproximación de pi con los primeros n términos de la fórmula de Beeler. Por ejemplo,

aproximaPiBeeler 1   ==  2.0
aproximaPiBeeler 2   ==  2.6666666666666665
aproximaPiBeeler 3   ==  2.933333333333333
aproximaPiBeeler 10  ==  3.140578169680337
aproximaPiBeeler 60  ==  3.141592653589793
pi                   ==  3.141592653589793

• (graficas xs) dibuja la gráfica de las k-ésimas aproximaciones de pi, donde k toma los valores de la lista xs, con las fórmulas de Gregory-Leibniz y de Beeler. Por ejemplo, (graficas [1..25]) dibuja donde la línea morada corresponde a la aproximación de Gregory-Leibniz y la verde a la de Beeler.

Leer más…

El producto de Wallis es una expresión, descubierta por John Wallis en 1655, para representar el valor de π y que establece que:

 π     2     2     4     4     6     6     8     8
--- = --- · --- · --- · --- · --- · --- · --- · --- ···
 2     1     3     3     5     5     7     7     9

Definir las funciones

factoresWallis  :: [Rational]
productosWallis :: [Rational]
aproximacionPi  :: Int -> Double
errorPi         :: Double -> Int

ales que

• factoresWallis es la sucesión de los factores del productos de Wallis. Por ejemplo,

λ> take 10 factoresWallis
[2 % 1,2 % 3,4 % 3,4 % 5,6 % 5,6 % 7,8 % 7,8 % 9,10 % 9,10 % 11]

• productosWallis es la sucesión de los productos de los primeros factores de Wallis. Por ejemplo,

λ> take 7 productosWallis
[2 % 1,4 % 3,16 % 9,64 % 45,128 % 75,256 % 175,2048 % 1225]

• (aproximacionPi n) es la aproximación de pi obtenida multiplicando los n primeros factores de Wallis. Por ejemplo,

aproximacionPi 20     ==  3.2137849402931895
aproximacionPi 200    ==  3.1493784731686008
aproximacionPi 2000   ==  3.142377365093878
aproximacionPi 20000  ==  3.141671186534396

• (errorPi x) es el menor número de factores de Wallis necesarios para obtener pi con un error menor que x. Por ejemplo,

errorPi 0.1     ==  14
errorPi 0.01    ==  155
errorPi 0.001   ==  1569
errorPi 0.0001  ==  15707

Leer más…

Definir la función

productos :: Integer -> Integer -> [[Integer]]

tal que (productos n x) es las listas de n elementos consecutivos cuyo producto es x. Por ejemplo,

productos 2 6     ==  [[2,3]]
productos 3 6     ==  [[1,2,3]]
productos 4 1680  ==  [[5,6,7,8]]
productos 2 5     ==  []

Comprobar con QuickCheck que si n > 0 y x > 0, entonces

productos n (product [x..x+n-1]) == [[x..x+n-1]]

Usando productos, definir la función

productosDe2y3consecutivos :: [Integer]

cuyos elementos son los números naturales (no nulos) que pueden expresarse simultáneamente como producto de dos y tres números consecutivos. Por ejemplo,

head productosDe2y3consecutivos  ==  6

Nota. Según demostró Mordell en 1962, productosDe2y3consecutivos sólo tiene dos elementos.

Leer más…

La conjetura de Goldbach afirma que

Todo número entero mayor que 5 se puede escribir como suma de tres números primos.

En este ejercicio consideraremos la variación consistente en exigir que los tres sumandos sean distintos.

Definir las funciones

sumas3PrimosDistintos      :: Int -> [(Int,Int,Int)]
conKsumas3PrimosDistintos  :: Int -> Int -> [Int]
noSonSumas3PrimosDistintos :: Int -> [Int]

tales que

• (sumas3PrimosDistintos n) es la lista de las descomposiciones decrecientes de n como tres primos distintos. Por ejemplo,

sumas3PrimosDistintos 26  ==  [(13,11,2),(17,7,2),(19,5,2)]
sumas3PrimosDistintos 18  ==  [(11,5,2),(13,3,2)]
sumas3PrimosDistintos 10  ==  [(5,3,2)]
sumas3PrimosDistintos 11  ==  []

• (conKsumas3PrimosDistintos k n) es la lista de los números menores o iguales que n que se pueden escribir en k forma distintas como suma de tres primos distintos. Por ejemplo,

conKsumas3PrimosDistintos 3 99  ==  [26,27,29,32,36,42,46,48,54,58,60]
conKsumas3PrimosDistintos 2 99  ==  [18,20,21,22,23,24,25,28,30,34,64,70]
conKsumas3PrimosDistintos 1 99  ==  [10,12,14,15,16,19,40]
conKsumas3PrimosDistintos 0 99  ==  [11,13,17]

• (noSonSumas3PrimosDistintos n) es la lista de los números menores o iguales que n que no se pueden escribir como suma de tres primos distintos. Por ejemplo,

noSonSumas3PrimosDistintos 99   ==  [11,13,17]
noSonSumas3PrimosDistintos 500  ==  [11,13,17]

Leer más…

Una forma de la conjetura de Golbach afirma que todo entero mayor que 1 se puede escribir como la suma de uno, dos o tres números primos.

Si se define el índice de Goldbach de n > 1 como la mínima cantidad de primos necesarios para que su suma sea n, entonces la conjetura de Goldbach afirma que todos los índices de Goldbach de los enteros mayores que 1 son menores que 4.

Definir las siguientes funciones

indiceGoldbach  :: Int -> Int
graficaGoldbach :: Int -> IO ()

tales que

• (indiceGoldbach n) es el índice de Goldbach de n. Por ejemplo,

indiceGoldbach 2                        ==  1
indiceGoldbach 4                        ==  2
indiceGoldbach 27                       ==  3
sum (map indiceGoldbach [2..5000])      ==  10619
maximum (map indiceGoldbach [2..5000])  ==  3

• (graficaGoldbach n) dibuja la gráfica de los índices de Goldbach de los números entre 2 y n. Por ejemplo, (graficaGoldbach 150) dibuja

Comprobar con QuickCheck la conjetura de Goldbach anterior.

Leer más…

Hyman Levy observó que

7 = 3 + 2 x 2
9 = 3 + 2 x 3 =  5 + 2 x 2
11 = 5 + 2 x 3 =  7 + 2 x 2
13 = 3 + 2 x 5 =  7 + 2 x 3
15 = 3 + 2 x 5 = 11 + 2 x 2
17 = 3 + 2 x 7 =  7 + 2 x 5 = 11 + 2 x 3 = 13 + 2 x 2
19 = 5 + 2 x 7 = 13 + 2 x 3

y conjeturó que todos los número impares mayores o iguales que 7 se pueden escribir como la suma de un primo y el doble de un primo. El objetivo de los siguientes ejercicios es comprobar la conjetura de Levy.

Definir las siguientes funciones

descomposicionesLevy :: Integer -> [(Integer,Integer)]
graficaLevy          :: Integer -> IO ()

tales que

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

descomposicionesLevy  7  ==  [(3,2)]
descomposicionesLevy  9  ==  [(3,3),(5,2)]
descomposicionesLevy 17  ==  [(3,7),(7,5),(11,3),(13,2)]

• (graficaLevy n) dibuja los puntos (x,y) tales que x pertenece a [7,9..7+2x(n-1)] e y es el número de descomposiciones de Levy de x. Por ejemplo, (graficaLevy 200) dibuja

Comprobar con QuickCheck la conjetura de Levy.

Leer más…

Partiendo de los 5 primeros números primos y calculando el valor absoluto de la diferencia de cada dos números consecutivos hasta quedarse con un único número se obtiene la siguiente tabla:

2, 3, 5, 7, 11
1, 2, 2, 4
1, 0, 2
1, 2
1

Se observa que todas las filas, salvo la inicial, comienzan con el número 1.

Repitiendo el proceso pero empezando con los 8 primeros números primos se obtiene la siguiente tabla:

2, 3, 5, 7, 11, 13, 17, 19
1, 2, 2, 4,  2,  4,  2
1, 0, 2, 2,  2,  2
1, 2, 0, 0,  0
1, 2, 0, 0
1, 2, 0
1, 2
1

Se observa que, de nuevo, todas las filas, salvo la inicial, comienza con el número 1.

La conjetura de Gilbreath afirma que si escribimos la sucesión de números primos completa y después construimos las correspondientes sucesiones formadas por el valor absoluto de la resta de cada pareja de números consecutivos, entonces todas esas filas que obtenemos comienzan siempre por 1.

El objetivo de este ejercicio es comprobar experimentalmente dicha conjetura.

Para la representación, usaremos la simétrica de la que hemos comentado anteriormente; es decir,

2
3, 1
5, 2, 1
7, 2, 0, 1
11, 4, 2, 2, 1
13, 2, 2, 0, 2, 1
17, 4, 2, 0, 0, 2, 1
19, 2, 2, 0, 0, 0, 2, 1

en la que la primera columna son los números primos y el elemento de la fila i y columna j (con i, j > 1) es el valor absoluto de la diferencia de los elementos (i,j-1) e (i-1,j-1).

Definir las siguientes funciones

siguiente           :: Integer -> [Integer] -> [Integer]
triangulo           :: [[Integer]]
conjetura_Gilbreath :: Int -> Bool

tales que

• (siguiente x ys) es la línea siguiente de la ys que empieza por x en la tabla de Gilbreath; es decir, si ys es [y1,y2,...,yn], entonces (siguiente x ys) es [x,|y1-x|,|y2-|y1-x||,...]. Por ejemplo,

siguiente  7 [5,2,1]               ==  [7,2,0,1]
siguiente 29 [23,4,2,0,0,0,0,2,1]  ==  [29,6,2,0,0,0,0,0,2,1]

• triangulo es el triángulo de Gilbreath. Por ejemplo,

λ> take 10 triangulo
[[ 2],
[ 3,1],
[ 5,2,1],
[ 7,2,0,1],
[11,4,2,2,1],
[13,2,2,0,2,1],
[17,4,2,0,0,2,1],
[19,2,2,0,0,0,2,1],
[23,4,2,0,0,0,0,2,1],
[29,6,2,0,0,0,0,0,2,1]]

• (conjeturaGilbreath n) se verifica si se cumple la conjetura de Gilbreath para los n primeros números primos; es decir, en el triángulo de Gilbreath cuya primera columna son los n primeros números primos, todas las filas a partir de la segunda terminan en 1. Por ejemplo,

λ> conjeturaGilbreath 1000
True

Leer más…

En el artículo Integers as a sum of consecutive primes in 2,3,4,.. ways se presentan números que se pueden escribir como sumas de primos consecutivos de varias formas. Por ejemplo, el 41 se puede escribir de dos formas distintas

41 =  2 +  3 +  5 + 7 + 11 + 13
41 = 11 + 13 + 17

el 240 se puede escribir de tres formas

240 =  17 +  19 + 23 + 29 + 31 + 37 + 41 + 43
240 =  53 +  59 + 61 + 67
240 = 113 + 127

y el 311 se puede escribir de 4 formas

311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
311 =  53 +  59 +  61 + 67 + 71
311 = 101 + 103 + 107

Definir la función

sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma de dos o más números primos consecutivos. Por ejemplo,

λ> sumas 41
[[2,3,5,7,11,13],[11,13,17]]
λ> sumas 240
[[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]]
λ> sumas 311
[[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],
[53,59,61,67,71],[101,103,107]]
λ> maximum [length (sumas n) | n <- [1..600]]
4

Leer más…

Leer más…

Los intervalos se pueden representar por pares de enteros (a,b) con a < b. Los elementos del intervalo (2,5) son 2, 3, 4 y 5; por tanto, su longitud es 4. Para calcular la suma de los longitudes de una lista de intervalos hay que tener en cuenta de quw si hay intervalos superpuestos sus elementos deben de contarse sólo una vez. Por ejemplo, la suma de los intervalos de [(1,4),(7,10),(3,5)] es 7 ya que, como los intervalos (1,4) y (3,5) se solapan, los podemos ver como el intervalo (1,5) que tiene una longitud de 4.

Definir la función

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

tal que (sumaIntervalos xs) es la suma de las longitudes de los intervalos de xs contando los superpuestos sólo una vez. Por ejemplo,

sumaIntervalos [(1, 5)]                  == 4
sumaIntervalos [(1, 5), (6, 10)]         == 8
sumaIntervalos [(1, 5), (5, 10)]         == 9
sumaIntervalos [(1, 5), (1, 5)]          == 4
sumaIntervalos [(1, 4), (7, 10), (3, 5)] == 7

Leer más…

En este ejercicio, se representa un mapa mediante una lista de listas de la misma longitud donde todos sus elementos son 0 menos uno (que es un 1) que es donde se encuentra la mina. Por ejemplo, en el mapa

0 0 0 0
0 0 0 0
0 1 0 0

la posición de la mina es (2,1).

Definir la función

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

tal que (posicionMina m) es la posición de la mina en el mapa m, Por ejemplo,

posicionMina [[0,0,0,0],[0,0,0,0],[0,1,0,0]]  ==  (2,1)

Leer más…

Un número primo distinto de 2 tiene la forma 4k + 1 o 4k + 3. Chebyshev notó en 1853 que la mayoría de las veces hay más números primos de la forma 4k + 3 que números primos de la forma 4k + 1 menores que un número dado. Esto se llama el sesgo de Chebyshev.

Definir las funciones

distribucionPrimosModulo4 :: [(Integer, Integer, Integer)]
empatesRestosModulo4 :: [Integer]
mayoria1RestosModulo4 :: [Integer]
grafica_Chebyshev :: Int -> IO ()

tales que

• distribucionPrimosModulo4 es la lista de las ternas (p,a,b) tales que p es un números primo, a es la cantidad de primos menores o iguales que p congruentes con 1 módulo 4 y b es la cantidad de primos menores o iguales que p congruentes con 3 módulo 4. Por ejemplo,

λ> take 7 distribucionPrimosModulo4
[(2,0,0),(3,0,1),(5,1,1),(7,1,2),(11,1,3),(13,2,3),(17,3,3)]
λ> distribucionPrimosModulo4 !! (5*10^5)
(7368791,249888,250112)

• empatesRestosModulo4 es la lista de los primos p tales que la cantidad de primos menores o iguales que p congruentes con 1 módulo 4 es igual a la cantidad de primos menores o iguales que p congruentes con 3 módulo 4. Por ejemplo,

λ> take 10 empatesRestosModulo4
[2,5,17,41,461,26833,26849,26863,26881,26893]
λ> length (takeWhile (<= 10^6) empatesRestosModulo4)
112

• mayoria1RestosModulo4 es la lista de los primos p tales que la cantidad de primos menores o iguales que p congruentes con 1 módulo 4 es mayor que la cantidad de primos menores o iguales que p congruentes con 3 módulo 4. Por ejemplo,

λ> take 10 mayoria1RestosModulo4
[26861,616841,616849,616877,616897,616909,616933,616943,616951,616961]
λ> length (takeWhile (<= 10^6) mayoria1RestosModulo4)
239

• (graficaChebyshev n) dibuja la gráfica de los puntos (p,b-a) donde p es uno de los n primeros primos impares, a es la cantidad de primos menores o iguales que p congruentes con 1 módulo 4 y b es la cantidad de primos menores o iguales que p congruentes con 3 módulo 4. Por ejemplo, (graficaChebyshev 5000) dibuja la figura

Leer más…

Un número magnánimo es un número tal que las sumas obtenidas insertando un "+" entre sus dígitos en cualquier posición son números primos. Por ejemplo, 4001 es un número magnánimo porque los números 4+001=5, 40+01=41 y 400+1=401 son primos.

Definir las funciones

esMagnanimo :: Integer -> Bool
primosMagnanimos :: [Integer]

tales que

• (esMagnanimo n) se verifica si n es un número magnánimo. Por ejemplo,

esMagnanimo 4001  ==  True
esMagnanimo 2019  ==  False

• primosMagnanimos es la lista de los números primos magnánimos. Por ejemplo,

λ> take 20 primosMagnanimos
[2,3,5,7,11,23,29,41,43,47,61,67,83,89,101,227,229,281,401,443]

Leer más…

Definir la función

diagonalesInvertidas :: Matrix a -> Matrix a

tal que (diagonalesInvertidas q) es la matriz obtenida invirtiendo el orden de los elementos de la diagonal principal y de la diagonal secundaria de q. Por ejemplo,

λ> fromList 5 5 [1..]
┌                ┐
│  1  2  3  4  5 │
│  6  7  8  9 10 │
│ 11 12 13 14 15 │
│ 16 17 18 19 20 │
│ 21 22 23 24 25 │
└                ┘
λ> diagonalesInvertidas (fromList 5 5 [1..])
┌                ┐
│ 25  2  3  4 21 │
│  6 19  8 17 10 │
│ 11 12 13 14 15 │
│ 16  9 18  7 20 │
│  5 22 23 24  1 │
└                ┘
λ> fromList 3 3 ['a','b'..]
┌             ┐
│ 'a' 'b' 'c' │
│ 'd' 'e' 'f' │
│ 'g' 'h' 'i' │
└             ┘
λ> diagonalesInvertidas (fromList 3 3 ['a','b'..])
┌             ┐
│ 'i' 'b' 'g' │
│ 'd' 'e' 'f' │
│ 'c' 'h' 'a' │
└             ┘

Leer más…

El método de Newton para el cálculo de pi se basa en la relación

y en el desarrollo del arco seno

de donde se obtiene la fórmula

La primeras aproximaciones son

a(0) = 6*(1/2)                               = 3.0
a(1) = 6*(1/2+1/(2*3*2^3))                   = 3.125
a(2) = 6*(1/2+1/(2*3*2^3)+(1*3)/(2*4*5*2^5)) = 3.1390625

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: [Int] -> IO ()

tales que

• (aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Newton. Por ejemplo,

aproximacionPi 0   ==  3.0
aproximacionPi 1   ==  3.125
aproximacionPi 2   ==  3.1390625
aproximacionPi 10  ==  3.1415926468755613
aproximacionPi 21  ==  3.141592653589793
pi                 ==  3.141592653589793

• (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..30]) dibuja

Leer más…

Se dice que una palabra tiene una repetición en una frase si es igual a una, o más, de las palabras consecutivas sin distinguir mayúsculas de minúsculas.

Definir la función

nRepeticionesConsecutivas :: String ->Int

tal que (nRepeticionesConsecutivas cs) es el número de repeticiones de palabras consecutivas de la cadena cs. Por ejemplo,

nRepeticionesConsecutivas "oso rana"                    == 0
nRepeticionesConsecutivas "oso rana oso"                == 0
nRepeticionesConsecutivas "oso oSo rana"                == 1
nRepeticionesConsecutivas "oso oso oso rana"            == 1
nRepeticionesConsecutivas "coronavirus virus oso rana"  == 0
nRepeticionesConsecutivas "virus     virus oso rana"    == 1
nRepeticionesConsecutivas "virus oso virus oso rana"    == 0
nRepeticionesConsecutivas "oso oso oso oso oso oso"     == 1
nRepeticionesConsecutivas "oso oso oso oso rana rana"   == 2
nRepeticionesConsecutivas "rana rana oso oso rana rana" == 3

Leer más…

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir las funciones

mediasDigitosDePi        :: IO [Double]
graficaMediasDigitosDePi :: Int -> IO ()

tales que

• mediasDigitosDePi es la sucesión cuyo n-ésimo elemento es la media de los n primeros dígitos de pi. Por ejemplo,

λ> xs <- mediasDigitosDePi
λ> take 5 xs
[1.0,2.5,2.0,2.75,4.0]
λ> take 10 xs
[1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]
λ> take 10 <$> mediasDigitosDePi
[1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]

• (graficaMediasDigitosDePi n) dibuja la gráfica de los n primeros términos de mediasDigitosDePi. Por ejemplo,
• (graficaMediasDigitosDePi 20) dibuja
• (graficaMediasDigitosDePi 200) dibuja
• (graficaMediasDigitosDePi 2000) dibuja

Leer más…

Definir, por simulación, la función

distanciaEsperada :: Int -> IO Double

tal que (distanciaEsperada n) es la distancia esperada entre n puntos del cuadrado unitario de vértices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,

distanciaEsperada 10     ==  0.43903617921423593
distanciaEsperada 10     ==  0.6342350621260004
distanciaEsperada 100    ==  0.5180418995364429
distanciaEsperada 100    ==  0.5288261085653962
distanciaEsperada 1000   ==  0.5143804432569616
distanciaEsperada 10000  ==  0.5208360147922616

El valor exacto de la distancia esperada es

ve = (sqrt(2) + 2 + 5*log(1+sqrt(2)))/15 = 0.5214054331647207

Definir la función

graficaDistanciaEsperada :: [Int] -> IO ()

tal que (graficaDistanciaEsperadan n) dibuja las gráficas de los pares (n, distanciaEsperada n) para n en la lista creciente ns junto con la recta y = ve, donde ve es el valor exacto. Por ejemplo, (graficaDistanciaEsperada [10,30..4000]) dibuja

Leer más…

Una serie infinita para el cálculo de pi, publicada por Nilakantha en el siglo XV, es

           4       4       4       4
pi = 3 + ----- - ----- + ----- - ------ + ···
         2x3x4   4x5x6   6x7x8   8x9x10

Definir las funciones

aproximacionPi :: Int -> Double
tabla          :: FilePath -> [Int] -> IO ()

tales que

• (aproximacionPi n) es la n-ésima aproximación de pi obtenido sumando los n primeros términos de la serie de Nilakantha. Por ejemplo,

aproximacionPi 0        ==  3.0
aproximacionPi 1        ==  3.1666666666666665
aproximacionPi 2        ==  3.1333333333333333
aproximacionPi 3        ==  3.145238095238095
aproximacionPi 4        ==  3.1396825396825396
aproximacionPi 5        ==  3.1427128427128426
aproximacionPi 10       ==  3.1414067184965018
aproximacionPi 100      ==  3.1415924109719824
aproximacionPi 1000     ==  3.141592653340544
aproximacionPi 10000    ==  3.141592653589538
aproximacionPi 100000   ==  3.1415926535897865
aproximacionPi 1000000  ==  3.141592653589787
pi                      ==  3.141592653589793

• (tabla f ns) escribe en el fichero f las n-ésimas aproximaciones de pi, donde n toma los valores de la lista ns, junto con sus errores. Por ejemplo, al evaluar la expresión

tabla "AproximacionesPi.txt" [0,10..100]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|   10 | 3.141406718497 | 0.000185935093 |
|   20 | 3.141565734659 | 0.000026918931 |
|   30 | 3.141584272675 | 0.000008380915 |
|   40 | 3.141589028941 | 0.000003624649 |
|   50 | 3.141590769850 | 0.000001883740 |
|   60 | 3.141591552546 | 0.000001101044 |
|   70 | 3.141591955265 | 0.000000698325 |
|   80 | 3.141592183260 | 0.000000470330 |
|   90 | 3.141592321886 | 0.000000331704 |
|  100 | 3.141592410972 | 0.000000242618 |
+------+----------------+----------------+

al evaluar la expresión

tabla "AproximacionesPi.txt" [0,500..5000]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|  500 | 3.141592651602 | 0.000000001988 |
| 1000 | 3.141592653341 | 0.000000000249 |
| 1500 | 3.141592653516 | 0.000000000074 |
| 2000 | 3.141592653559 | 0.000000000031 |
| 2500 | 3.141592653574 | 0.000000000016 |
| 3000 | 3.141592653581 | 0.000000000009 |
| 3500 | 3.141592653584 | 0.000000000006 |
| 4000 | 3.141592653586 | 0.000000000004 |
| 4500 | 3.141592653587 | 0.000000000003 |
| 5000 | 3.141592653588 | 0.000000000002 |
+------+----------------+----------------+

Leer más…

Definir la función

division :: String -> [String]

tal que (division cs) es la lista de las palabras formadas por dos elementos consecutivos de cs y, en el caso de que la longitud de cs sea impar, el último elemento de la última palabra es el carácter de subrayado. Por ejemplo,

division "pandemia"    ==  ["pa","nd","em","ia"]
division "covid2019"   ==  ["co","vi","d2","01","9_"]
division "covid 2019"  ==  ["co","vi","d ","20","19"]

Leer más…

Definir la función

palabrasInvertidas :: String -> String

tal que (palabrasInvertidas cs) es la cadena obtenida invirtiendo las palabras de cs. Por ejemplo,

λ> palabrasInvertidas "Del principio al final"
"final al principio Del"
λ> palabrasInvertidas "una a una"
"una a una"

Leer más…

Definir la función

primeroNoConsecutivo :: (Eq a,Enum a) => [a] -> Maybe a

tal que (primeroNoConsecutivo xs) es el primer elemento de la lista xs que no es igual al siguiente de su elemento anterior en xs o Nothing si tal elemento no existe. Por ejemplo

primeroNoConsecutivo [1,2,3,4,6,7,8] == Just 6
primeroNoConsecutivo "bcdfg"         == Just 'f'
primeroNoConsecutivo "bcdef"         == Nothing

Leer más…

Los números de Fibonacci son los números F(n) de la siguiente sucesión

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

que comienza con 0 y 1 y los siguientes términos son las sumas de los dos anteriores.

Un número x es el producto de dos números de Fibonacci consecutivos si existe un n tal que

F(n) * F(n+1) = x

y su prueba es (F(n),F(n+1),True). Por ejemplo, 714 es el producto de dos números de Fibonacci consecutivos ya que

F(8) = 21, F(9) = 34 y 714 = 21 * 34.

Su prueba es (21, 34, True).

Un número x no es el producto de dos números de Fibonacci consecutivos si no existe un n tal que

F(n) * F(n+1) = x

y su prueba es (F(m),F(m+1),False) donde m es el menor número tal que

F(m) * F(m+1) > x

Por ejemplo, 800 no es el producto de dos números de Fibonacci consecutivos, ya que

F(8) = 21, F(9) = 34, F(10) = 55 y 21 * 34 < 800 < 34 * 55.

Su prueba es (34, 55, False),

Definir la función

productoFib :: Integer -> (Integer, Integer, Bool)

tal que (productoFib x) es la prueba de que es, o no es, el producto de dos números de Fibonacci consecutivos. Por ejemplo,

productoFib 714  == (21,  34, True)
productoFib 800  == (34,  55, False)
productoFib 4895 == (55,  89, True)
productoFib 5895 == (89, 144, False)

Leer más…

La ordenación pendular de una lista xs es la lista obtenida organizando sus elementos de manera similar al movimiento de ida y vuelta de un péndulo; es decir,

• El menor elemento de xs se coloca en el centro de la lista.
• El siguiente elemento se coloca a la derecha del menor.
• El siguiente elemento se coloca a la izquierda del menor y así sucesivamente, de una manera similar a la de un péndulo.

Por ejemplo, la ordenación pendular de [6,6,8,5,10] es [10,6,5,6,8].

Definir la función

pendulo :: [Int] -> [Int]

tal que (pendulo xs) es la ordenación pendular de xs. Por ejemplo,

pendulo [6,6,8,5,10]                 == [10,6,5,6,8]
pendulo [-9,-2,-10,-6]               == [-6,-10,-9,-2]
pendulo [11,-16,-18,13,-11,-12,3,18] == [13,3,-12,-18,-16,-11,11,18]

Leer más…

Un niño está jugando con una pelota en el noveno piso de un edificio alto. La altura de este piso, h, es conocida. Deja caer la pelota por la ventana. La pelota rebota una r-ésima parte de su altura (por ejemplo, dos tercios de su altura). Su madre mira por una ventana a w metros del suelo (por ejemplo, a 1.5 metros). ¿Cuántas veces verá la madre a la pelota pasar frente a su ventana incluyendo cuando está cayendo y rebotando?

Se deben cumplir tres condiciones para que el experimento sea válido:

• La altura "h" debe ser mayor que 0
• El rebote "r" debe ser mayor que 0 y menor que 1
• La altura de la ventana debe ser mayor que 0 y menor que h.

Definir la función

numeroAvistamientos :: Double -> Double -> Double -> Integer

tal que (numeroAvistamientos h r v) es el número de avistamientos de la pelota si se cumplen las tres condiciones anteriores y es -1 en caso contrario. Por ejemplo,

numeroAvistamientos 3    0.66 1.5  ==  3
numeroAvistamientos 30   0.66 1.5  ==  15
numeroAvistamientos (-3) 0.66 1.5  ==  -1
numeroAvistamientos 3    (-1) 1.5  ==  -1
numeroAvistamientos 3    2    1.5  ==  -1
numeroAvistamientos 3    0.5  (-1) ==  -1
numeroAvistamientos 3    0.5  4    ==  -1

Leer más…

Definir la función

mayorEquidigital :: Integer -> Integer

tal que (mayorEquidigital n) es el mayor número que se puede formar con los dígitos de n. Por ejemplo,

mayorEquidigital 325271  ==  753221

Leer más…

¡El mundo está en cuarentena! Hay una nueva pandemia que lucha contra la humanidad. Cada continente está aislado de los demás, pero las personas infectadas se han propagado antes de la advertencia.

En este problema se representará el mundo por una cadena como la siguiente

"01000000X000X011X0X"

donde 0 representa no infectado, 1 representa infectado y X representa un océano

Las reglas de propagación son:

• El virus no puede propagarse al otro lado de un océano.
• Si una persona se infecta, todas las personas de este continente se infectan también.
• El primer y el último continente no están conectados.

El problema consiste en encontrar el porcentaje de la población humana que se infectó al final. Por ejemplo,

inicio:     "01000000X000X011X0X"
final:      "11111111X000X111X0X"
total:      15
infectados: 11
porcentaje: 100*11/15 = 73.33333333333333

Definir la función

porcentajeInfectados :: String -> Double

tal que (porcentajeInfectados xs) es el porcentaje final de infectados para el mapa inicial xs. Por ejemplo,

porcentajeInfectados "01000000X000X011X0X"  == 73.33333333333333
porcentajeInfectados "01X000X010X011XX"     == 72.72727272727273
porcentajeInfectados "XXXXX"                == 0.0
porcentajeInfectados "0000000010"           == 100.0
porcentajeInfectados "X00X000000X10X0100"   == 42.857142857142854

Leer más…

Si \(A\) es una matriz \(m \times n\) y \(B\) es una matriz \(p \times q\), entonces el producto de Kronecker \(A \otimes B\) es la matriz bloque \(mp \times nq\)

Más explícitamente, tenemos

Por ejemplo,

Definir la función

kronecker :: Num t => Matrix t -> Matrix t -> Matrix t

tal que (kronecker a b) es el producto de Kronecker de las matrices a y b. Por ejemplo,

λ> kronecker (fromLists [[1,2],[3,1]]) (fromLists [[0,3],[2,1]])
┌         ┐
│ 0 3 0 6 │
│ 2 1 4 2 │
│ 0 9 0 3 │
│ 6 3 2 1 │
└         ┘
λ> kronecker (fromLists [[1,2],[3,4]]) (fromLists [[2,1],[-1,0],[3,2]])
┌             ┐
│  2  1  4  2 │
│ -1  0 -2  0 │
│  3  2  6  4 │
│  6  3  8  4 │
│ -3  0 -4  0 │
│  9  6 12  8 │
└             ┘
λ> kronecker (fromLists [[2,1],[-1,0],[3,2]]) (fromLists [[1,2],[3,4]])
┌             ┐
│  2  4  1  2 │
│  6  8  3  4 │
│ -1 -2  0  0 │
│ -3 -4  0  0 │
│  3  6  2  4 │
│  9 12  6  8 │
└             ┘

Leer más…

Nota: En este ejercicio se usa la misma notación que en los anteriores importando los módulos

• Evaluacion_de_FNC
• Modelos_de_FNC
• Problema_SAT_para_FNC
• Cliques
• KCliques
• Grafo_FNC

Definir las funciones

cliquesFNC :: FNC -> [[(Int,Literal)]]
cliquesCompletos :: FNC -> [[(Int,Literal)]]
esSatisfaciblePorClique :: FNC -> Bool

tales que

• (cliquesFNCf) es la lista de los cliques del grafo de f. Por ejemplo,

λ> cliquesFNC [[1,-2,3],[-1,2],[-2,3]]
[[], [(0,1)], [(1,2)], [(0,1),(1,2)], [(2,-2)],
 [(0,1),(2,-2)], [(2,3)], [(0,1),(2,3)], [(1,2),(2,3)],
 [(0,1),(1,2),(2,3)], [(0,-2)], [(2,-2),(0,-2)], [(2,3),(0,-2)],
 [(1,-1)], [(2,-2),(1,-1)], [(2,3),(1,-1)], [(0,-2),(1,-1)],
 [(2,-2),(0,-2),(1,-1)], [(2,3),(0,-2),(1,-1)], [(0,3)],
 [(1,2),(0,3)], [(2,-2),(0,3)], [(2,3),(0,3)],
 [(1,2),(2,3),(0,3)], [(1,-1),(0,3)],
 [(2,-2),(1,-1),(0,3)], [(2,3),(1,-1),(0,3)]]

• (cliquesCompletos f) es la lista de los cliques del grafo de f que tiene tantos elementos como cláusulas tiene f. Por ejemplo,

λ> cliquesCompletos [[1,-2,3],[-1,2],[-2,3]]
[[(0,1),(1,2),(2,3)],   [(2,-2),(0,-2),(1,-1)],
 [(2,3),(0,-2),(1,-1)], [(1,2),(2,3),(0,3)],
 [(2,-2),(1,-1),(0,3)], [(2,3),(1,-1),(0,3)]]
λ> cliquesCompletos [[1,2],[1,-2],[-1,2],[-1,-2]]
[]

• (esSatisfaciblePorClique f) se verifica si f no contiene la cláusula vacía, tiene más de una cláusula y posee algún clique completo. Por ejemplo,

λ> esSatisfaciblePorClique [[1,-2,3],[-1,2],[-2,3]]
True
λ> esSatisfaciblePorClique [[1,2],[1,-2],[-1,2],[-1,-2]]
False

Comprobar con QuickCheck que toda fórmula en FNC es satisfacible si, y solo si, es satisfacible por Clique.

Leer más…

Para reducir el problema del clique a SAT se comienza asociando a cada fórmula F en FNC un grafo G de forma que F es saisfacible si, y sólo si, G tiene un clique con tantos nodos como cláusulas tiene F.

Los nodos del grafo de F son los literales de las cláusulas de F junto con el número de la cláusula. Por ejemplo, la lista de nodos de la FNC [[1,-2,3],[-1,2],[-2,3]] es

[(0,1),(0,-2),(0,3),
 (1,-1),(1,2),
 (2,-2),(2,3)]

En el grafo de F, hay un arco entre dos nodos si, y solo si, corresponden a cláusulas distintas y sus literales no son complementarios. Por ejemplo,

• hay un arco entre (0,1) y (1,2) [porque son de cláusulas distintas (0 y 1) y sus literales (1 y 2) no son complementarios.
• no hay un arco entre (0,1) y (1,-1) [porque sus literales (1 y -1) no son complementarios.
• no hay un arco entre (0,1) y (0,3) [porque son de la misma cláusula (la 0)].

Nota: En este ejercicio se usará los conceptos de los anteriores importando los módulos Evaluacion_de_FNC y Grafo.

Definir las funciones

nodosFNC :: FNC -> [(Int,Literal)]
grafoFNC :: FNC -> Grafo (Int,Literal)

tales que

• (nodosFNC f) es la lista de los nodos del grafo de f. Por ejemplo,

λ> nodosFNC [[1,-2,3],[-1,2],[-2,3]]
[(0,1),(0,-2),(0,3),(1,-1),(1,2),(2,-2),(2,3)]

• (grafo FNC f) es el grafo de f. Por ejemplo,

λ> grafoFNC [[1,-2,3],[-1,2],[-2,3]]
[ ((0,1),(1,2)),  ((0,1),(2,-2)), ((0,1),(2,3)),
  ((0,-2),(1,-1)),((0,-2),(2,-2)),((0,-2),(2,3)),
  ((0,3),(1,-1)), ((0,3),(1,2)),  ((0,3),(2,-2)),((0,3),(2,3)),
  ((1,-1),(2,-2)),((1,-1),(2,3)),
  ((1,2),(2,3))]
λ> grafoFNC [[1,2],[1,-2],[-1,2],[-1,-2]]
[((0,1),(1,1)),((0,1),(1,-2)),((0,1),(2,2)),((0,1),(3,-2)),
 ((0,2),(1,1)),((0,2),(2,-1)),((0,2),(2,2)),((0,2),(3,-1)),
 ((1,1),(2,2)),((1,1),(3,-2)),
 ((1,-2),(2,-1)),((1,-2),(3,-1)),((1,-2),(3,-2)),
 ((2,-1),(3,-1)),((2,-1),(3,-2)),
 ((2,2),(3,-1))]

Leer más…

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

Definir la función

kCliques :: Eq a => Grafo a -> Int -> [[a]]

tal que (kCliques g k) es la lista de los cliques del grafo g de tamaño k. Por ejemplo,

λ> kCliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3
[[2,3,5],[2,4,5]]
λ> kCliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2
[[1,2],[2,3],[2,4],[2,5],[3,5],[4,5]]
λ> kCliques [(n,n+1) | n <- [1..100]] 3
[]

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

Leer más…

Leer más…

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

Un clique (en español, pandilla) de un grafo g es un conjunto de nodos de g tal que todos sus elementos están conectados en g.

Definir las funciones

esClique :: Eq a => Grafo a -> [a] -> Bool
cliques  :: Eq a => Grafo a -> [[a]]

tales que

• (esClique g xs) se verifica si el conjunto de nodos xs del grafo g es un clique de g. Por ejemplo,

esClique [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] [2,3,5]  ==  True
esClique [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] [2,3,4]  ==  False

• (cliques g) es la lista de los cliques del grafo g. Por ejemplo,

λ> cliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)]
[[],[1],[2],[1,2],[3],[2,3],[4],[2,4],
 [5],[2,5],[3,5],[2,3,5],[4,5],[2,4,5]]

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

Leer más…

Definir la función

parejas :: [a] -> [(a,a)]

tal que (parejas xs) es la lista de las parejas formados por los elementos de xs y sus siguientes en xs. Por ejemplo,

parejas [1..4] == [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
length (parejas [sin,cos,tan,log])  ==  6

Leer más…

Un grafo no dirigido se representa por la lista de sus arcos. Por ejemplo, el grafo

1 -- 2 -- 4
| \  |
|  \ |
3 -- 5

se representa por [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)].

Se define el tipo de grafo por

type Grafo a = [(a,a)]

Definir las funciones

nodos      :: Eq a => Grafo a -> [a]
conectados :: Eq a => Grafo a -> a -> a -> Bool

tales que

• (nodos g) es la lista de los nodos del grafo g. Por ejemplo,

nodos [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)]  ==  [1,2,3,4,5]

• (conectados g x y) se verifica si el grafo no dirigido g posee un arco con extremos x e y. Por ejemplo,

conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 2  ==  True
conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2 3  ==  True
conectados [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 4  ==  False

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

Leer más…

Nota: En este ejercicio usaremos las mismas notaciones que en los anteriores importando los módulos Modelos_de_FNC y Evaluacion_de_FNC.

Una FNC (fórmula en forma normal conjuntiva) es satisfacible, si tiene algún modelo. Por ejemplo,

Definir la función

esSatisfacible :: FNC -> Bool

tal que (esSatisfacible f) se verifica si la FNC f es satistacible. Por ejemplo,

esSatisfacible [[-1,2],[-2,1]]    ==  True
esSatisfacible [[-1,2],[-2],[1]]  ==  False
esSatisfacible [[1,2],[]]         ==  False
esSatisfacible []                 ==  True

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

Leer más…

Nota: En este ejercicio usaremos las mismas notaciones que en anterior importando los módulos Interpretaciones_de_FNC y Evaluacion_de_FNC.

Una interpretación I es un modelo de un literal L si el valor de L en I es verdadero. Por ejemplo, la interpretación [2,5]

• es modelo del literal x(2) (porque 2 ∈ [2,5])
• no es modelo del literal x(3) (porque 3 ∉ [2,5])
• es modelo del literal -x(4) (porque 4 ∉ [2,5])

Una interpretación I es un modelo de una cláusula C si el valor de C en I es verdadero. Por ejemplo, la interpretación [2,5]

• es modelo de la cláusula (x(2) v x(3)) (porque x(2) es verdadero)
• no es modelo de la cláusula (x(3) v x(4)) (porque x(3) y x(4) son falsos)

Una interpretación I es un modelo de una FNC F si el valor de F en I es verdadero. Por ejemplo, la interpretación [2,5]

• es modelo de la FNC ((x(2) v x(5)) & (-x(4) v x(3)) porque lo es de sus dos cláusulas.

Definir las siguientes funciones

esModeloLiteral  :: Interpretacion -> Literal -> Bool
esModeloClausula :: Interpretacion -> Clausula -> Bool
esModelo         :: Interpretacion -> FNC -> Bool
modelosClausula  :: Clausula -> [Interpretacion]
modelos          :: FNC -> [Interpretacion]

tales que

• (esModeloLiteral i l) se verifica si i es modelo del literal l. Por ejemplo,

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

• (esModeloClausula i c) se verifica si i es modelo de la cláusula c. Por ejemplo,

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

• (esModelo i f) se verifica si i es modelo de la fórmula f. Por ejemplo,

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

• (modelosClausula c) es la lista de los modelos de la cláusula c. Por ejemplo,

modelosClausula [-1,2]  ==  [[],[2],[1,2]]
modelosClausula [-1,1]  ==  [[],[1]]
modelosClausula []      ==  []

• (modelos f) es la lista de los modelos de la fórmula f. Por ejemplo,

modelos [[-1,2],[-2,1]]    ==  [[],[1,2]]
modelos [[-1,2],[-2],[1]]  ==  []
modelos [[1,-1,2]]         ==  [[],[1],[2],[1,2]]

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

Leer más…

Nota: En este ejercicio usaremos las mismas notaciones que en los anteriores importando los módulos Evaluacion_de_FNC y Atomos_de_FNC.

Definir las siguientes funciones

interpretacionesClausula :: Clausula -> [Interpretacion]
interpretaciones         :: FNC -> [Interpretacion]

tales que

• (interpretacionesClausula c) es el conjunto de interpretaciones de la cláusula c. Por ejemplo,

interpretacionesClausula [1,2,-1]  ==  [[],[1],[2],[1,2]]
interpretacionesClausula []        ==  [[]]

• (interpretaciones f) es el conjunto de interpretaciones de la fórmula f. Por ejemplo,

interpretaciones [[1,-2],[-1,2]] == [[],[1],[2],[1,2]]
interpretaciones []              == [[]]

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

Leer más…

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…

La propiedad de la longitud de la parte periódica afirma que

Si p es un número primo distinto de 2 y de 5, entonces la longitud del período de 1/p es el menor entero positivo n tal que p divide a [latex]10^n - 1[/latex].

El objetivo de este ejercicio es la verificación de dicha propiedad.

Las fracciones se representan por un par de enteros. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

type Fraccion = (Integer,Integer)

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

 6/2  = 3                  se representa por (3,[],[])
 1/2  = 0.5                se representa por (0,[5],[])
 1/3  = 0.333333...        se representa por (0,[],[3])
23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

type Decimal = (Integer,[Integer],[Integer])

Definir, usando las funciones cocientesRestos y primerRepetido de los ejercicios anteriores, las funciones

decimal :: Fraccion -> Decimal
longitudPeriodo :: Fraccion -> Integer

tales que

• (decimal f) es la representación decimal de la fracción f. Por ejemplo,

decimal (6,2)          ==  (3,[],[])
decimal (3,4)          ==  (0,[7,5],[])
decimal (1,3)          ==  (0,[],[3])
decimal (23,14)        ==  (1,[6],[4,2,8,5,7,1])
decimal (247813,19980) ==  (12,[4,0],[3,0,5])
decimal (1,101)        ==  (0,[],[0,0,9,9])

• (longitudPeriodo f) es la longitud de la parte periódica de la representación decimal de la fracción f. Por ejemplo,

longitudPeriodo (6,2)           ==  0
longitudPeriodo (3,4)           ==  0
longitudPeriodo (1,3)           ==  1
longitudPeriodo (23,14)         ==  6
longitudPeriodo (247813,19980)  ==  3
longitudPeriodo (1,101)         ==  4
longitudPeriodo (1,1229)        ==  1228

Comprobar con QuickCheck la propiedad de la longitud de la parte periódica; es decir, k es un número natural distinto de 0 y 2 y p es el primo k-ésimo, entonces la longitud del período de 1/p es el menor entero positivo n tal que p divide a [latex]10^n - 1[/latex]..

Leer más…

La transformación de una fracción en un número decimal se realiza mediante una sucesión de divisiones. Por ejemplo, para transformar a decimal la fracción

 247813    |19980
-19980     ---------------
-------     12.40305305...
  48013
 -39960
 ------
   80530
  -79920
  ------
     6100
    -   0
    -----
     61000
    -59940
    ------
      10600
     -    0
     ------
      106000
     - 99900
     -------
        61000
        -59940
        ------
         10600
        -    0
        ------
        106000
       - 99900
       -------
         61000

La transformación anterior se puede representar mediante la siguiente lista de cocientes y restos

[(12,8053),(4,610),(0,6100),(3,1060),(0,10600),(5,6100),
                            (3,1060),(0,10600),(5,6100)]

Definir la función

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

tal que (cocientesRestos (n,d)) es la lista de los cocientes y restos de la transformación decimal de la fracción n/d como se ha indicado anteriormente. Por ejemplo,

λ> take 9 (cocientesRestos (247813,19980))
[(12,8053),(4,610),(0,6100),(3,1060),(0,10600),(5,6100),
(3,1060),(0,10600),(5,6100)]
λ> take 10 (cocientesRestos (6,2))
[(3,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0)]
λ> take 10 (cocientesRestos (1,2))
[(0,1),(5,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0)]
λ> take 10 (cocientesRestos (1,3))
[(0,1),(3,1),(3,1),(3,1),(3,1),(3,1),(3,1),(3,1),(3,1),(3,1)]
λ> take 10 (cocientesRestos (23,14))
[(1,9),(6,6),(4,4),(2,12),(8,8),(5,10),(7,2),(1,6),(4,4),(2,12)]

Leer más…

Definir la función

primerRepetido :: Eq a => [a] -> Maybe a

tal que (primerRepetido xs) es justo el primer elemento repetido de la lista xs o Nothing si no tiene elementos repetidos. Por ejemplo,

primerRepetido [3,7,5,7,2]  ==  Just 7
primerRepetido [3,9,5,6,2]  ==  Nothing

Leer más…

Un número entero n es libre de cuadrados si no existe un número primo p tal que p² divide a n; es decir, los factores primos de n son todos distintos.

La función de Möbius μ(n) está definida para todos los enteros positivos como sigue:

• μ(n) = 1 si n es libre de cuadrados y tiene un número par de factores primos.
• μ(n) = -1 si n es libre de cuadrados y tiene un número impar de factores primos.
• μ(n) = 0 si n no es libre de cuadrados.

Sus primeros valores son 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, ...

La función de Mertens M(n) está definida para todos los enteros positivos como la suma de μ(k) para 1 ≤ k ≤ n. Sus primeros valores son 1, 0, -1, -1, -2, -1, -2, -2, ...

La conjetura de Mertens afirma que

Para todo entero x mayor que 1, el valor absoluto de la función de Mertens en x es menor que la raíz cuadrada de x.

La conjetura fue planteada por Franz Mertens en 1897. Riele Odlyzko, demostraronen 1985 que la conjetura de Mertens deja de ser cierta más o menos a partir de \(10^{10^{64}}\), cifra que luego de algunos refinamientos se redujo a \(10^{10^{40}}\).

Definir las funciones

mobius :: Integer -> Integer
mertens :: Integer -> Integer
graficaMertens :: Integer -> IO ()

tales que

• (mobius n) es el valor de la función de Möbius en n. Por ejemplo,

mobius 6   ==  1
mobius 30  ==  -1
mobius 12  ==  0

• (mertens n) es el valor de la función de Mertens en n. Por ejemplo,

mertens 1     ==  1
mertens 2     ==  0
mertens 3     ==  -1
mertens 5     ==  -2
mertens 661   ==  -11
mertens 1403  ==  11

• (graficaMertens n) dibuja la gráfica de la función de Mertens, la raíz cuadrada y el opuestos de la raíz cuadrada para los n primeros n enteros positivos. Por ejemplo, (graficaMertens 1000) dibuja

Comprobar con QuickCheck la conjetura de Mertens.

Nota: El ejercicio está basado en La conjetura de Merterns y su relación con un número tan raro como extremada y colosalmente grande publicado por @Alvy la semana pasada en Microsiervos.

Leer más…

Definir la función

productoSuma4Cuadrados :: Integral a => [a] -> [a] -> [a] -> [a] -> a

tal que (productoSuma4Cuadrados as bs cs ds) es el producto de las sumas de los cuadrados de cada una de las listas que ocupan la misma posición (hasta que alguna se acaba). Por ejemplo,

productoSuma4Cuadrados [2,3] [1,5] [4,6] [0,3,9]
= (2² + 1² + 4² + 0²) * (3² + 5² + 6² + 3²)
= (4 +  1 + 16  + 0)  * (9 + 25 + 36  + 9)
= 1659

Comprobar con QuickCheckWith que si as, bs cs y ds son listas no vacías de enteros positivos, entonces (productoSuma4Cuadrados as bs cs ds) se puede escribir como la suma de los cuadrados de cuatro enteros positivos.

Leer más…

El número 42 es una suma de cuatro cuadrados de números enteros positivos ya que

42 = 16 + 16 + 9 + 1 = 4² + 4² + 3² + 1²

Definir las funciones

sumas4Cuadrados :: Integer -> [(Integer,Integer,Integer,Integer)]
graficaNumeroSumas4Cuadrados :: Integer -> IO ()

tales que

• (sumas4Cuadrados n) es la lista de las descompociones de n como suma de cuatro cuadrados. Por ejemplo,

sumas4Cuadrados 42  ==  [(16,16,9,1),(25,9,4,4),(36,4,1,1)]
sumas4Cuadrados 14  ==  []
length (sumas4Cuadrados (5*10^4))  ==  260

• (graficaNumeroSumas4Cuadrados n) dibuja la gráfica del número de descomposiciones en sumas de 4 cuadrados de los n primeros. Por ejemplo, (graficaNumeroSumas4Cuadrados 600) dibuja

Leer más…

Definir la sucesión

numerosSin2EnBase3a :: [Integer]

cuyos términos son los números cuya representación en base 3 no contiene el dígito 2. Por ejemplo,

λ> take 20 numerosSin2EnBase3
[0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,81,82,84,85]

Se observa que

• 12 está en la sucesión ya que su representación en base 3 es 110 (porque 1·3² + 1·3¹ + 0.3⁰ = 12) y no contiene a 2.
• 14 no está en la sucesión ya que su representación en base 3 es 112 (porque 1·3² + 1·3¹ + 2.3⁰ = 14) y contiene a 2.

Comprobar con QuickCheck que las sucesiones numerosSin2EnBase3 sucesionSin3enPA (del ejercicio anterior) son iguales; es decir, para todo número natural n, el n-ésimo término de numerosSin2EnBase3 es igual al n-ésimo término de sucesionSin3enPA.

Leer más…

Tres números x, y, z está en progresión aritmética (PA) si existe un d tal que y = x+d y z = y+d. Por ejemplo, 1, 3, 5 están en PA ya que 3 = 1+2 y 5 = 3+2.

Se considera la sucesión donde cada uno de sus términos es el número natural tal que no está en PA con cualesquiera dos términos anteriores de la sucesión. Por ejemplo, si representamos por f(n) el n-ésimo término de la sucesión, entonces

f(0) = 0, que es el menor número natural;
f(1) = 1, que es el menor número natural que no está en la sucesión;
f(2) = 3, ya que [0, 1, 2] están en PA y
                 [0, 1, 3] no están en PA;
f(3) = 4, ya que [0, 1, 4], [0, 3, 4] y [1, 3, 4] no están en PA;
f(4) = 9, ya que se descartan
          + el 5 porque [1, 3, 5] están en PA
          + el 6 porque [0, 3, 6] están en PA
          + el 7 porque [1, 4, 7] están en PA
          + el 8 porque [0, 4, 8] estan en PA
          y se acepta el 9 porque no están en PA niguna de [0,1,9],
          [0,3,9], [0,4,9], [1,3,9], [1,4,9], [3,4,9].

Definir la sucesión

sucesionSin3enPA :: [Integer]

donde cada uno de sus términos es el menor número natural tal que no está en PA con cualesquiera dos términos anteriores de la sucesión. Por ejemplo,

λ> take 20 sucesionSin3enPA
[0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,81,82,84,85]
λ> sucesionSin3enPA !! 250
3270

Leer más…

La conjetura de Goldbach afirma que todo número entero mayor que 2 se puede expresar como suma de dos primos.

Las descomposiciones de Goldbach son las maneras de expresar un número como suma de dos primos. Por ejemplo, el número 10 tiene dos descomposiciones de Goldbach ya que se puede expresar como la suma de 3 y 7 y la suma de 5 y 5.

Definir las funciones

descomposicionesGoldbach :: Integer -> [(Integer,Integer)]
numeroGoldbach :: Integer -> Integer
tieneMaximoLocalGoldbach :: Integer -> Bool

tales que

• (descomposicionesGoldbach n) es la lista de las descomposiciones de Goldbach del número n. Por ejemplo,

descomposicionesGoldbach 5   ==  [(2,3)]
descomposicionesGoldbach 10  ==  [(3,7),(5,5)]
descomposicionesGoldbach 22  ==  [(3,19),(5,17),(11,11)]
descomposicionesGoldbach 34  ==  [(3,31),(5,29),(11,23),(17,17)]
descomposicionesGoldbach 35  ==  []
descomposicionesGoldbach (9+10^9)  ==  [(2,1000000007)]

• (numeroGolbach n) es el número de descomposiciones de Goldbach del número n. Por ejemplo,

numeroGoldbach 5         ==  1
numeroGoldbach 10        ==  2
numeroGoldbach 22        ==  3
numeroGoldbach 34        ==  4
numeroGoldbach 35        ==  0
numeroGoldbach (9+10^9)  ==  1
maximum [numeroGoldbach n | n <- [2..3000]]  ==  128

• (tieneMaximoLocalGoldbach n) se verifica si en n se alcanza un máximo local en el número de descomposiciones de Goldbach; es decir, los números n tales que el número de descomposiciones de Goldbach de n es mayor o igual que las de n-1 y las de n+1. Por ejemplo,

λ> filter tieneMaximoLocalGoldbach [1..45]
[1,2,4,5,6,7,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44]

En el ejemplo anterior se comprueba que en los múltiplos de 6 (es decir, en 6, 12, 18, 24, 30, 36 y 42), el número de descomposiciones de Goldbach alcanza un máximo local. Comprobar con QuickCheck que esta propiedad se cumple en general; es decir, para todo entero positivo n, el número de descomposiciones de Goldbach en 6n es un máximo local.

Leer más…

El teorema de la amistad afirma que

En cualquier reunión de n personas hay al menos dos personas que tienen el mismo número de amigos (suponiendo que la relación de amistad es simétrica).

Se pueden usar las siguientes representaciones:

• números enteros para representar a las personas,
• pares de enteros (x,y), con x < y, para representar que la persona x e y so amigas y
• lista de pares de enteros para representar la reunión junto con las relaciones de amistad.

Por ejemplo, [(2,3),(3,5)] representa una reunión de tres personas (2, 3 y 5) donde

• 2 es amiga de 3,
• 3 es amiga de 2 y 5 y
• 5 es amiga de 3. Si clasificamos las personas poniendo en la misma clase las que tienen el mismo número de amigos, se obtiene [[2,5],[3]] ya que 2 y 5 tienen 1 amigo y 3 tiene 2 amigos.

Definir la función

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

tal que (clasesAmigos r) es la clasificación según el número de amigos de las personas de la reunión r; es decir, la lista cuyos elementos son las listas de personas con 1 amigo, con 2 amigos y así hasta que se completa todas las personas de la reunión r. Por ejemplo,

clasesAmigos [(2,3),(3,5)]            ==  [[2,5],[3]]
clasesAmigos [(2,3),(4,5)]            ==  [[2,3,4,5]]
clasesAmigos [(2,3),(2,5),(3,5)]      ==  [[2,3,5]]
clasesAmigos [(2,3),(3,4),(2,5)]      ==  [[4,5],[2,3]]
clasesAmigos [(x,x+1) | x <- [1..5]]  ==  [[1,6],[2,3,4,5]]
length (clasesAmigos [(x,x+1) | x <- [1..2020]]) == 2

Comprobar con QuickCheck el teorema de la amistad; es decir, si r es una lista de pares de enteros, entonces (clasesAmigos r') donde r' es la lista de los pares (x,y) de r con x < y y se supone que r' es no vacía.

Leer más…

Definir las funciones

multiplosDeLaLongitud :: [Int] -> [Int]
multiplosDeLaLongitudDeConsecutivos :: Int -> Int -> [Int]

tales que

• (multiplosDeLaLongitud xs) es la lista de los elementos de xs que son múltiplos de la longitud de xs. Por ejemplo,

multiplosDeLaLongitud [2,4,6,8] == [4,8]

• (multiplosDeLaLongitudDeConsecutivos n m) es la lista de elementos de [n..n+m-1] que son múltiplos de n. Por ejemplo,

multiplosDeLaLongitudDeConsecutivos 9 2  ==  [10]
multiplosDeLaLongitudDeConsecutivos 9 12 ==  [12]

Comprobar con QuickCheck si se verifican las siguientes propiedades

• En cualquier conjunto de m elementos consecutivos, m divide exactamente a uno de dichos elementos. En otras palabras, si n y m son enteros positivos, entonces (multiplosDeLaLongitudDeConsecutivos n m) tiene exactamente un elemento.
• Si n es un entero positivo y m >= n, entonces (multiplosDeLaLongitudDeConsecutivos n m) es igual a [m]
• Si n y n son enteros positivos y m < n, entonces (multiplosDeLaLongitudDeConsecutivos n m) es igual a [m * ceiling (n' / m')] donde n' y m' son las formas decimales de n y m respectivamente.

Leer más…

La conjetura de Catalan, enunciada en 1844 por Eugène Charles Catalan y demostrada 2002 por Preda Mihăilescu1, afirma que

Las únicas dos potencias de números enteros consecutivos son 8 y 9 (que son respectivamente 2³ y 3²).

En otras palabras, la única solución entera de la ecuación

x^a - y^b = 1

para x, a, y, b > 1 es x = 3, a = 2, y = 2, b = 3.

La conjetura de Pillai, propuesta por S.S. Pillai en 1942, generaliza este resultado y es un problema abierto. Afirma que cada entero se puede escribir sólo un número finito de veces como una diferencia de dos potencias perfectas. En otras palabras, para todo entero positivo n, el conjunto de soluciones de

x^a - y^b = n

para x, a, y, b > 1 es finito.

Por ejemplo, para n = 4, hay 3 soluciones

(2,3, 2,2) ya que 2³ -  2² =   8 -   4 = 4
(6,2, 2,5) ya que 6² -  2⁵ =  36 -  32 = 4
(5,3,11,2) ya que 5³ - 11² = 125 - 121 = 4

Las soluciones se pueden representar por la menor potencia (en el caso anterior, por 4, 32 y 121) ya que dado n (en el caso anterior es 4), la potencia mayor es la menor más n.

Definir las funciones

potenciasPerfectas :: [Integer]
solucionesPillati :: Integer -> [Integer]
solucionesPillatiAcotadas :: Integer -> Integer -> [Integer]

tales que

• potenciasPerfectas es la lista de las potencias perfectas (es decir, de los números de la forma x^a con x y a mayores que 1). Por ejemplo,

take 10 potenciasPerfectas  ==  [4,8,9,16,25,27,32,36,49,64]
potenciasPerfectas !! 200   ==  28224

• (solucionesPillati n) es la lista de las menores potencias de las soluciones de la ecuación de Pillati x^a - y^b = n; es decir, es la lista de los u tales que u y u+n son potencias perfectas. Por ejemplo,

take 3 (solucionesPillati 4)  ==  [4,32,121]
take 2 (solucionesPillati 5)  ==  [4,27]
take 4 (solucionesPillati 7)  ==  [9,25,121,32761]

• (solucionesPillatiAcotadas c n) es la lista de elementos de (solucionesPillati n) menores que n. Por ejemplo,

solucionesPillatiAcotadas (10^3) 1  ==  [8]
solucionesPillatiAcotadas (10^3) 2  ==  [25]
solucionesPillatiAcotadas (10^3) 3  ==  [125]
solucionesPillatiAcotadas (10^3) 4  ==  [4,32,121]
solucionesPillatiAcotadas (10^3) 5  ==  [4,27]
solucionesPillatiAcotadas (10^3) 6  ==  []
solucionesPillatiAcotadas (10^3) 7  ==  [9,25,121]
solucionesPillatiAcotadas (10^5) 7  ==  [9,25,121,32761]

Leer más…

La 40ª Conferencia General de la UNESCO ha proclamado el de enero el Día mundial de la Lógica. La fecha del 14 de enero se ha eligido para rendir homenaje a dos grandes lógicos del siglo XX: Kurt Gödel (que falleció el 14 de enero de 1978) y Alfred Tarski (que nació el 14 de enero de 1901).

Gödel demostró en 1931 los teoremas de incompletitud y para su demostración introdujo la actualmente conocida como codificación de Gödel que asigna a cada fórmula de un lenguaje formal un número único.

En este ejercicio aplicaremos la codificación de Gödel a las listas de números enteros.

Dada una lista de números naturales xs, la codificación de Gödel de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los sucesores de los elementos de xs. Por ejemplo, si xs es [6,0,4], la codificación de xs es

2^(6+1) * 3^(0+1) * 5^(4+1) = 1200000

Definir las funciones

codificaG   :: [Integer] -> Integer
decodificaG :: Integer -> [Integer]

tales que

• (codificaG xs) es la codificación de Gödel de xs. Por ejemplo,

codificaG [6,0,4]            ==  1200000
codificaG [3,1,1]            ==  3600
codificaG [3,1,0,0,0,0,0,1]  ==  4423058640
codificaG [1..6]             ==  126111168580452537982500

• (decodificaG n) es la lista xs cuya codificación es n. Por ejemplo,

decodificaG 1200000                   ==  [6,0,4]
decodificaG 3600                      ==  [3,1,1]
decodificaG 4423058640                ==  [3,1,0,0,0,0,0,1]
decodificaG 126111168580452537982500  ==  [1,2,3,4,5,6]

Comprobar con QuickCheck que decodificaG es la inversa por la izquierda de codificaG; es decir, para toda lista xs de números enteros, se verifica que

decodificaG (codificaG ys) == ys

donde ys es la lista de los valores absolutos de los elementos de xs.

Leer más…

Un número de Munchausen es un número entero positivo tal que es igual a la suma de sus dígitos elevados a sí mismo. Por ejemplo, 3435 es un número de Munchausen ya que

3³ + 4⁴ + 3³ + 5⁵ = 27 + 256 + 27 + 3125 = 3435

Definir la función

esMunchausen :: Integer -> Bool

tal que (esMunchausen n) se verifica si n es un número de Munchausen. Por ejemplo,

esMunchausen 3435  ==  True
esMunchausen 2020  ==  False

Comprobar con QuickCheck que que los únicos números de Munchausen son 1 y 3435.

Nota 1: No usar la propiedad en la definición.

Nota 2: El ejercicio está basado en el artículo ¿Por qué 3435 es uno de mis números favoritos? de Miguel Ángel Morales en El Aleph.

Leer más…

El teorema de existencia de divisores afirma que

En cualquier subconjunto de {1, 2, ..., 2m} con al menos m+1 elementos existen números distintos a, b tales que a divide a b.

Un conjunto de números naturales xs es mayoritario si existe un m tal que la lista de xs es un subconjunto de {1,2,...,2m} con al menos m+1 elementos. Por ejemplo, {2,3,5,6} porque es un subconjunto de {1,2,...,6} con más de 3 elementos.

Definir las funciones

divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
esMayoritario :: [Integer] -> Bool

tales que

• (divisores xs) es la lista de pares de elementos distintos de (a,b) tales que a divide a b. Por ejemplo,

divisoresMultiplos [2,3,5,6]  ==  [(2,6),(3,6)]
divisoresMultiplos [2,3,5]    ==  []
divisoresMultiplos [4..8]     ==  [(4,8)]

• (esMayoritario xs) se verifica xs es mayoritario. Por ejemplo,

esMayoritario [2,3,5,6]  ==  True
esMayoritario [2,3,5]    ==  False

Comprobar con QuickCheck el teorema de existencia de divisores; es decir, en cualquier conjunto mayoritario existen números distintos a, b tales que a divide a b. Para la comprobación se puede usar el siguiente generador de conjuntos mayoritarios

mayoritario :: Gen [Integer]
mayoritario = do
  m' <- arbitrary
  let m = 1 + abs m'
  xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
  return xs'

con lo que la propiedad que hay que comprobar con QuickCheck es

teorema_de_existencia_de_divisores :: Property
teorema_de_existencia_de_divisores =
  forAll mayoritario (not . null . divisoresMultiplos)

Leer más…

El problema de Waring, propuesto por Edward Waring consiste en determinar si, para cada número entero k mayor que 1, existe un número n tal que todo entero positivo se puede escribir como una suma de k-potencias de números positivos con n sumandos como máximo.

La respuesta afirmativa al problema, aportada por David Hilbert, se conoce como el teorema de Hilbert-Waring. Su enunciado es

Para cada número entero k, con k ≥ 2, existe un entero positivo g(k) tal que todo entero positivo se puede expresar como una suma de a lo más g(k) k-ésimas potencias.

Definir las funciones

descomposiciones :: Integer -> Integer -> Integer -> [[Integer]]
orden :: Integer -> Integer -> Integer

tales que

• (descomposiciones x k n) es la lista de descomposiciones de x como suma de n potencias con exponente k de números enteros positivos.

descomposiciones 9   2 1  ==  [[9]]
descomposiciones 9   3 1  ==  []
descomposiciones 9   3 2  ==  [[1,8]]
descomposiciones 9   4 9  ==  [[1,1,1,1,1,1,1,1,1]]
descomposiciones 25  2 2  ==  [[9,16]]
descomposiciones 133 2 3  ==  [[8,125]]
descomposiciones 38  3 2  ==  [[1,1,36],[4,9,25]]

• (orden x k) es el menor número de sumandos necesario para expresar x como suma de k-ésimas potencias. Por ejemplo,

orden 9  2  ==  1
orden 9  3  ==  2
orden 9  4  ==  9
orden 10 2  ==  2
orden 10 3  ==  3
orden 10 4  ==  10
[maximum [orden x k | x <- [1..1000]] | k <- [1..6]] == [1,4,9,19,37,73]

Comprobar el teorema de Hilbert-Waring para k hasta 7; es decir, para todo número x positivo se verifica que

orden x 2 <= 4
orden x 3 <= 9
orden x 4 <= 19
orden x 5 <= 37
orden x 6 <= 73
orden x 7 <= 143

y, en general,

orden x k <= 2^k + floor ((3/2)^k) - 2

Leer más…

Dos números enteros son coprimos (o primos entre sí) si no tienen ningún factor primo en común. Por ejemplo, 4 y 15 son coprimos.

Una terna coprima es una terna (a,b,c) tal que

• a y b son coprimos,
• a y c son coprimos y
• b y c son coprimos.

Por ejemplo, (3,4,5) es una terna coprima.

Definir la función

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

tal que (sumas3coprimos n) es la lista de las ternas coprimas cuya suma es n. Por ejemplo,

sumas3coprimos 10  ==  [(2,3,5)]
sumas3coprimos 11  ==  []
sumas3coprimos 12  ==  [(2,3,7),(3,4,5)]
length (sumas3coprimos 4000)  ==  546146

Comprobar con QuickCheck que todo número entero mayor que 15 se puede escribir como suma de alguna terna coprima; es decir, para todo entero n, (sumas3coprimos2 (18 + abs n)) tiene algún elemento.

Leer más…

Para cada número entero positivo n, se define el conjunto

S(n) = {1, 2, 3, ..., n}

de los números desde el 1 hasta n.

Definir la función

mayorPotenciaDeDosEnS :: Integer -> Integer

tal que (mayorPotenciaDeDosEnS n) es la mayor potencia de 2 en S(n). Por ejemplo,

mayorPotenciaDeDosEnS 3  ==  2
mayorPotenciaDeDosEnS 4  ==  4

Comprobar con QuickCheck que la mayor potencia de 2 en S(n) no divide a ningún otro elemento de S(n).

Leer más…

Sea S el conjunto

S = {1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, ...}

de los enteros positivos congruentes con 1 módulo 4; es decir,

S = {4n+1 | n ∈ N}

Un elemento n de S es irreducible si sólo es divisible por dos elementos de S: 1 y n. Por ejemplo, 9 es irreducible; pero 45 no lo es (ya que es el proctos de 5 y 9 que son elementos de S).

Definir las funciones

esIrreducible :: Integer -> Bool
factorizaciones :: Integer -> [[Integer]]
conFactorizacionNoUnica :: [Integer]

tales que

• (esIrreducible n) se verifica si n es irreducible. Por ejemplo,

esIrreducible 9   ==  True
esIrreducible 45  ==  False

• (factorizaciones n) es la lista de conjuntos de elementos irreducibles de S cuyo producto es n. Por ejemplo,

factorizaciones 9     ==  [[9]]
factorizaciones 693   ==  [[9,77],[21,33]]
factorizaciones 4389  ==  [[21,209],[33,133],[57,77]]

• conFactorizacionNoUnica es la lista de elementos de S cuya factorización no es única. Por ejemplo,

λ> take 10 conFactorizacionNoUnica
[441,693,1089,1197,1449,1617,1881,1953,2205,2277]

Leer más…

Una lista CuCu es una lista de números enteros positivos tales que la suma de sus Cubos es igual al Cuadrado de su suma. Por ejemplo, [1, 2, 3, 2, 4, 6] es una lista CuCu ya que

1³ + 2³ + 3³ + 2³ + 4³ + 6³ = (1 + 2 + 3 + 2 + 4 + 6)²

La lista de Liouville correspondiente al número entero positivo n es la lista formada por el número de divisores de cada divisor de n. Por ejemplo, para el número 20 se tiene que sus divisores son

1, 2, 4, 5, 10, 20

puesto que el número de sus divisores es

• El 1 tiene 1 divisor (el 1 solamente).
• El 2 tiene 2 divisores (el 1 y el 2).
• El 4 tiene 3 divisores (el 1, el 2 y el 4).
• El 5 tiene 2 divisores (el 1 y el 5).
• El 10 tiene 4 divisores (el 1, el 2, el 5 y el 10).
• El 20 tiene 6 divisores (el 1, el 2, el 4, el 5, el 10 y el 20).

la lista de Liouville de 20 es [1, 2, 3, 2, 4, 6] que, como se comentó anteriormente, es una lista CuCu.

El teorema de Lioville afirma que todas las lista de Lioville son CuCu.

Definir las funciones

esCuCu :: [Integer] -> Bool
liouville :: Integer -> [Integer]

tales que

• (esCuCu xs) se verifica si la lista xs es CuCu; es decir, la suma de los cubos de sus elementos es igual al cuadrado de su suma. Por ejemplo,

esCuCu [1,2,3]        ==  True
esCuCu [1,2,3,2]      ==  False
esCuCu [1,2,3,2,4,6]  ==  True

• (liouville n) es la lista de Lioville correspondiente al número n. Por ejemplo,

liouville 20  ==  [1,2,3,2,4,6]
liouville 60  ==  [1,2,2,3,2,4,4,6,4,6,8,12]
length (liouville (product [1..25]))  ==  340032

Comprobar con QuickCheck

• que para todo entero positivo n, (liouville (2^n)) es la lista [1,2,3,...,n+1] y
• el teorema de Lioville; es decir, para todo entero positivo n, (liouville n) es una lista CuCu.

Nota: Este ejercicio está basado en Cómo generar conjuntos CuCu de Gaussianos.

Leer más…

La conjetura de Grimm establece que a cada elemento de un conjunto de números compuestos se puede asignar número primo que lo divide, de forma que cada uno de los números primos elegidos es distinto de todos los demás. Más formalmente, si n+1, n+2, ..., n+k son números compuestos, entonces existen números primos p(i), distintos entre sí, tales que p(i) divide a n+i para 1 ≤ i ≤ k.

Diremos que la lista ps = [p(1),...,p(k)] es una sucesión de Grim para la lista xs = [x(1),...,x(k)] si p(i) son números primos distintos y p(i) divide a x(i), para 1 ≤ i ≤ k. Por ejemplo, 2, 5, 13, 3, 7 es una sucesión de Grim de 24, 25, 26, 27, 28.

Definir las funciones

compuestos :: Integer -> [Integer]
sucesionesDeGrim :: [Integer] -> [[Integer]]

tales que

• (compuestos n) es la mayor lista de números enteros consecutivos empezando en n. Por ejemplo,

compuestos 24  ==  [24,25,26,27,28]
compuestos  8  ==  [8,9,10]
compuestos 15  ==  [15,16]
compuestos 16  ==  [16]
compuestos 17  ==  []

• (sucesionesDeGrim xs) es la lista de las sucesiones de Grim de xs. Por ejemplo,

sucesionesDeGrim [15,16]          == [[3,2],[5,2]]
sucesionesDeGrim [8,9,10]         == [[2,3,5]]
sucesionesDeGrim [9,10]           == [[3,2],[3,5]]
sucesionesDeGrim [24,25,26,27,28] == [[2,5,13,3,7]]
sucesionesDeGrim [25,26,27,28]    == [[5,2,3,7],[5,13,3,2],[5,13,3,7]]

Comprobar con QuickCheck la conjetura de Grim; es decir, para todo número n > 1, (sucesionesDeGrim (compuestos n)) es una lista no vacía.

Leer más…

La sucesión de Fibonacci, F(n), es la siguiente sucesión infinita de números naturales:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

La sucesión comieanza con los números 0 y 1. A partir de estos, cada término es la suma de los dos anteriores.

El teorema de Carmichael establece que para todo n mayor que 12, el n-ésimo número de Fibonacci F(n) tiene al menos un factor primo que no es factor de ninguno de los términos anteriores de la sucesión.

Si un número primo p es un factor de F(n) y no es factor de ningún F(m) con m < n, entonces se dice que p es un factor característico o un divisor primitivo de F(n).

Definir la función

factoresCaracteristicos :: Int -> [Integer]

tal que (factoresCaracteristicos n) es la lista de los factores característicos de F(n). Por ejemplo,

factoresCaracteristicos  4  ==  [3]
factoresCaracteristicos  6  ==  []
factoresCaracteristicos 19  ==  [37,113]
factoresCaracteristicos 37  ==  [73,149,2221]

Comprobar con QuickCheck el teorema de Carmichael; es decir, para todo número entero (factoresCaracteristicos (13 + abs n)) es una lista no vacía.

Leer más…

La derivada aritmética es una función definida sobre los números naturales por analogía con la regla del producto para el cálculo de las derivadas usada en análisis.

Para un número natural n su derivada D(n) se define por

D(0)  = 0
D(1)  = 0
D(p)  = 1, si p es primo
D(ab) = D(a)b + aD(b) (regla de Leibniz para derivar productos)

Por ejemplo,

D(6)  = D(2*3) = D(2)*3 + 2*D(3) = 1*3 + 2*1 =  5
D(12) = D(2*6) = D(2)*6 + 2*D(6) = 1*6 + 2*5 = 16

Definir la función

derivada :: Integer -> Integer

tal que (derivada n) es la derivada aritmérica de n. Por ejemplo,

derivada  6  ==  5
derivada 12  ==  16
maximum [derivada n | n <- [1..60000]]  ==  380928

Comprobar con QuickCheck que si x es un número entero positivo y su descomposición en factores primos es

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

entonces la derivada de x es

x * [e(1)/p(1) + e(2)/p(2) +...+ e(n)/p(n)]

Nota: No usar en la definición la propiedad que hay que comprobar.

Leer más…

El postulado de Bertrand afirma que para cualquier número entero n > 1, existe al menos un número primo p con n < p < 2n.

Definir la función

siguientePrimo :: Integer -> Integer

tal que (siguientePrimo n) es el menor primo mayor que n. Por ejemplo,

siguientePrimo 8   ==  11
siguientePrimo 11  ==  13

Comprobar con QuickCheck el postulado de Bertrand; es decir, para todo entero n > 1, se verifica que n < p < 2n, donde p es (siguientePrimo n).

Leer más…

En un ejercicio anterior se mostró que los conjuntos finitos de números naturales se pueden enumerar como sigue

 0: []
 1: [0]
 2: [1]
 3: [1,0]
 4: [2]
 5: [2,0]
 6: [2,1]
 7: [2,1,0]
 8: [3]
 9: [3,0]
10: [3,1]
11: [3,1,0]
12: [3,2]
13: [3,2,0]
14: [3,2,1]
15: [3,2,1,0]
16: [4]
17: [4,0]
18: [4,1]
19: [4,1,0]

en la que los elementos están ordenados de manera decreciente.

Además, se definió la constante

enumeracionCFN :: [[Integer]]

tal que sus elementos son los conjuntos de los números naturales con la ordenación descrita anteriormente. Por ejemplo,

λ> take 20 enumeracionCFN
[[],
 [0],
 [1],[1,0],
 [2],[2,0],[2,1],[2,1,0],
 [3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0],
 [4],[4,0],[4,1],[4,1,0]]

Definir la función

posicion :: [Integer] -> Integer

tal que (posicion xs) es la posición del conjunto finito de números naturales xs, representado por una lista decreciente, en enumeracionCFN. Por ejemplo,

posicion [2,0]          ==  5
posicion [2,1]          ==  6
posicion [2,1,0]        ==  7
posicion [0]            ==  1
posicion [1,0]          ==  3
posicion [2,1,0]        ==  7
posicion [3,2,1,0]      ==  15
posicion [4,3,2,1,0]    ==  31
posicion [5,4,3,2,1,0]  ==  63

Comprobar con QuickCheck que para todo número natural n,

posicion [n,n-1..0] == 2^(n+1) - 1.

Leer más…

Dado un conjunto de números naturales, por ejemplo A = {0, 2, 3, 4}, calculamos las sumas de todos los pares de elementos de A. Como A tiene 4 elementos hay 16 pares, pero no todas sus sumas son distintas. En este caso solo hay 8 sumas distintas: {0, 2, 3, 4, 5, 6, 7, 8}. Procediendo análogamente hay 9 diferencias distinatas entre los pares de A: {-4, -3, -2, -1, 0, 1, 2, 3, 4}.

Experimentando con más conjuntos, se puede conjeturar que el número de restas es mayor que el de sumas y argumentar que que mientras que con dos números distintos sólo se produce una suma distints sin embargo se producen dos restas distintas. Por ejemplo, con 5 y 7 sólo se produce una suma (ya que 5+7 y 7+5 ambos dan 12) pero dos restas (ya que 5-7 y 7-5 dan -2 y 2, respectivamente).

Sin embargo, la conjetura es falsa. Un contraejemplo en el conjunto {0, 2, 3, 4, 7, 11, 12, 14}, que tiene 26 sumas distintas con sus pares de elementos pero sólo 25 restas.

Los conjuntos con más sumas distintas con sus pares de elementos que restas se llaman conjuntos MSQR (por "más sumas que restas").

El objetivo de este ejercicio es calcular los conjuntos MSQR.

Definir las funciones

tieneMSQR :: [Integer] -> Bool
conjuntosMSQR :: [[Integer]]

tales que

• (tieneMSQR xs) se verifica si el conjunto xs tiene más sumas que restas. Por ejemplo,

tieneMSQR [0, 2, 3, 4]                 ==  False
tieneMSQR [0, 2, 3, 4, 7, 11, 12, 14]  ==  True

• conjuntosMSQR es la lista de los conjuntos MSQR. Por ejemplo,

λ> take 5 conjuntosMSQR
[[14,12,11,7,4,3,2,0],
 [14,12,11,10,7,3,2,0],
 [14,13,12,9,5,4,2,1,0],
 [14,13,12,10,9,5,2,1,0],
 [15,13,12,8,5,4,3,1]]

 length (takeWhile (< [14]) conjuntosMSQR)   ==  0
 length (takeWhile (< [15]) conjuntosMSQR)   ==  4
 length (takeWhile (< [16]) conjuntosMSQR)   ==  10
 length (takeWhile (< [17]) conjuntosMSQR)   ==  30

Leer más…

Los conjuntos finitos de números naturales se pueden enumerar como sigue

 0: []
 1: [0]
 2: [1]
 3: [1,0]
 4: [2]
 5: [2,0]
 6: [2,1]
 7: [2,1,0]
 8: [3]
 9: [3,0]
10: [3,1]
11: [3,1,0]
12: [3,2]
13: [3,2,0]
14: [3,2,1]
15: [3,2,1,0]
16: [4]
17: [4,0]
18: [4,1]
19: [4,1,0]

en la que los elementos están ordenados de manera decreciente.

Definir la constante

enumeracionCFN :: [[Integer]]

tal que sus elementos son los conjuntos de los números naturales con la ordenación descrita anteriormente. Por ejemplo,

λ> take 20 enumeracionCFN
[[],
 [0],
 [1],[1,0],
 [2],[2,0],[2,1],[2,1,0],
 [3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0],
 [4],[4,0],[4,1],[4,1,0]]

Comprobar con QuickCheck que

• si (xs,ys) es un par de elementos consecutivos de enumeracionCFN, entonces xs < ys;
• todo conjunto finito de números naturales, representado por una lista decreciente, está en enumeracionCFN.

Leer más…

Un par de números primos (p,q) es un par de números primos gemelos si su distancia de 2; es decir, si q = p+2. Por ejemplo, (17,19) es una par de números primos gemelos.

La conjetura de los primos gemelos postula la existencia de infinitos pares de primos gemelos.

Definir la constante

primosGemelos :: [(Integer,Integer)]

tal que sus elementos son los pares de primos gemelos. Por ejemplo,

λ> take 7 primosGemelos
[(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61)]
λ> primosGemelos !! (4*10^4)
(6381911,6381913)

Comprobar con QuickCheck la conjetura de los primos gemelos.

Leer más…

La sucesión de Fibonacci, F(n), es la siguiente sucesión infinita de números naturales:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

La sucesión comienza con los números 0 y 1. A partir de estos, cada término es la suma de los dos anteriores.

Definir la función

sumaFibsIndiceImpar :: Int -> Integer

tal que (sumaFibsIndiceImpar n) es la suma de los n primeros términos de la sucesión de Fibonacci no índice impar; es decir,

sumaFibsIndiceImpar n = F(1) + F(3) + ... + F(2*n-1)

Por ejemplo,

sumaFibsIndiceImpar 1  ==  1
sumaFibsIndiceImpar 2  ==  3
sumaFibsIndiceImpar 3  ==  8
sumaFibsIndiceImpar 4  ==  21
sumaFibsIndiceImpar 5  ==  55
sumaFibsIndiceImpar (10^4) `rem` (10^9)  ==  213093125

En los ejemplos anteriores se observa que

sumaFibsIndiceImpar 1  ==  F(2)
sumaFibsIndiceImpar 2  ==  F(4)
sumaFibsIndiceImpar 3  ==  F(6)
sumaFibsIndiceImpar 4  ==  F(8)
sumaFibsIndiceImpar 5  ==  F(10)

Comprobar con QuickCheck que (sumaFibsIndiceImpar n) es F(2n); es decir, el 2n-ésimo número de Fibonacci

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