Decimos que un número es de suma prima si la suma de todos sus dígitos es un número primo. Por ejemplo el número 562 es de suma prima pues la suma de sus dígitos es el número primo 13; sin embargo, el número 514 no es de suma prima pues la suma de sus dígitos es 10, que no es primo.

Decimos que un número es de suma prima hereditario por la derecha si es de suma prima y los números que se obtienen eliminando sus últimas cifras también son de suma prima. Por ejemplo 7426 es de suma prima hereditario por la derecha pues 7426, 742, 74 y 7 son todos números de suma prima.

Definir la constante

listaSumaPrimaHD :: [Integer]

cuyo valor es la lista infinita de los números de suma prima hereditarios por la derecha. Por ejemplo,

take 10 listaSumaPrimaHD     ==  [2,3,5,7,20,21,23,25,29,30]
listaSumaPrimaHD !! 2000000  ==  3800024668046

Leer más…

Todo número par se puede escribir como suma de números pares de varias formas. Por ejemplo,

8 = 8
  = 6 + 2
  = 4 + 4
  = 4 + 2 + 2
  = 2 + 2 + 2 + 2

Definir la función

descomposicionesDecrecientes:: Integer -> [[Integer]]

tal que (descomposicionesDecrecientes n) es la lista con las descomposiciones de n como suma de pares, en forma decreciente. Por ejemplo,

λ> descomposicionesDecrecientes 8
[[8],[6,2],[4,4],[4,2,2],[2,2,2,2]]
λ> descomposicionesDecrecientes 10
[[10],[8,2],[6,4],[6,2,2],[4,4,2],[4,2,2,2],[2,2,2,2,2]]
λ> length (descomposicionesDecrecientes 100)
204226

Leer más…

Los polinomios de Bell forman una sucesión de polinomios, definida como sigue:

B₀(x) = 1 (polinomio unidad)
Bₙ(x) = x·[Bₙ(x) + Bₙ'(x)]

donde Bₙ' es la derivada de Bₙ. Por ejemplo,

B₀(x) = 1                       = 1
B₁(x) = x·(1+0)                 = x
B₂(x) = x·(x+1)                 = x²+x
B₃(x) = x·(x²+x + 2x+1)         = x³+3x²+x
B₄(x) = x·(x³+3x²+x + 3x²+6x+1) = x⁴+6x³+7x²+x

Definir la función

polBell :: Integer -> Polinomio Integer

tal que (polBell n) es el polinomio de Bell de grado n. Por ejemplo,

polBell 4                    ==  x^4 + 6*x^3 + 7*x^2 + 1*x
coeficiente 2 (polBell 4)    ==  7
coeficiente 2 (polBell 30)   ==  536870911
coeficiente 1 (polBell 1000) == 1
length (show (coeficiente 9 (polBell 1000)))  ==  949

Notas: Se usa la librería I1M.PolOperaciones que se encuentra aquí y se describe aquí. Además, en el último ejemplo se usa la función coeficiente tal que (coeficiente k p) es el coeficiente del término de grado k en el polinomio p definida por

coeficiente :: Num a => Integer -> Polinomio a -> a
coeficiente k p | k == n                 = coefLider p
                | k > grado (restoPol p) = 0
                | otherwise              = coeficiente k (restoPol p)
                where n = grado p

Leer más…

Consideramos las matrices representadas como tablas cuyos índices son pares de números naturales.

type Matriz a = Array (Int,Int) a

Una matriz cruzada es una matriz cuadrada en la que sólo hay elementos distintos de 0 en las diagonales principal y secundaria. Por ejemplo,

| 1 0 0 0 3 |     | 1 0 0 3 |
| 0 2 0 1 0 |     | 0 2 3 0 |
| 0 0 3 0 0 |     | 0 4 5 0 |
| 0 2 0 1 0 |     | 2 0 0 3 |
| 1 0 0 0 3 |

Definir la función

creaCruzada :: Int -> Matriz Int

tal que (creaCruzada n) es la siguiente matriz cruzada con n filas y n columnas:

| 1  0   0  ...  0   0  1 |
| 0  2   0  ...  0   2  0 |
| 0  0   3  ...  3   0  0 |
| ....................... |
| 0  0  n-2 ... n-2  0  0 |
| 0 n-1  0  ...  0  n-1 0 |
| n  0   0  ...  0   0  n |

Es decir, los elementos de la diagonal principal son [1,...,n], en orden desde la primera fila hasta la última; y los elementos de la diagonal secundaria son [1,...,n], en orden desde la primera fila hasta la última. Por ejemplo,

λ> elems (creaCruzada 3)
[1,0,1, 0,2,0, 3,0,3]
λ> elems (creaCruzada 4)
[1,0,0,1, 0,2,2,0, 0,3,3,0, 4,0,0,4]
λ> elems (creaCruzada 5)
[1,0,0,0,1, 0,2,0,2,0, 0,0,3,0,0, 0,4,0,4,0, 5,0,0,0,5]

Leer más…

Consideremos los árboles binarios con etiquetas en las hojas y en los nodos. Por ejemplo,

  5
 / \
2   4
   / \
  7   1
     / \
    2   3

Un camino es una sucesión de nodos desde la raiz hasta una hoja. Por ejemplo, [5,2] y [5,4,1,2] son caminos que llevan a 2, mientras que [5,4,1] no es un camino, pues no lleva a una hoja.

Definimos el tipo de dato Arbol y el ejemplo por

data Arbol = H Int | N Arbol Int Arbol
             deriving Show

arb1:: Arbol
arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3)))

Definir la función

maxLong :: Int -> Arbol -> Int

tal que (maxLong x a) es la longitud máxima de los caminos que terminan en x. Por ejemplo,

maxLong 3 arb1 == 4
maxLong 2 arb1 == 4
maxLong 7 arb1 == 3

Leer más…

Un elemento de una matriz es un máximo local si es mayor que todos sus vecinos. Por ejemplo, en la matriz

[[1,0,0,8],
 [0,2,0,3],
 [0,0,0,5],
 [3,5,7,6],
 [1,2,3,4]]

los máximos locales son 8 (en la posición (1,4)), 2 (en la posición (2,2)) y 7 (en la posición (4,3)).

Definimos el tipo de las matrices, mediante

type Matriz a = Array (Int,Int) Int

y el ejemplo anterior por

ej1 :: Matriz Int
ej1 = listArray ((1,1),(5,4)) (concat [[1,0,0,8],
                                       [0,2,0,3],
                                       [0,0,0,5],
                                       [3,5,7,6],
                                       [1,2,3,4]])

Definir la función

maximosLocales :: Matriz Int -> [((Int,Int),Int)]

tal que (maximosLocales p) es la lista de las posiciones en las que hay un máximo local, con el valor correspondiente. Por ejemplo,

maximosLocales ej1 == [((1,4),8),((2,2),2),((4,3),7)]

Leer más…

En lógica temporal, la expresión AFp significa que en algún momento en el futuro se cumple la propiedad p. Trasladado a su interpretación en forma de árbol lo que quiere decir es que en todas las ramas (desde la raíz hasta una hoja) hay un nodo que cumple la propiedad p.

Consideramos el siguiente tipo algebraico de los árboles binarios:

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

y el siguiente árbol

a1 :: Arbol Int
a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)

En este árbol se cumple (AF par); es decir, en todas las ramas hay un número par; pero no se cumple (AF primo); es decir, hay ramas en las que no hay ningún número primo. Donde una rama es la secuencia de nodos desde el nodo inicial o raíz hasta una hoja.

Definir la función

propiedadAF :: (a -> Bool) -> Arbol a -> Bool

tal que (propiedadAF p a) se verifica si se cumple (AF p) en el árbol a; es decir, si en todas las ramas hay un nodo (interno u hoja) que cumple la propiedad p. Por ejemplo

propiedadAF even a1     ==  True
propiedadAF isPrime a1  ==  False

Leer más…

El cociente entero de un polinomio P(x) por un monomio axⁿ es el polinomio que se obtiene a partir de los términos de P(x) con un grado mayor o igual que n, realizando la división entera entre sus coeficientes y el coeficiente del monomio divisor y restando el valor de n al de sus grados. Por ejemplo,

• El cociente entero de 4x⁴ + 6x³ + 7x² + 5x + 2 por el monomio 3x² se obtiene a partir de los términos 4x⁴ + 6x³ + 7x² realizando la división entera entre sus coeficientes y el número 3 y restando 2 a sus grados. De esta forma se obtiene x² + 2x + 2
• El cociente entero de 6x⁵ + 2x⁴ + 8x³ + 5x² + 8x + 4 por el monomio 4x³ se obtiene a partir de los términos 6x⁵ + 2x⁴ + 8x³ realizando la división entera entre sus coeficientes y el número 4 y restando 3 a sus grados. De esta forma se obtiene x² + 2

Definir la función

cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

tal que (cocienteEntero p a n) es el cociente entero del polinomio p por el monomio de grado n y coeficiente a. Por ejemplo,

λ> let listaApol xs = foldr (\(n,b) -> consPol n b) polCero xs
λ> cocienteEntero (listaApol [(4,4),(3,6),(2,7),(1,5),(0,2)]) 3 2
x^2 + 2*x + 2
λ> cocienteEntero (listaApol [(5,6),(4,2),(3,8),(2,5),(1,8),(0,4)]) 4 3
x^2 + 2

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.

Leer más…

Se dice que dos números naturales son parientes sitienen exactamente un factor primo en común, independientemente de su multiplicidad. Por ejemplo,

• Los números 12 (2²·3) y 40 (2³·5) son parientes, pues tienen al 2 como único factor primo en común.
• Los números 49 (7²) y 63 (3²·7) son parientes, pues tienen al 7 como único factor primo en común.
• Los números 12 (2²·3) y 30 (2·3·5) no son parientes, pues tienen dos factores primos en común.
• Los números 49 (7²) y 25 (5²) no son parientes, pues no tienen factores primos en común.

Se dice que una lista de números naturales es una secuencia de parientes si cada par de números consecutivos son parientes. Por ejemplo,

• La lista [12,40,35,28] es una secuencia de parientes.
• La lista [12,30,21,49] no es una secuencia de parientes.

Definir la función

secuenciaParientes :: [Integer] -> Bool

tal que (secuenciaParientes xs) se verifica si xs es una secuencia de parientes. Por ejemplo,

secuenciaParientes [12,40,35,28]           ==  True
secuenciaParientes [12,30,21,49]           ==  False
secuenciaParientes [2^n | n <- [1..2000]]  ==  True

Leer más…

En este ejercicio, representamos las fracciones mediante pares de números de enteros.

Definir la función

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

tal que (fraccionesOrd n) es la lista con las fracciones propias positivas ordenadas, con denominador menor o igual que n. Por ejemplo,

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

Leer más…