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…

Definir la función

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

tal que (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como sus elementos son listas infinitas ordenadas. Por ejemplo,

λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
[2,3,4,5,6,7,8,9,10,11]
λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
[2,4,6,8,9,10,12,14,16,18]

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…

Definir la función

esPotenciaDeDos :: Integer -> Bool

tal que (esPotenciaDeDos n) se verifica si n es una potencia de dos (suponiendo que n es mayor que 0). Por ejemplo.

esPotenciaDeDos    1        == True
esPotenciaDeDos    2        == True
esPotenciaDeDos    6        == False
esPotenciaDeDos    8        == True
esPotenciaDeDos 1024        == True
esPotenciaDeDos 1026        == False
esPotenciaDeDos (2^100000)  == True

Nota: Comprobar la definición para grandes potencias de 2.

Leer más…

La sucesión de los números triangulares se obtiene sumando los números naturales.

*     *      *        *         *
     * *    * *      * *       * *
           * * *    * * *     * * *
                   * * * *   * * * *
                            * * * * *
1     3      6        10        15

Así, el 7º número triangular es

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Los primeros 10 números triangulares son

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Los divisores de los primeros 7 números triangulares son:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

Como se puede observar, 28 es el menor número triangular con más de 5 divisores.

Definir la función

menorTriangularConAlMenosNDivisores :: Int -> Integer

tal que (menorTriangularConAlMenosNDivisores n) es el menor número triangular que tiene al menos n divisores. Por ejemplo,

menorTriangularConAlMenosNDivisores 5    ==  28
menorTriangularConAlMenosNDivisores 50   ==  25200
menorTriangularConAlMenosNDivisores 500  ==  76576500

Leer más…

Definir la función

dosCuadrados :: Picture

que dibuje dos cuadrados encajados como se muestra en la siguiente figura

Nota: Escribir las soluciones usando la siguiente plantilla

import Graphics.Gloss

main :: IO ()
main = display (InWindow "Dibujo" (500,300) (20,20)) white dosCuadrados

dosCuadrados :: Picture
dosCuadrados = undefined

Leer más…

Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.

Definir la función

particiones :: Int -> [[Int]]

tal que (particiones n) es la lista de las particiones del número n. Por ejemplo,

particiones 4  ==  [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
particiones 5  ==  [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
length (particiones 50)  ==  204226

Leer más…

El producto escalar de los vectores [latex][a_1,a_2,\dots,a_n][/latex] y [latex][b_1,b_2,\dots,b_n][/latex] es [latex]a_1 \times b_1 + a_2 \times b_2 + \dots + a_n \times b_n[/latex].

Definir la función

menorProductoEscalar :: (Ord a, Num a) => [a] -> [a] -> a

tal que (menorProductoEscalar xs ys) es el mínimo de los productos escalares de las permutaciones de xs y de las permutaciones de ys. Por ejemplo,

menorProductoEscalar [3,2,5]  [1,4,6]   ==  29
menorProductoEscalar [3,2,5]  [1,4,-6]  ==  -19
menorProductoEscalar [0..9]   [0..9]    ==  120
menorProductoEscalar [0..99]  [0..99]   ==  161700
menorProductoEscalar [0..999] [0..999]  ==  166167000

Leer más…

Un capicúa es un número que es igual leído de izquierda a derecha que de derecha a izquierda.

Definir la función

mayorCapicuaP :: Integer -> Integer

tal que (mayorCapicuaP n) es el mayor capicúa que es el producto de dos números de n cifras. Por ejemplo,

mayorCapicuaP 2  ==  9009
mayorCapicuaP 3  ==  906609
mayorCapicuaP 4  ==  99000099
mayorCapicuaP 5  ==  9966006699

Leer más…

Definir la función

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

tal que (siguiente x ys) es justo el elemento siguiente a la primera ocurrencia de x en ys o Nothing si x no pertenece a ys. Por ejemplo,

siguiente 5 [3,5,2,5,7]                       ==  Just 2
siguiente 9 [3,5,2,5,7]                       ==  Nothing
siguiente 'd' "afdegdb"                       ==  Just 'e'
siguiente "todo" ["En","todo","la","medida"]  ==  Just "la"
siguiente "nada" ["En","todo","la","medida"]  ==  Nothing
siguiente 999999 [1..1000000]                 ==  Just 1000000
siguiente 1000000 [1..1000000]                ==  Nothing

Leer más…

Un número natural es polidivisible si cumple las siguientes condiciones:

• El número formado por sus dos primeros dígitos es divisible por 2.
• El número formado por sus tres primeros dígitos es divisible por 3.
• El número formado por sus cuatros primeros dígitos es divisible por 4.
• etcétera.

Por ejemplo, el número 345654 es un número polidivisible ya que

• 34 es divisible por 2,
• 345 es divisible por 3,
• 3456 es divisible por 4,
• 34565 es divisible por 5 y
• 345654 es divisible por 6.

pero 123456 no lo es, porque 1234 no es divisible por 4.

Definir las funciones

polidivisibles :: [Integer]
polidivisiblesN :: Integer -> [Integer]

tales que

• polidivisible es la sucesión cuyos elementos son los números polidivisibles. Por ejemplo,

λ> take 20 polidivisibles
[1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,22,24,26,28,30]
λ> take 10 (dropWhile (<100) polidivisibles)
[102,105,108,120,123,126,129,141,144,147]

• (polidivisiblesN k) es la lista de los números polidivisibles con k dígitos. Por ejemplo,

λ> polidivisiblesN 2
[10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,
 50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,
 90,92,94,96,98]

Comprobar que, para n entre 1 y 5, la cantidad de números polidivisibles de n dígitos es 9*10^(n-1)/n!.

Leer más…

Definir la función

posicion :: Array Int Bool -> Maybe Int

tal que (posicion v) es la menor posición del vector de booleanos v cuyo valor es falso y es Nothing si todos los valores son verdaderos. Por ejemplo,

posicion (listArray (0,4) [True,True,False,True,False]) == Just 2
posicion (listArray (0,4) [i <= 2 | i <- [0..4]])       == Just 3
posicion (listArray (0,4) [i <= 7 | i <- [0..4]])       == Nothing

Leer más…

Definir la función

divideSegun :: (a -> Bool) -> [a] -> [[a]]

tal que (divideSegun p xs) es la lista de los segmentos de xs cuyos elementos cumplen la propiedad p. Por ejemplo,

divideSegun even [3,5,2,7,6,8,9,1]  ==  [[3,5],[7],[9,1]]
divideSegun odd  [3,5,2,7,6,8,9,1]  ==  [[2],[6,8]]

Comprobar con QuickCheck que, para cualquier lista xs de números enteros, la concatenación de los elementos de (divideSegun even xs) es la lista de los elementos de xs que no son pares.

Leer más…

Definir la función

particiones :: Int -> [a] -> [[[a]]]

tal que (particiones n xs) es la lista de lista de n elementos cuya concatenación es xs. Por ejemplo,

λ> particiones 2 "abc"
[["","abc"],["a","bc"],["ab","c"],["abc",""]]
λ> particiones 3 "abc"
[["","","abc"],["","a","bc"],["","ab","c"],["","abc",""],
 ["a","","bc"],["a","b","c"],["a","bc",""],["ab","","c"],
 ["ab","c",""],["abc","",""]]
λ> length (particiones 4 "abc")
20

Leer más…

Definir la sucesión

naturales0 :: [Int]

cuyos elementos son los números naturales separados por 0. Por ejemplo,

λ> take 25 naturales0
[0,0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10,0,11,0,12]

Comprobar con QuickCheck que el n-ésimo término de la sucesión es n*(1+(-1)^n)/4.

Nota. En la comprobación usar

quickCheckWith (stdArgs {maxSize=7}) prop_naturales0

Leer más…

Definir la sucesión

enteros :: [Int]

tal que sus elementos son los números enteros comenzando en el 0 e intercalando los positivos y los negativos. Por ejemplo,

λ> take 23 enteros
[0,1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7,8,-8,9,-9,10,-10,11,-11]

Comprobar con QuickCheck que el n-ésimo término de la sucesión es (1-(2n+1)(-1)^n)/4.

Nota. En la comprobación usar

quickCheckWith (stdArgs {maxSize=7}) prop_naturales0

Leer más…

Definir la función

sustituye :: Eq a => [a] -> [a] -> [a] -> [a]

tal que (sustituye xs ys zs) es la lista obtenida sustituyendo las ocurrencias de xs en zs por ys. Por ejemplo,

sustituye "as" "_" "las casaderas"   ==  "l_ c_ader_"
sustituye "as" "es" "las casaderas"  ==  "les cesaderes"
sustituye "asa" "a" "las casaderas"  ==  "las caderas"
sustituye "asd" "a" "las casaderas"  ==  "las casaderas"

Leer más…

Definir la función

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

tal que (triparticiones xs) es la lista de las ternas (xs1,xs2,xs3) tales que su concatenación es xs. Por ejemplo,

λ> triparticiones "abc"
[("","","abc"),("","a","bc"),("","ab","c"),("","abc",""),
 ("a","","bc"),("a","b","c"),("a","bc",""),("ab","","c"),
 ("ab","c",""),("abc","","")]

Comprobar con QuickCheck que, suponiendo que xs es una lista de elementos comparables por igualdad, entonces para cada terna de (triparticiones xs) se cumple que la concatenación de sus elementos es xs.

Leer más…

Definir la función

conSuma :: (Eq a, Num a) => [a] -> [[a]] -> [[[a]]]

tal que (conSuma xs yss) es la lista de los vectores de xss cuya suma vectorial es xs. Por ejemplo,

λ> conSuma [9,10,12] [[4,7,3],[3,1,4],[5,3,9],[2,2,5]]
[[[4,7,3],[5,3,9]],[[4,7,3],[3,1,4],[2,2,5]]]
λ> conSuma [9,11,12] [[4,7,3],[3,1,4],[5,3,9],[2,2,5]]
[]

Leer más…

Definir la función

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

tal que (sumaVec xss) es la suma de los vectores de xss. Por ejemplo,

sumaVec [[4,7,3],[3,1,4],[2,2,5]]  ==  [9,10,12]
sumaVec [[4,7],[3,3],[1,4],[2,5]]  ==  [10,19]

Leer más…

Definir la función

ordenaSegun :: Ord b => (a -> b) -> [a] -> [a]

tal que (ordenaSegun f xs) es la lista obtenida ordenando los elementos de xs según sus valores mediante la función f. Por ejemplo,

ordenaSegun abs [-3,2,5,-2]                           ==  [2,-2,-3,5]
ordenaSegun abs [-3,-2,5,2]                           ==  [-2,2,-3,5]
ordenaSegun length ["pq","x","mn"]                    ==  ["x","pq","mn"]
[g 0 | g <- ordenaSegun (\f -> f 4) [(+5),(+2),(+3)]] == [2,3,5]

Comprobar con QuickCheck que (ordenaSegun id) es equivalente a sort.

Leer más…

Los puntos de una cuadrícula se puede representar mediante pares de números enteros

type Punto = (Int,Int)

y las regiones rectangulares mediante el siguiente tipo de dato

data Region = Rectangulo Punto  Punto
            | Union      Region Region
            | Diferencia Region Region
            deriving (Eq, Show)

donde

• (Rectangulo p1 p2) es la región formada por un rectángulo cuyo vértice superior izquierdo es p1 y su vértice inferior derecho es p2.
• (Union r1 r2) es la región cuyos puntos pertenecen a alguna de las regiones r1 y r2.
• (Diferencia r1 r2) es la región cuyos puntos pertenecen a la región r1 pero no pertenecen a la r2.

Definir la función

puntos :: Region -> [Punto]

tal que (puntos r) es la lista de puntos de la región r. Por ejemplo, usando las regiones definidas por

r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)