Definir la función

mayoresCrecientes :: Ord a => [a] -> [[a]]

tal que (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs de mayor longitud. Por ejemplo,

λ> mayoresCrecientes [3,2,6,4,5,1]
[[3,4,5],[2,4,5]]
λ> mayoresCrecientes [3,2,3,2,3,1]
[[2,3],[2,3],[2,3]]
λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]
[[10,22,33,50,60,80],[10,22,33,41,60,80]]
λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
[[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]
λ> length (head (mayoresCrecientes (show (2^300))))
10

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…

Una partición prima de un número natural n es un conjunto de primos cuya suma es n. Por ejemplo, el número 7 tiene 7 particiones primas ya que

7 = 7 = 5 + 2 = 3 + 2 + 2

Definir la función

particiones :: Int -> [[Int]]

tal que (particiones n) es el comjunto de las particiones primas de n. Por ejemplo,

particiones 7             ==  [[7],[5,2],[3,2,2]]
particiones 8             ==  [[5,3],[3,3,2],[2,2,2,2]]
particiones 9             ==  [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]
length (particiones 100)  ==  40899

Leer más…

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

sylvester        :: Integer -> Integer
graficaSylvester :: Integer -> Integer -> IO ()

tales que

• (sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,

λ> [sylvester n | n <- [0..7]]
[2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]
λ> length (show (sylvester 25))
6830085

• (graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
• (graficaSylvester 3 30) dibuja
• (graficaSylvester 4 30) dibuja
• (graficaSylvester 5 30) dibuj4

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

(  1  6 11  2 )
(  7 12  3  8 )
(  3  8  4  9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El camino de máxima suma es el segundo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

caminoMaxSuma :: Matrix Int -> [Int]

tal que (caminoMaxSuma m) es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[1,7,12,8,4,9]
λ> sum (caminoMaxSuma (fromList 500 500 [1..]))
187001249

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

(  1  6 11  2 )
(  7 12  3  8 )
(  3  8  4  9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El máximo de las suma de los caminos es 41.

Definir la función

maximaSuma :: Matrix Int -> Int

tal que (maximaSuma m) es el máximo de las sumas de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
41
λ> maximaSuma (fromList 800 800 [1..])
766721999

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

(  1  6 11  2 )
(  7 12  3  8 )
(  3  8  4  9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Definir la función

caminos :: Matrix Int -> [[Int]]

tal que (caminos m) es la lista de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[[1,7, 3,8,4,9],
[1,7,12,8,4,9],
[1,7,12,3,4,9],
[1,7,12,3,8,9],
[1,6,12,8,4,9],
[1,6,12,3,4,9],
[1,6,12,3,8,9],
[1,6,11,3,4,9],
[1,6,11,3,8,9],
[1,6,11,2,8,9]]
λ> length (caminos (fromList 12 13 [1..]))
1352078

Leer más…

Las árboles binarios se pueden representar con el siguiente tipo

data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving Show

Por ejemplo, el árbol

    1
   / \
  2   3
 / \
4   5

se representa por

ej1 :: Arbol Int
ej1 = N 1 (N 2 (N 4 H H) (N 5 H H)) (N 3 H H)

La altura de cada elemento del árbol es la máxima distancia a las hojas en su rama. Por ejemplo, en el árbol anterior, la altura de 1 es 3, la de 2 es 2, la de 3 es 1, la de 4 es 1 y la de 5 es 1.

Definir la función

sumaAlturas :: Arbol t -> Int

tal que (sumaAlturas a) es la suma de las alturas de los elementos de a. Por ejemplo,

λ> sumaAlturas (N 1 (N 2 (N 4 H H) (N 5 H H)) (N 3 H H))
8
λ> sumaAlturas (N 1 (N 2 (N 4 H H) H) (N 3 H H))
7
λ> sumaAlturas (N 1 (N 2 (N 4 H H) H) (N 2 (N 4 H H) (N 5 H H)))
10

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…

El triángulo de Pascal es un triángulo de números

       1
      1 1
     1 2 1
   1  3 3  1
  1 4  6  4 1
 1 5 10 10 5 1
...............

construido de la siguiente forma

• la primera fila está formada por el número 1;
• las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

La matriz de Pascal es la matriz cuyas filas son los elementos de la correspondiente fila del triángulo de Pascal completadas con ceros. Por ejemplo, la matriz de Pascal de orden 6 es

|1 0  0  0 0 0|
|1 1  0  0 0 0|
|1 2  1  0 0 0|
|1 3  3  1 0 0|
|1 4  6  4 1 0|
|1 5 10 10 5 1|

Definir la función

matrizPascal :: Int -> Matrix Integer

tal que (matrizPascal n) es la matriz de Pascal de orden n. Por ejemplo,

λ> matrizPascal 6
(  1  0  0  0  0  0 )
(  1  1  0  0  0  0 )
(  1  2  1  0  0  0 )
(  1  3  3  1  0  0 )
(  1  4  6  4  1  0 )
(  1  5 10 10  5  1 )

Leer más…