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)

se tiene

λ> puntos r0021
[(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)]
λ> puntos r3051
[(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)]
λ> puntos r4162
[(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)]
λ> puntos (Union r0021 r3051)
[(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)]
λ> puntos (Diferencia r3051 r4162)
[(3,0),(3,1),(4,0),(5,0)]
λ> puntos (Union (Diferencia r3051 r4162) r4162)
[(3,0),(3,1),(4,0),(5,0),(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)]

Comprobar con QuickCheck, usando la función enRegion definida en el ejercicio "Puntos en regiones rectangulares" que (enRegion p r) es equivalente a (p elem puntos r).

Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de regiones

import Test.QuickCheck
import Control.Monad

type Punto = (Int,Int)

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

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

puntos :: Region -> [Punto]
puntos = undefined

-- La propiedad es
prop_puntos :: Punto -> Region -> Bool
prop_puntos p r = undefined

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_puntos
--    +++ OK, passed 100 tests.

enRegion :: Punto -> Region -> Bool
enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) =
    x1 <= x && x <= x2 && y1 <= y && y <= y2
enRegion p (Union r1 r2)      = enRegion p r1 || enRegion p r2
enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2)

-- Generador de regiones:
instance Arbitrary Region where
    arbitrary = sized arb where
        arb 0         = liftM2 Rectangulo arbitrary arbitrary
        arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,
                               liftM2 Union sub sub,
                               liftM2 Diferencia sub sub]
              where sub = arb (n `div` 2)

Leer más…

Un segmento de una lista xs es una sublista de xs formada por elementos consecutivos en la lista. El problema de la máxima suma de segmentos consiste en dada una lista de números enteros calcular el máximo de las sumas de todos los segmentos de la lista. Por ejemplo, para la lista [-1,2,-3,5,-2,1,3,-2,-2,-3,6] la máxima suma de segmentos es 7 que es la suma del segmento [5,-2,1,3] y para la lista [-1,-2,-3] es 0 que es la suma de la lista vacía.

Definir la función

mss :: [Integer] -> Integer

tal que (mss xs) es la máxima suma de los segmentos de xs. Por ejemplo,

mss [-1,2,-3,5,-2,1,3,-2,-2,-3,6]  ==  7
mss [-1,-2,-3]                     ==  0
mss [1..500]                       ==  125250
mss [1..1000]                      ==  500500
mss [-500..3]                      ==  6
mss [-1000..3]                     ==  6

Leer más…

Definir la función

disjuntas :: Ord a => [a] -> [a] -> Bool

tal que (disjuntas xs ys) se verifica si las listas ordenadas crecientemente xs e ys son disjuntas. Por ejemplo,

disjuntas [2,5]   [1,4,7]                  ==  True
disjuntas [2,5,7] [1,4,7]                  ==  False
disjuntas [1..1000000] [3000000..4000000]  ==  True

Leer más…

Un triángulo de Herón es un triángulo tal que sus lados y su área son números enteros. Su nombre se debe al matemático griego Herón de Alejandría que descubrió la fórmula para calcular el área de un triángulo a partir de sus lados.

La fórmula de Herón dice que el área de un triángulo cuyos lados miden a, b y c es \[\sqrt{s(s-a)(s-b)(s-c)}\] donde s es el semiperímetro del triángulo; es decir, \[s=\frac{a+b+c}{2}\]

Un ejemplo de triángulo de Herón es el triángulo de lados 3, 4 y 5 cuya área es 6. Se puede observar que cualquier triángulo cuyos lados sean múltiplos de 3, 4 y 5 también es de Herón; por ejemplo, el de lados 6, 8 y 10 también lo es.

Se dice que un triángulo de Herón es primitivo si el máximo común divisor de sus lados es 1. Por ejemplo, el de lados 3, 4 y 5 es primitivo; pero el de lados 6, 8 y 10 no lo es.

Definir la sucesión

triangulosHeronPrimitivos :: [(Int,Int,Int)]

tal que sus elementos son los triángulos de Herón primitivos ordenados por su perímetro. Por ejemplo,

λ> take 7 triangulosHeronPrimitivos
[(3,4,5),(5,5,6),(5,5,8),(5,12,13),(4,13,15),(10,13,13),(9,10,17)]

Leer más…

Un número pitagórico es un número natural cuyo cuadrado se puede escribir como la suma de los cuadrados de dos números naturales no nulos; es decir, el número natural a es pitagórico si existen dos números naturales b y c distintos de cero tales que a² = b²+c². Por ejemplo, 5 es un número pitagórico ya que 5² = 3²+4² y también lo es 2015 ya que 2015² = 1612²+1209².

Definir la sucesión

pitagoricos :: [Integer]

cuyos elementos son los números pitagóricos. Por ejemplo,

λ> take 20 pitagoricos
[5,10,13,15,17,20,25,26,29,30,34,35,37,39,40,41,45,50,51,52]

Calcular la posición de 2015 en la sucesión.

Leer más…

Definir la función

cuadrados :: Int -> Float -> Picture

de forma que (cuadrados n) sea la animación obtenida rotando n cuadrados encajados como se muestra a continuación.

Nota: Escribir las soluciones usando la siguiente plantilla

import Graphics.Gloss
import System.IO

main :: IO ()
main = do
  hSetBuffering stdout NoBuffering
  putStr "Introduce el numero de cuadrados [1..10]: "
  n <- readLn
  animate (InWindow (show n ++ " cuadrados encajados rotando" )
                    (600,600) (20,20)) white (cuadrados n)

cuadrados :: Int -> Float -> Picture
cuadrados n t = undefined

Leer más…

Definir la función

   cuadrados :: Int -> Picture

tal que (cuadrados n) dibuje n cuadrados encajados como se muestra en las siguientes figuras:

• para n=2

• para n=4

• para n=10

Nota: Escribir las soluciones usando la siguiente plantilla

import Graphics.Gloss
import System.IO

main :: IO ()
main = do
  hSetBuffering stdout NoBuffering
  putStr "Introduce el numero de cuadrados [1..10]: "
  n <- readLn
  display (InWindow (show n ++ " cuadrados encajados" )
                    (600,600) (20,20)) white (cuadrados n)

cuadrados :: Int -> Picture
cuadrados n = undefined

Leer más…

El siguiente tipo de dato algebraico representa las fórmulas proposicionales construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negación (Neg) y la disyunción (Dis):

data Form = X
          | V
          | F
          | Neg Form
          | Dis Form Form
          deriving (Eq, Ord, Show)

Por ejemplo, la fórmula (¬X v V) se representa por (Dis (Neg X) V).

Definir las funciones

valor      :: Form -> Bool -> Bool
simplifica :: Form -> Form

tales que (valor p i) es el valor de la fórmula p cuando se le asigna a X el valor i. Por ejemplo,

valor (Neg X) True           ==  False
valor (Neg F) True           ==  True
valor (Dis X (Neg X)) True   ==  True
valor (Dis X (Neg X)) False  ==  True