Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]

Definir la función

reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

reducido []                              ==  []
reducido [N]                             ==  [N]
reducido [N,O]                           ==  [N,O]
reducido [N,O,E]                         ==  [N]
reducido [N,O,E,S]                       ==  []
reducido [N,O,S,E]                       ==  [N,O,S,E]
reducido [S,S,S,N,N,N]                   ==  []
reducido [N,S,S,E,O,N]                   ==  []
reducido [N,S,S,E,O,N,O]                 ==  [O]
reducido (take (10^7) (cycle [N,E,O,S])) ==  []

Nótese que en el penúltimo ejemplo las reducciones son

    [N,S,S,E,O,N,O]
--> [S,E,O,N,O]
--> [S,N,O]
--> [O]

Leer más…

Los números racionales se pueden representar como pares de enteros:

type Racional a = (a,a)

Definir la función

reducida :: Integral a => [Racional a] -> [Racional a]

tal que (reducida xs) es la lista de los números racionales donde cada uno es igual al correspondiente elemento de xs y el denominador de todos los elementos de (reducida xs) es el menor número que cumple dicha condición; es decir, si xs es la lista

[(x_1, y_1), ..., (x_n, y_n)]

entonces (reducida xs) es

[(z_1, d), ..., (z_n, d)]

tales que

z_1/d = x_1/y_1, ..., z_n/d = x_n/y_n

y d es el menor posible. Por ejemplo,

reducida [(1,2),(1,3),(1,4)]  ==  [(6,12),(4,12),(3,12)]
reducida [(1,2),(1,3),(6,4)]  ==  [(3,6),(2,6),(9,6)]
reducida [(-7,6),(-10,-8)]    ==  [(-14,12),(15,12)]
reducida [(8,12)]             ==  [(2,3)]

Leer más…

Definir la funciones

sumas  :: Int -> [[Int]]
nSumas :: Int -> Integer

tales que

• (sumas n) es la lista de las descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,

sumas 1            ==  [[1]]
sumas 2            ==  [[1,1],[2]]
sumas 3            ==  [[1,1,1],[1,2],[2,1]]
sumas 4            ==  [[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]
length (sumas 26)  ==  196418
length (sumas 33)  ==  5702887

• (nSumas n) es el número de descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,

nSumas 4                      ==  5
nSumas 123                    ==  36726740705505779255899443
length (show (nSumas 123456)) ==  25801

Leer más…

Un número primo es hereditario si todos los números obtenidos eliminando dígitos por la derecha o por la izquierda son primos. Por ejemplo, 3797 es hereditario ya que los números obtenidos eliminando dígitos por la derecha son 3797, 379, 37 y 3 y los obtenidos eliminando dígitos por la izquierda son 3797, 797, 97 y 7 y todos ellos son primos.

Definir la sucesión

hereditarios :: [Integer]

cuyos elementos son los números hereditarios. Por ejemplo,

λ> take 15 hereditarios
[2,3,5,7,23,37,53,73,313,317,373,797,3137,3797,739397]

Leer más…

La constante de Champernowne es el número irracional

0.12345678910111213141516171819202122232425262728293031323334 ...

cuya parte entera es 0 y la parte decimal se obtiene concatenado los números naturales a partir de 1.

Definir la función

productoChampernowne :: [Int] -> Int

tal que (productoChampernowne ns) es el producto de los dígitos de la constante de Champernowne que ocupan las posiciones ns. Por ejemplo,

productoChampernowne [0,1,2]                 ==  6
productoChampernowne [8,20]                  ==  45
productoChampernowne [10^i-1 | i <- [0..7]]  ==  1470

Leer más…

Se tiene una calle en la que las casas sólo están en un lado de ésta y las casas están numeradas de 1 hasta n, donde n es el número total de casas en la calle. Se dice que el número de una casa es equilibrado si y solamente si la suma de los números de las casas anteriores es igual a la suma de los números posteriores a la casa. Por ejemplo, el número de la 6ª casa, en una calle con 8 casas, es equilibrado ya que

1 + 2 + 3 + 4 + 5 = 7 + 8

Definir la función

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

tal que (soluciones x y) es la lista de pares (a,n) tales que a es el número equilibrado de una casa en una calle con n casas y n está entre x e y. Por ejemplo,

soluciones 1 500          ==  [(1,1),(6,8),(35,49),(204,288)]
soluciones 1000 3000      ==  [(1189,1681)]
soluciones (10^5) (10^6)  ==  [(235416,332928)]
soluciones (10^6) (10^7)  ==  [(1372105,1940449)]
(fst $ head $ soluciones (10^100) (10^101))  `mod` (10^9)  ==  763728460
(fst $ head $ soluciones (10^800) (10^1000)) `mod` (10^9)  ==  311156546

Leer más…

Las torres de Hanói es un rompecabeza que consta de tres postes que llamaremos A, B y C. Hay N discos de distintos tamaños en el poste A, de forma que no hay un disco situado sobre otro de menor tamaño. Los postes B y C están vacíos. Sólo puede moverse un disco a la vez y todos los discos deben de estar ensartados en algún poste. Ningún disco puede situarse sobre otro de menor tamaño. El problema consiste en colocar los N discos en el poste C.

Definir la función

hanoi :: Int -> [String]

tal que (hanoi n) es la lista de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,

λ> hanoi 1
["Mueve el disco 1 de A a C"]
λ> hanoi 2
["Mueve el disco 1 de A a B","Mueve el disco 2 de A a C","Mueve el disco 1 de B a C"]
λ> mapM_ putStrLn (hanoi 2)
Mueve el disco 1 de A a B
Mueve el disco 2 de A a C
Mueve el disco 1 de B a C
λ> mapM_ putStrLn (hanoi 3)
Mueve el disco 1 de A a C
Mueve el disco 2 de A a B
Mueve el disco 1 de C a B
Mueve el disco 3 de A a C
Mueve el disco 1 de B a A
Mueve el disco 2 de B a C
Mueve el disco 1 de A a C

Leer más…

Empezando con el número 1 y moviéndose en el sentido de las agujas del reloj se obtienen las matrices espirales

|1 2|   |7 8 9|   | 7  8  9 10|   |21 22 23 24 25|
|4 3|   |6 1 2|   | 6  1  2 11|   |20  7  8  9 10|
        |5 4 3|   | 5  4  3 12|   |19  6  1  2 11|
                  |16 15 14 13|   |18  5  4  3 12|
                                  |17 16 15 14 13|

La suma los elementos de sus diagonales es

• en la 2x2: 1+3+2+4 = 10
• en la 3x3: 1+3+5+7+9 = 25
• en la 4x4: 1+2+3+4+7+10+13+16 = 56
• en la 5x5: 1+3+5+7+9+13+17+21+25 = 101

Definir la función

sumaDiagonales :: Integer -> Integer

tal que (sumaDiagonales n) es la suma de los elementos en las diagonales de la matriz espiral de orden nxn. Por ejemplo.

sumaDiagonales 1         ==  1
sumaDiagonales 2         ==  10
sumaDiagonales 3         ==  25
sumaDiagonales 4         ==  56
sumaDiagonales 5         ==  101
sumaDiagonales (1+10^6)  ==  666669166671000001
sumaDiagonales (10^2)    ==         671800
sumaDiagonales (10^3)    ==        667168000
sumaDiagonales (10^4)    ==       666716680000
sumaDiagonales (10^5)    ==      666671666800000
sumaDiagonales (10^6)    ==     666667166668000000
sumaDiagonales (10^7)    ==    666666716666680000000
sumaDiagonales (10^8)    ==   666666671666666800000000
sumaDiagonales (10^9)    ==  666666667166666668000000000

Comprobar con QuickCheck que el último dígito de (sumaDiagonales n) es 0, 4 ó 6 si n es par y es 1, 5 ó 7 en caso contrario.

Leer más…

Un número pandigital es un número que contiene todos los dígitos del 1 al 9 sólo una vez. Por ejemplo, 192384576 es un número pandigital.

El producto de un número natural x por una lista de números naturales ys es el número obtenido concatenando los productos de x por cada uno de los elementos de ys. Por ejemplo, el producto de 2 por [3,2,5] es 6410.

Un número pandigital x es un múltiplo si existe un y y un n > 1 tales que x es el producto de y por [1,2,3,...,n]. Por ejemplo, 192384576 es un pandigital múltiplo ya que

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

por tanto, 192384576 es el producto de 192 por [1,2,3]. Otro pandgital múltiplo es el 918273645 ya que es el producto de 9 por [1,2,3,4,5].

Definir la sucesión

pandigitalesMultiplos :: [Integer]

tal que sus elementos son los números pandigitales múltiplos. Por ejemplo,

λ> take 5 pandigitalesMultiplos
[123456789,192384576,219438657,273546819,327654981]

Leer más…

El producto de un número natural x por una lista de números naturales ys es el número obtenido concatenando los productos de x por cada uno de los elementos de ys. Por ejemplo, el producto de 2 por [3,2,5] es 26410.

Definir la función

producto :: Integer -> [Integer] -> Integer

tal que (producto x ys) es el producto de x por ys. Por ejemplo,

producto  2 [3,2,5]  ==  6410
producto 10 [3,2,5]  ==  302050

Leer más…

El grado perimetral de un número p es la cantidad de tres triángulos rectángulos de lados enteros cuyo perímetro es p. Por ejemplo, el grado perimetral de 120 es 3 ya que sólo hay 3 triángulos rectángulos de lados enteros cuyo perímetro es 120: {20,48,52}, {24,45,51} y {30,40,50}.

Definir la función

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

tal que (maxGradoPerimetral n) es el par (m,ps) tal que m es el máximo grado perimetral de los números menores o iguales que n y ps son los perímetros, menores o iguales que n, cuyo grado perimetral es m. Por ejemplo,

maxGradoPerimetral   50  ==  (1,[12,24,30,36,40,48])
maxGradoPerimetral  100  ==  (2,[60,84,90])
maxGradoPerimetral  200  ==  (3,[120,168,180])
maxGradoPerimetral  400  ==  (4,[240,360])
maxGradoPerimetral  500  ==  (5,[420])
maxGradoPerimetral  750  ==  (6,[720])
maxGradoPerimetral  839  ==  (6,[720])
maxGradoPerimetral  840  ==  (8,[840])
maxGradoPerimetral 1500  ==  (8,[840,1260])
maxGradoPerimetral 2000  ==  (10,[1680])
maxGradoPerimetral 3000  ==  (12,[2520])

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
ausente2 ([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 exactamente un término de la progresión aritmética que no está en la lista.

Leer más…

Un polinomio de coeficientes enteros se dirá par si todos sus coeficientes son números pares. Por ejemplo, el polinomio 2x³ - 4x² + 8 es par y el x² + 2x + 10 no lo es.

Definir el predicado

parPol :: Integral a => Polinomio a -> Bool

tal que (parPol p) se verifica si p es un polinomio par. Por ejemplo,

λ> parPol (consPol 3 2 (consPol 2 (-4) (consPol 0 8 polCero)))
True
λ> parPol (consPol 2 1 (consPol 1 2 (consPol 0 10 polCero)))
False

Comprobar con QuickCheck que la suma de un polinomio con él mismo es un polinomio par.

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

Leer más…

Representamos las matrices mediante el tipo de dato

type Matriz a = Array (Int,Int) a

Por ejemplo,

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

representa la matriz

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

Definir la función

ampliada :: Num a => Matriz a -> Matriz a

tal que (ampliada p) es la matriz obtenida al añadir una nueva fila a p cuyo elemento i-ésimo es la suma de la columna i-ésima de p. Por ejemplo,

|1 2 3 0|        |1 2 3 0|
|4 5 6 7| ==>    |4 5 6 7|
                 |5 7 9 7|

En Haskell,

λ> ampliada ejM
array ((1,1),(3,4)) [((1,1),1),((1,2),2),((1,3),3),((1,4),0),
                     ((2,1),4),((2,2),5),((2,3),6),((2,4),7),
                     ((3,1),5),((3,2),7),((3,3),9),((3,4),7)]

Leer más…

Representamos los árboles binarios con elementos en las hojas y en los nodos mediante el tipo de dato

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

Por ejemplo,

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

Definir la función

ramasCon :: Eq a => Arbol a -> a -> [[a]]

tal que (ramasCon a x) es la lista de las ramas del árbol a en las que aparece el elemento x. Por ejemplo,

ramasCon ej1 2 ==  [[5,2,1],[5,2,2],[5,3,2]]

Leer más…

Dos enteros positivos a y b se dirán relacionados si poseen, exactamente, un factor primo en común. Por ejemplo, 12 y 20 están relacionados, pero 6 y 30 no lo están.

Definir la lista infinita

paresRel :: [(Int,Int)]

tal que paresRel enumera todos los pares (a,b), con 1 ≤ a < b, tal que a y b están relacionados. Por ejemplo,

λ> take 10 paresRel
[(2,4),(2,6),(3,6),(4,6),(2,8),(4,8),(6,8),(3,9),(6,9),(2,10)]

¿Qué lugar ocupa el par (51,111) en la lista infinita paresRel?

Leer más…

Definir las funciones

agrupa  :: Eq a => [a] -> [(a,Int)]
expande :: [(a,Int)] -> [a]

tales que

• (agrupa xs) es la lista obtenida agrupando las ocurrencias consecutivas de elementos de xs junto con el número de dichas ocurrencias. Por ejemplo:

agrupa "aaabzzaa" == [('a',3),('b',1),('z',2),('a',2)]

• (expande xs) es la lista expandida correspondiente a ps (es decir, es la lista xs tal que la comprimida de xs es ps. Por ejemplo,

expande [('a',2),('b',3),('a',1)] == "aabbba"

Comprobar con QuickCheck que dada una lista de enteros, si se la agrupa y después se expande se obtiene la lista inicial.

Leer más…

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…

En 1772, Euler publicó que el polinomio n² + n + 41 genera 40 números primos para todos los valores de n entre 0 y 39. Sin embargo, cuando n=40, 40²+40+41 = 40(40+1)+41 es divisible por 41.

Usando ordenadores, se descubrió el polinomio n² - 79n + 1601 que genera 80 números primos para todos los valores de n entre 0 y 79.

Definir la función

generadoresMaximales :: Integer -> (Int,[(Integer,Integer)])

tal que (generadoresMaximales n) es el par (m,xs) donde

• xs es la lista de pares (x,y) tales que n²+xn+y es uno de los polinomios que genera un número máximo de números primos consecutivos a partir de cero entre todos los polinomios de la forma n²+an+b, con |a| ≤ n y |b| ≤ n y
• m es dicho número máximo.

Por ejemplo,

generadoresMaximales    4  ==  ( 3,[(-2,3),(-1,3),(3,3)])
generadoresMaximales    6  ==  ( 5,[(-1,5),(5,5)])
generadoresMaximales   50  ==  (43,[(-5,47)])
generadoresMaximales  100  ==  (48,[(-15,97)])
generadoresMaximales  200  ==  (53,[(-25,197)])
generadoresMaximales 1650  ==  (80,[(-79,1601)])

Leer más…

El triángulo de Floyd, llamado así en honor a Robert Floyd, es un triángulo rectángulo formado con números naturales. Para crear un triángulo de Floyd, se comienza con un 1 en la esquina superior izquierda, y se continúa escribiendo la secuencia de los números naturales de manera que cada línea contenga un número más que la anterior. Las 5 primeras líneas del triángulo de Floyd son

 1
 2   3
 4   5   6
 7   8   9  10
11  12  13  14  15

Definir la función

trianguloFloyd :: [[Integer]]

tal que trianguloFloyd es el triángulo de Floyd. Por ejemplo,

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

(trianguloFloyd !! (10^5)) !! 0  ==  5000050001
(trianguloFloyd !! (10^6)) !! 0  ==  500000500001
(trianguloFloyd !! (10^7)) !! 0  ==  50000005000001

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…

Definir la función

actualiza :: [a] -> [(Int,a)] -> [a]

tal que (actualiza xs ps) es la lista obtenida sustituyendo en xs los elementos cuyos índices son las primeras componentes de ps por las segundas. Por ejemplo,

actualiza [3,5,2,4] [(2,1),(0,7)]  ==  [7,5,1,4]
sum (actualiza2 [1..10^4] [(i,2*i) | i <- [0..10^4-1]]) == 99990000

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

ordenDeDivibilidad :: Integer -> Int

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

ordenDeDivibilidad 74156                      ==  3
ordenDeDivibilidad 3608528850368400786036725  ==  25

Leer más…

Una propiedad del número 24 es que entre los números menores o iguales que 24 hay la misma cantidad de números con el dígito 1 que sin el 1; en efecto, los que tienen 1 son

[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21]

y los que no lo tienen son

[2,  3,  4,  5,  6,  7,  8,  9, 20, 22, 23, 24]

Diremos que un número es especial si cumple dicha propiedad.

Definir la sucesión

especiales :: [Integer]

cuyos elementos son los números especiales. Por ejemplo,

take 10 especiales  ==  [2,16,24,160,270,272,1456,3398,3418,3420]

Leer más…

Los caminos en los árboles binarios

    .          .
   / \        / \
  .   .      /   \
 / \        .     .
.   .      / \   / \
          .   . .   .

son [[I,I],[I,D],[D]] y [[I,I],[I,D],[D,I],[D,D]], donde I indica un movimiento hacia la izquierda y D uno hacia la derecha.

Los árboles binarios se pueden representar por

data Arbol = H | N Arbol Arbol

los movimientos por

data Mov    = I | D deriving Show

y los caminos por

type Camino = [Mov]

Definir la función

caminos :: Arbol -> [Camino]

tal que (caminos a) es la lista de los caminos en el árbol binario a. Por ejemplo,

caminos (N (N H H) H)             == [[I,I],[I,D],[D]]
caminos (N (N H H) (N H H))       == [[I,I],[I,D],[D,I],[D,D]]
caminos (N H (N (N H H) (N H H))) == [[I],[D,I,I],[D,I,D],[D,D,I],[D,D,D]]

Leer más…

Sea S un conjunto de números. Las listas de ceros emparejados de S son las listas formadas con los elementos de S y en las cuales los ceros aparecen en sublistas de longitud par. Por ejemplo, si S = {0,1,2} entonces [1], [2], [2,1], [2,0,0,2,0,0,1] y [0,0,0,0,1,2] son listas de ceros emparejados de S; pero [0,0,0,2,1,0,0] y [0,0,1,0,1] no lo son.

Definir las funciones

cerosEmparejados  :: Integer -> Integer -> [[Integer]]
nCerosEmparejados :: Integer -> Integer -> Integer

tales que + (cerosEmparejados m n) es la lista de las listas de longitud n de ceros emparejados con los números 0, 1, 2,..., m. Por ejemplo,

λ> cerosEmparejados 2 0
[[]]
λ> cerosEmparejados 2 1
[[1],[2]]
λ> cerosEmparejados 3 1
[[1],[2],[3]]
λ> cerosEmparejados 2 2
[[1,1],[1,2],[2,1],[2,2],[0,0]]
λ> cerosEmparejados 2 3
[[1,1,1],[1,1,2],[1,2,1],[1,2,2],[1,0,0],[2,1,1],[2,1,2],
 [2,2,1],[2,2,2],[2,0,0],[0,0,1],[0,0,2]]
λ> cerosEmparejados 2 4
[[1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,2,2],[1,1,0,0],[1,2,1,1],
 [1,2,1,2],[1,2,2,1],[1,2,2,2],[1,2,0,0],[1,0,0,1],[1,0,0,2],
 [2,1,1,1],[2,1,1,2],[2,1,2,1],[2,1,2,2],[2,1,0,0],[2,2,1,1],
 [2,2,1,2],[2,2,2,1],[2,2,2,2],[2,2,0,0],[2,0,0,1],[2,0,0,2],
 [0,0,1,1],[0,0,1,2],[0,0,2,1],[0,0,2,2],[0,0,0,0]]

• (nCerosEmparejados m n) es el número de listas de longitud n de ceros emparejados con los números 0, 1, 2,..., m. Por ejemplo,

nCerosEmparejados 2 2   ==  5
nCerosEmparejados 2 3   ==  12
nCerosEmparejados 2 4   ==  29
nCerosEmparejados 9 27  ==  79707842493701635611689499

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…

En este problema se consideran matrices cuyos elementos son 0 y 1. Los valores 1 aparecen en forma de islas rectangulares separadas por 0 de forma que como máximo las islas son diagonalmente adyacentes. Por ejemplo,

ej1, ej2 :: Array (Int,Int) Int
ej1 = listArray ((1,1),(6,3))
                [0,0,0,
                 1,1,0,
                 1,1,0,
                 0,0,1,
                 0,0,1,
                 1,1,0]
ej2 = listArray ((1,1),(6,6))
                [1,0,0,0,0,0,
                 1,0,1,1,1,1,
                 0,0,0,0,0,0,
                 1,1,1,0,1,1,
                 1,1,1,0,1,1,
                 0,0,0,0,1,1]

Definir la función

numeroDeIslas :: Array (Int,Int) Int -> Int

tal que (numeroDeIslas p) es el número de islas de la matriz p. Por ejemplo,

numeroDeIslas ej1  ==  3
numeroDeIslas ej2  ==  4

Leer más…

Sea \(\{b_i \mid i \geq 1\}\) una sucesión infinita de números enteros mayores que 1. Entonces, todo entero \(x\) mayor que cero se puede escribir de forma única como \[ x = x_0 + x_1 b_1 + x_2 b_1 b_2 + \dots + x_n b_1 b_2 \dotsm b_n, \] donde cada \(x_i\) satisface la condición \(0 \leq x_i < b_{i+1}\). Se dice que \([x_n, x_{n-1}, \dots, x_2, x_1, x_0]\) es la representación de \(x\) en la base \((b_i).

Por ejemplo, la representación de 377 en la base \((2i)_{i \geq 1}\) es \([7,5,0,1]\), ya que \[ 377 = 1 + 0 \times 2 + 5 \times 2 \times 4 + 7 \times 2 \times 4 \times 6, \] y además: \[ 0 \leq 1 < 2, \quad 0 \leq 0 < 4, \quad 0 \leq 5 < 6, \quad 0 \leq 7 < 8. \]

Definir las funciones

decimalAmultiple :: [Int] -> Int -> [Int]
multipleAdecimal :: [Int] -> [Int] -> Int

tales que (decimalAmultiple bs x) es la representación del número x en la base bs y (multipleAdecimal bs cs) es el número decimal cuya representación en la base bs es cs. Por ejemplo,

decimalAmultiple [2,4..] 377                      ==  [7,5,0,1]
multipleAdecimal [2,4..] [7,5,0,1]                ==  377
decimalAmultiple [2,5..] 377                      ==  [4,5,3,1]
multipleAdecimal [2,5..] [4,5,3,1]                ==  377
decimalAmultiple [2^n | n <- [1..]] 2015          ==  [1,15,3,3,1]
multipleAdecimal [2^n | n <- [1..]] [1,15,3,3,1]  ==  2015
decimalAmultiple (repeat 10) 2015                 ==  [2,0,1,5]
multipleAdecimal (repeat 10) [2,0,1,5]            ==  2015

Comprobar con QuickCheck que se verifican las siguientes propiedades

prop_inversas :: [Int] -> Int -> Property
prop_inversas bs x =
    x > 0 ==> multipleAdecimal bs (decimalAmultiple bs x) == x

prop_coeficientes :: [Int] -> Int -> Property
prop_coeficientes bs x =
    x > 0 ==> and [0 <= c && c < b | (c,b) <- zip cs bs]
    where cs = reverse (decimalAmultiple bs x)

para distintas bases dadas. Por ejemplo,

λ> quickCheck (prop_inversas [2,4..])
+++ OK, passed 100 tests.
λ> quickCheck (prop_inversas [3,5..])
+++ OK, passed 100 tests.
λ> quickCheck (prop_coeficientes [2,4..])
+++ OK, passed 100 tests.
λ> quickCheck (prop_coeficientes [3,5..])
+++ OK, passed 100 tests.

Leer más…

La diferencia progresiva entre dos elementos de una lista es la resta entre el que ocupa la mayor posición y la menor. Por ejemplo, en la lista [1,5,8,2,9] la diferencia entre los elementos 5 y 8 es 3 y entre 5 y 2 es -3.

Definir la función

mayorDiferencia :: [Int] -> Int

tal que (mayorDiferencia xs) es la mayor diferencia progresiva entre los elementos de xs. Por ejemplo,

mayorDiferencia [1,5,8,2,9]  ==  8
mayorDiferencia [9,5,8,2,1]  ==  3
mayorDiferencia [3,2,1]      ==  0
mayorDiferencia [1..10^7]    ==  9999999

Leer más…

Los conjuntos de polinomios se pueden representar por listas de listas de la misma longitud. Por ejemplo, los polinomios 3x²+5x+9, 10x³+9 y 8x³+5x²+x-1 se pueden representar por las listas [0,3,5,9], [10,0,0,9] y [8,5,1,-1].

Definir la función

sumaPolinomios :: Num a => [[a]] -> [a]

tal que (sumaPolinomios ps) es la suma de los polinomios ps. Por ejemplo,

λ> sumaPolinomios1 [[0,3,5,9],[10,0,0,9],[8,5,1,-1]]
[18,8,6,17]
λ> sumaPolinomios6 (replicate 1000000 (replicate 3 1))
[1000000,1000000,1000000]

Leer más…

La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n² primeros números naturales colocados de manera creciente a lo largo de las diagonales secundarias. Por ejemplo, La matriz zigzagueante de orden 5 es

 0  1  5  6 14
 2  4  7 13 15
 3  8 12 16 21
 9 11 17 20 22
10 18 19 23 24

La colocación de los elementos se puede ver gráficamente en

Definir la función

zigZag :: Int -> Array (Int,Int) Int

tal que (zigZag n) es la matriz zigzagueante de orden n. Por ejemplo,

λ> elems (zigZag 3)
[0,1,5, 2,4,6, 3,7,8]
λ> elems (zigZag 4)
[0,1,5,6, 2,4,7,12, 3,8,11,13, 9,10,14,15]
λ> elems (zigZag 5)
[0,1,5,6,14, 2,4,7,13,15, 3,8,12,16,21, 9,11,17,20,22, 10,18,19,23,24]
λ> take 15 (elems (zigZag 1000))
[0,1,5,6,14,15,27,28,44,45,65,66,90,91,119]

Leer más…

Definir la función

nMinimoCambios :: Ord a => [a] -> Int

tal que (nMinimoCambios xs) es el menor número de elementos de xs que hay que cambiar para que todos sean iguales. Por ejemplo,

nMinimoCambios [3,5,3,7,9,6]      ==  4
nMinimoCambios [3,5,3,7,3,3]      ==  2
nMinimoCambios "Salamanca"        ==  5
nMinimoCambios (4 : [1..500000])  ==  499999

En el primer ejemplo, los elementos que hay que cambiar son 5, 7, 9 y 6.

Leer más…

Definir la función

diagonalesSecundarias :: Matriz a -> [[a]]

tal que (diagonalesSecundarias p) es la lista de las diagonales secundarias de p. Por ejemplo, para la matriz

1  2  3  4
5  6  7  8
9 10 11 12

la lista de sus diagonales secundarias es

[[1],[2,5],[3,6,9],[4,7,10],[8,11],[12]]

En Haskell,

λ> diagonalesSecundarias (listArray ((1,1),(3,4)) [1..12])
[[1],[2,5],[3,6,9],[4,7,10],[8,11],[12]]

Leer más…

La n-ésima densidad de un tipo de número es el cociente entre la cantidad de los números entre 1 y n que son del tipo considerado y n. Por ejemplo, la 7-ésima densidad de los múltiplos de 3 es 2/7 ya que entre los 7 primeros números sólo 2 son múltiplos de 3.

Definir las funciones

densidades :: Int -> (Double,Double,Double)
graficas   :: Imt -> IO ()

tales que

• (densidades n) es la terna formada por la n-ésima densidad de los números abundantes (es decir, para los que la suma de sus divisores propios es mayor que el número), de los números perfectos (es decir, para los que la suma de sus divisores propios es mayor que el número) y de los números deficientes (es decir, para los que la suma de sus divisores propios es menor que el número). Por ejemplo,

densidades 100     ==  (0.22,    2.0e-2, 0.76)
densidades 1000    ==  (0.246,   3.0e-3, 0.751)
densidades 10000   ==  (0.2488,  4.0e-4, 0.7508)
densidades 100000  ==  (0.24795, 4.0e-5, 0.75201)

• (graficas n) dibuja las gráficas de las k-ésimas densidades (para k entre 1 y n) de los números abundantes, de los números perfectos y de los números deficientes. Por ejemplo, (graficas 100) dibuja

y (graficas 400) dibuja

Leer más…

Definir la función

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

tal que (sumaDivisoresHasta n) es la lista de los pares (a,b) tales que a es un número entre 1 y n y b es la suma de los divisores propios de a. Por ejemplo,

λ> sumaDivisoresHasta 12
[(1,0),(2,1),(3,1),(4,3),(5,1),(6,6),(7,1),(8,7),(9,4),(10,8),(11,1),(12,16)]
λ> maximum (map snd (sumaDivisoresHasta 123456))
368640

Leer más…

Definir la función

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

tal que (divisoresHasta n) es la lista de los pares (a,b) tales que a es un número entre 2 y n y b es un divisor propio de a. Por ejemplo,

λ> divisoresHasta 6
[(2,1),(3,1),(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)]
λ> divisoresHasta 8
[(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(4,2),(6,2),(8,2),(6,3),(8,4)]
λ> length (divisoresHasta 1234567)
16272448

Leer más…

La conjetura de Waring sobre los números primos establece que todo número impar es primo o la suma de tres primos. La conjetura de Goldbach afirma que todo número par mayor que 2 es la suma de dos números primos. Ambos problemas siguen abiertos después de más de 200 años. En este problema no se propone su solución, sino una tarea más simple: buscar una manera de expresar los enteros mayores que 7 como suma de exactamente cuatro números primos; es decir, definir la función

suma4primos :: Integer -> (Integer,Integer,Integer,Integer)

tal que (suma4primos n) es una cuádrupla (a,b,c,d) de números primos cuya suma es n (que se supone mayor que 7). Por ejemplo,

suma4primos 24             ==  (2,2,3,17)
suma4primos 1234567890123  ==  (2,3,29,1234567890089)

Comprobar con QuickCheck que suma4primos es correcta; es decir si (suma4primos n) es (a,b,c,d) entonces los números a, b c y d son primos y su suma es n.

Nota: Para cada n pueden existir distintas cuádruplas que cumplan la especificación. Por ejemplo, para el 16 hay tres: (2,2,5,7), (3,3,3,7) y (3,3,5,5). Cualquiera de ellas se admite como solución.

Leer más…

Un número n es abundante si la suma de los divisores propios de n es mayor que n. El primer número abundante es el 12 (cuyos divisores propios son 1, 2, 3, 4 y 6 cuya suma es 16). Por tanto, el menor número que es la suma de dos números abundantes es el 24.

Definir la sucesión

sumasDeDosAbundantes :: [Integer]

cuyos elementos son los números que se pueden escribir como suma de dos números abundantes. Por ejemplo,

take 10 sumasDeDosAbundantes  ==  [24,30,32,36,38,40,42,44,48,50]

Nota: La sucesión sumasDeDosAbundantes coincide con la sucesión A048260 de The On-Line Encyclopedia of Integer Sequences.

Leer más…

Leer más…

Definir la función

diagonalesPrincipales :: Matriz a -> [[a]]

tal que (diagonalesPrincipales p) es la lista de las diagonales principales de p. Por ejemplo, para la matriz

1  2  3  4
5  6  7  8
9 10 11 12

la lista de sus diagonales principales es

[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

En Haskell,

λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12])
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

Leer más…

Definir la función

segmentos :: Int -> [a] -> [[a]]

tal que (segmentos n xs) es la lista de los segmentos de longitud n de la lista xs. Por ejemplo,

segmentos 3 [1..5]  ==  [[1,2,3],[2,3,4],[3,4,5]]

Leer más…