El número 23 se puede escribir de 4 formas como suma de sus dígitos

2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3
2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3
2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3
2 + 3 + 3 + 3 + 3 + 3 + 3 + 3

La de menor número de sumando es la última, que tiene 8 sumandos.

Definir las funciones

minimoSumandosDigitos        :: Integer -> Integer
graficaMinimoSumandosDigitos :: Integer -> IO ()

tales que

• (minimoSumandosDigitos n) es el menor número de dígitos de n cuya suma es n. Por ejemplo,

minimoSumandosDigitos 23    ==  8
minimoSumandosDigitos 232   ==  78
minimoSumandosDigitos 2323  ==  775
map minimoSumandosDigitos [10..20] == [10,11,6,5,5,3,6,5,4,3,10]

• (graficaMinimoSumandosDigitos n) dibuja la gráfica de (minimoSumandosDigitos k) par los k primeros números naturales. Por ejemplo, (graficaMinimoSumandosDigitos 300) dibuja

Leer más…

Leer más…

La sucesión ECG estás definida por a(1) = 1, a(2) = 2 y, para n >= 3, a(n) es el menor natural que aún no está en la sucesión tal que a(n) tiene algún divisor común con a(n-1).

Los primeros términos de la sucesión son 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, ...

Al dibujar su gráfica, se parece a la de los electrocardiogramas (abreviadamente, ECG). Por ello, la sucesión se conoce como la sucesión ECG.

Definir las funciones

sucECG :: [Integer]
graficaSucECG :: Int -> IO ()

tales que

• sucECG es la lista de los términos de la sucesión ECG. Por ejemplo,

λ> take 20 sucECG
[1,2,4,6,3,9,12,8,10,5,15,18,14,7,21,24,16,20,22,11]
λ> sucECG !! 6000
6237

• (graficaSucECG n) dibuja la gráfica de los n primeros términos de la sucesión ECG. Por ejemplo, (graficaSucECG 160) dibuja

Leer más…

Una serie de potencias es una serie de la forma

a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, ...]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

type Serie a = [a]

Definir las siguientes funciones

opuesta      :: Num a => Serie a -> Serie a
suma         :: Num a => Serie a -> Serie a -> Serie a
resta        :: Num a => Serie a -> Serie a -> Serie a
producto     :: Num a => Serie a -> Serie a -> Serie a
cociente     :: Fractional a => Serie a -> Serie a -> Serie a
derivada     :: (Num a, Enum a) => Serie a -> Serie a
integral     :: (Fractional a, Enum a) => Serie a -> Serie a
expx         :: Serie Rational

tales que

• (opuesta xs) es la opuesta de la serie xs. Por ejemplo,

λ> take 7 (opuesta [-6,-4..])
[6,4,2,0,-2,-4,-6]

• (suma xs ys) es la suma de las series xs e ys. Por ejemplo,

λ> take 7 (suma [1,3..] [2,4..])
[3,7,11,15,19,23,27]

• (resta xs ys) es la resta de las series xs es ys. Por ejemplo,

λ> take 7 (resta [3,5..] [2,4..])
[1,1,1,1,1,1,1]
λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
[2,4,6,8,10,12,14]

• (producto xs ys) es el producto de las series xs e ys. Por ejemplo,

λ> take 7 (producto [3,5..] [2,4..])
[6,22,52,100,170,266,392]

• (cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
[2.0,4.0,6.0,8.0,10.0,12.0,14.0]

• (derivada xs) es la derivada de la serie xs. Por ejemplo,

λ> take 7 (derivada [2,4..])
[4,12,24,40,60,84,112]

• (integral xs) es la integral de la serie xs. Por ejemplo,

λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
[0.0,4.0,6.0,8.0,10.0,12.0,14.0]

• expx es la serie de la función exponencial. Por ejemplo,

λ> take 8 expx
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (derivada expx)
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (integral expx)
[0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Leer más…

Definir las funciones

grafo   :: [(Int,Int)] -> Grafo Int Int
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

• (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

λ> grafo [(2,4),(4,5)]
G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

• (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
[[1,3,5,7],[1,3,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
[[2,5,3,7],[2,5,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
[[1,3,5,2],[1,3,7,5,2]]
λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
[]
λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
109601

Leer más…

Definir la función

sinDobleCero :: Int -> [[Int]]

tal que (sinDobleCero n) es la lista de las listas de longitud n formadas por el 0 y el 1 tales que no contiene dos ceros consecutivos. Por ejemplo,

ghci> sinDobleCero 2
[[1,0],[1,1],[0,1]]
ghci> sinDobleCero 3
[[1,1,0],[1,1,1],[1,0,1],[0,1,0],[0,1,1]]
ghci> sinDobleCero 4
[[1,1,1,0],[1,1,1,1],[1,1,0,1],[1,0,1,0],[1,0,1,1],
 [0,1,1,0],[0,1,1,1],[0,1,0,1]]

Leer más…

Para cada entero positivo n, existe una única sucesión que empieza en 1, termina en n y en la que cada uno de sus elementos es el doble de su anterior o el doble más uno. Dicha sucesión se llama la sucesión duplicadora de n. Por ejemplo, la sucesión duplicadora de 13 es [1, 3, 6, 13], ya que

 3 = 2*1 +1
 6 = 2*3
13 = 2*6 +1

Definir la función

duplicadora :: Integer -> [Integer]

tal que (duplicadora n) es la sucesión duplicadora de n. Por ejemplo,

duplicadora 13                   ==  [1,3,6,13]
duplicadora 17                   ==  [1,2,4,8,17]
length (duplicadora (10^40000))  ==  132878

Leer más…

El complemento de un número positivo x se calcula por el siguiente procedimiento:

• si x es mayor que 9, se toma cada dígito por su valor posicional y se resta del mayor los otro dígitos. Por ejemplo, el complemento de 1448 es 1000 - 400 - 40 - 8 = 552. Para
• si x es menor que 10, su complemento es x.

Definir las funciones

cadena    :: Integer -> [Integer]
conCadena :: Int -> [Integer]

tales que

• (cadena x) es la cadena de primos a partir de x tal que cada uno es el complemento del anterior. Por ejemplo,

cadena 8         == []
cadena 7         == [7]
cadena 13        == [13,7]
cadena 643       == [643,557,443]
cadena 18127     == [18127,1873,127,73,67,53,47]
cadena 18181213  == [18181213,1818787,181213,18787,1213,787,613,587]

• (conCadena n) es la lista de números cuyas cadenas tienen n elementos. Por ejemplo,

take 6 (conCadena 3)                == [23,31,61,67,103,307]
[head (conCadena n) | n <- [4..8]]  == [37,43,157,18127,181873]

Leer más…

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

• f(0) es x
• f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

• Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, ...
• Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, ...
• Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, ...
• Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, ...
• Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, ...

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

• la generada por 2 converge a 2
• la generada por 3 converge a 26
• la generada por 4 converge a 4
• la generada por 5 converge a 26

Definir las siguientes funciones

omis           :: Integer -> [Integer]
rgencia        :: Integer -> Integer
caConvergencia :: [Integer] -> IO ()

 que

cLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,

λ> take 15 (sucLoomis 1)
[1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 2)
[2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 3)
[3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 4)
[4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
λ> take 15 (sucLoomis 5)
[5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 20)
[20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
λ> take 15 (sucLoomis 100)
[100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
λ> sucLoomis 1 !! (2*10^5)
235180736652

• (convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,

convergencia  2      ==  2
convergencia  3      ==  26
convergencia  4      ==  4
convergencia 17      ==  38
convergencia 19      ==  102
convergencia 43      ==  162
convergencia 27      ==  202
convergencia 58      ==  474
convergencia 63      ==  150056
convergencia 81      ==  150056
convergencia 89      ==  150056
convergencia (10^12) ==  1000101125092

• (graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja

Leer más…

El problema de las N reinas consiste en colocar N reinas en tablero rectangular de dimensiones N por N de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal. Por ejemplo, una solución para el problema de las 4 reinas es

|---|---|---|---|
|   | R |   |   |
|---|---|---|---|
|   |   |   | R |
|---|---|---|---|
| R |   |   |   |
|---|---|---|---|
|   |   | R |   |
|---|---|---|---|

Los estados del problema de las N reinas son los tableros con las reinas colocadas. Inicialmente el tablero está vacío y, en cda paso se coloca una reina en la primera columna en la que aún no hay ninguna reina.

Cada estado se representa por una lista de números que indican las filas donde se han colocado las reinas. Por ejemplo, el tablero anterior se representa por [2,4,1,3].

Usando la librería de árboles Data.Tree, definir las funciones

arbolReinas :: Int -> Tree [Int]
nEstados    :: Int -> Int
soluciones  :: Int -> [[Int]]
nSoluciones :: Int -> Int

tales que

• (arbolReinas n) es el árbol de estados para el problema de las n reinas. Por ejemplo,

λ> putStrLn (drawTree (fmap show (arbolReinas 4)))
[]
|
+- [1]
|  |
|  +- [3,1]
|  |
|  `- [4,1]
|     |
|     `- [2,4,1]
|
+- [2]
|  |
|  `- [4,2]
|     |
|     `- [1,4,2]
|        |
|        `- [3,1,4,2]
|
+- [3]
|  |
|  `- [1,3]
|     |
|     `- [4,1,3]
|        |
|        `- [2,4,1,3]
|
`- [4]
   |
   +- [1,4]
   |  |
   |  `- [3,1,4]
   |
   `- [2,4]

λ> putStrLn (drawTree (fmap show (arbolReinas 5)))
[]
|
+- [1]
|  |
|  +- [3,1]
|  |  |
|  |  `- [5,3,1]
|  |     |
|  |     `- [2,5,3,1]
|  |        |
|  |        `- [4,2,5,3,1]
|  |
|  +- [4,1]
|  |  |
|  |  `- [2,4,1]
|  |     |
|  |     `- [5,2,4,1]
|  |        |
|  |        `- [3,5,2,4,1]
|  |
|  `- [5,1]
|     |
|     `- [2,5,1]
|
+- [2]
|  |
|  +- [4,2]
|  |  |
|  |  `- [1,4,2]
|  |     |
|  |     `- [3,1,4,2]
|  |        |
|  |        `- [5,3,1,4,2]
|  |
|  `- [5,2]
|     |
|     +- [1,5,2]
|     |  |
|     |  `- [4,1,5,2]
|     |
|     `- [3,5,2]
|        |
|        `- [1,3,5,2]
|           |
|           `- [4,1,3,5,2]
|
+- [3]
|  |
|  +- [1,3]
|  |  |
|  |  `- [4,1,3]
|  |     |
|  |     `- [2,4,1,3]
|  |        |
|  |        `- [5,2,4,1,3]
|  |
|  `- [5,3]
|     |
|     `- [2,5,3]
|        |
|        `- [4,2,5,3]
|           |
|           `- [1,4,2,5,3]
|
+- [4]
|  |
|  +- [1,4]
|  |  |
|  |  +- [3,1,4]
|  |  |  |
|  |  |  `- [5,3,1,4]
|  |  |     |
|  |  |     `- [2,5,3,1,4]
|  |  |
|  |  `- [5,1,4]
|  |     |
|  |     `- [2,5,1,4]
|  |
|  `- [2,4]
|     |
|     `- [5,2,4]
|        |
|        `- [3,5,2,4]
|           |
|           `- [1,3,5,2,4]
|
`- [5]
   |
   +- [1,5]
   |  |
   |  `- [4,1,5]
   |
   +- [2,5]
   |  |
   |  `- [4,2,5]
   |     |
   |     `- [1,4,2,5]
   |        |
   |        `- [3,1,4,2,5]
   |
   `- [3,5]
      |
      `- [1,3,5]
         |
         `- [4,1,3,5]
            |
            `- [2,4,1,3,5]

• (nEstados n) es el número de estados en el problema de las n reinas. Por ejemplo,

nEstados 4            ==  17
nEstados 5            ==  54
map nEstados [0..10]  ==  [1,2,3,6,17,54,153,552,2057,8394,35539]

• (soluciones n) es la lista de estados que son soluciones del problema de las n reinas. Por ejemplo,

λ> soluciones 4
[[3,1,4,2],[2,4,1,3]]
λ> soluciones 5
[[4,2,5,3,1],[3,5,2,4,1],[5,3,1,4,2],[4,1,3,5,2],[5,2,4,1,3],
 [1,4,2,5,3],[2,5,3,1,4],[1,3,5,2,4],[3,1,4,2,5],[2,4,1,3,5]]

• (nSoluciones n) es el número de soluciones del problema de las n reinas. Por ejemplo,

nSoluciones 4            ==  2
nSoluciones 5            ==  10
map nSoluciones [0..10]  ==  [1,1,0,0,2,10,4,40,92,352,724]

Leer más…

La codificación de Fibonacci de un número n es una cadena d = d(0)d(1)...d(k-1)d(k) de ceros y unos tal que

n = d(0)*F(2) + d(1)*F(3) +...+ d(k-1)*F(k+1)
d(k-1) = d(k) = 1

donde F(i) es el i-ésimo término de la sucesión de Fibonacci.

0,1,1,2,3,5,8,13,21,34,...

Por ejemplo. La codificación de Fibonacci de 4 es "1011" ya que los dos últimos elementos son iguales a 1 y

1*F(2) + 0*F(3) + 1*F(4) = 1*1 + 0*2 + 1*3 = 4

La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla

 1  = 1     = F(2)           ≡       11
 2  = 2     = F(3)           ≡      011
 3  = 3     = F(4)           ≡     0011
 4  = 1+3   = F(2)+F(4)      ≡     1011
 5  = 5     = F(5)           ≡    00011
 6  = 1+5   = F(2)+F(5)      ≡    10011
 7  = 2+5   = F(3)+F(5)      ≡    01011
 8  = 8     = F(6)           ≡   000011
 9  = 1+8   = F(2)+F(6)      ≡   100011
10  = 2+8   = F(3)+F(6)      ≡   010011
11  = 3+8   = F(4)+F(6)      ≡   001011
12  = 1+3+8 = F(2)+F(4)+F(6) ≡   101011
13  = 13    = F(7)           ≡  0000011
14  = 1+13  = F(2)+F(7)      ≡  1000011

Definir la función

codigoFib :: Integer -> String

tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,

λ> codigoFib 65
"0100100011"
λ> [codigoFib n | n <- [1..7]]
["11","011","0011","1011","00011","10011","01011"]

Leer más…

Los números de Perrin se definen por la elación de recurrencia

P(n) = P(n - 2) + P(n - 3) si n > 2,

con los valores iniciales

P(0) = 3, P(1) = 0 y P(2) = 2.

Definir la sucesión

sucPerrin :: [Integer]

cuyos elementos son los números de Perrin. Por ejemplo,

λ> take 15 sucPerrin
[3,0,2,3,2,5,5,7,10,12,17,22,29,39,51]
λ> length (show (sucPerrin !! (2*10^5)))
24425

Comprobar con QuickCheck si se verifica la siguiente propiedad: para todo entero n > 1, el n-ésimo término de la sucesión de Perrin es divisible por n si y sólo si n es primo.

Leer más…

Definir la función

frecuencias :: Ord a => [a] -> Map a Int

tal que (frecuencias xs) es el diccionario formado por los elementos de xs junto con el número de veces que aparecen en xs. Por ejemplo,

λ> frecuencias "sosos"
fromList [('o',2),('s',3)]
λ> frecuencias (show (10^100))
fromList [('0',100),('1',1)]
λ> frecuencias (take (10^6) (cycle "abc"))
fromList [('a',333334),('b',333333),('c',333333)]
λ> size (frecuencias (take (10^6) (cycle [1..10^6])))
1000000

Leer más…

Los polinomios se pueden representar mediante diccionarios con los exponentes como claves y los coeficientes como valores.

El tipo de los polinomios con coeficientes de tipo a se define por

type Polinomio a = M.Map Int a

Dos ejemplos de polinomios (que usaremos en los ejemplos) son

3 + 7x - 5x^3
4 + 5x^3 + x^5

se definen por

ejPol1, ejPol2 :: Polinomio Int
ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
ejPol2 = M.fromList [(0,4),(3,5),(5,1)]

Definir las funciones

sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a

tales que

• (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,

λ> sumaPol ejPol1 ejPol2
fromList [(0,7),(1,7),(5,1)]
λ> sumaPol ejPol1 ejPol1
fromList [(0,6),(1,14),(3,-10)]

• (multPorTerm (n,a) p) es el producto del término ax^n por p. Por ejemplo,

λ> multPorTerm (2,3) (M.fromList [(0,4),(2,1)])
fromList [(2,12),(4,3)]

• (multPol p q) es el producto de los polinomios p y q. Por ejemplo,

λ> multPol ejPol1 ejPol2
fromList [(0,12),(1,28),(3,-5),(4,35),(5,3),(6,-18),(8,-5)]
λ> multPol ejPol1 ejPol1
fromList [(0,9),(1,42),(2,49),(3,-30),(4,-70),(6,25)]
λ> multPol ejPol2 ejPol2
fromList [(0,16),(3,40),(5,8),(6,25),(8,10),(10,1)]

Leer más…

Una cadena de divisores de un número n es una lista donde cada elemento es un divisor de su siguiente elemento en la lista. Por ejemplo, las cadenas de divisores de 12 son [2,4,12], [2,6,12], [2,12], [3,6,12], [3,12], [4,12], [6,12] y [12].

Definir la función

cadenasDivisores :: Int -> [[Int]]

tal que (cadenasDivisores n) es la lista de las cadenas de divisores de n. Por ejemplo,

λ> cadenasDivisores 12
[[2,4,12],[2,6,12],[2,12],[3,6,12],[3,12],[4,12],[6,12],[12]]
λ> length (cadenaDivisores 48)
48
λ> length (cadenaDivisores 120)
132

Leer más…

La sucesión fractal

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

está construida de la siguiente forma:

• los términos pares forman la sucesión de los números naturales

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

• los términos impares forman la misma sucesión original

0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

Definir las funciones

sucFractal     :: [Integer]
sumaSucFractal :: Integer -> Integer

tales que

• sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,

take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]
sucFractal !! 30     == 15
sucFractal !! (10^7) == 5000000

• (sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,

sumaSucFractal 10      == 13
sumaSucFractal (10^5)  == 1666617368
sumaSucFractal (10^10) == 16666666661668691669
sumaSucFractal (10^15) == 166666666666666166673722792954
sumaSucFractal (10^20) == 1666666666666666666616666684103392376198
length (show (sumaSucFractal (10^15000))) == 30000
sumaSucFractal (10^15000) `mod` (10^9)    == 455972157

Leer más…

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

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

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

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

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

Definir la función

caminoMaxSuma :: Matrix Int -> [Int]

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

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

Leer más…

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

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

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

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

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

Definir la función

maximaSuma :: Matrix Int -> Int

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

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

Leer más…

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

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

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

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

Definir la función

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

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

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

Nota: Se recomiend usar programación dinámica.

Leer más…

Definir la función

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

tal que (longitudMayorSublistaCreciente xs) es la el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]
3
λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]
6
λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
6
λ> longitudMayorSublistaCreciente [1..2000]
2000
λ> longitudMayorSublistaCreciente [2000,1999..1]
1
λ> import System.Random
λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
λ> longitudMayorSublistaCreciente2 xs
61
λ> longitudMayorSublistaCreciente3 xs
61

Nota: Se puede usar programación dinámica para aumentar la eficiencia.

Leer más…

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

Definir las funciones

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

tales que

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

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

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

Leer más…

Un conjunto de primos emparejables es un conjunto S de números primos tales que al concatenar cualquier par de elementos de S se obtiene un número primo. Por ejemplo, {3, 7, 109, 673} es un conjunto de primos emparejables ya que sus elementos son primos y las concatenaciones de sus parejas son 37, 3109, 3673, 73, 7109, 7673, 1093, 1097, 109673, 6733, 6737 y 673109 son primos.

Definir la función

emparejables :: Integer -> Integer -> [[Integer]]

tal que (emparejables n m) es el conjunto de los conjuntos emparejables de n elementos menores que n. Por ejemplo,

take 5 (emparejables 2   10)  ==  [[3,7]]
take 5 (emparejables 3   10)  ==  []
take 5 (emparejables 2  100)  ==  [[3,7],[3,11],[3,17],[3,31],[3,37]]
take 5 (emparejables 3  100)  ==  [[3,37,67],[7,19,97]]
take 5 (emparejables 4  100)  ==  []
take 5 (emparejables 4 1000)  ==  [[3,7,109,673],[23,311,677,827]]

Leer más…

Un número con n dígitos es pandigital si contiene todos los dígitos del 1 a n exactamente una vez. Por ejemplo, 2143 es un pandigital con 4 dígitos y, además, es primo.

Definir la constante

pandigitalesPrimos :: [Int]

tal que sus elementos son los números pandigitales, ordenados de mayor a menor. Por ejemplo,

take 3 pandigitalesPrimos       ==  [7652413,7642513,7641253]
2143 `elem` pandigitalesPrimos  ==  True
length pandigitalesPrimos       ==  538

Leer más…

Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,

|2 5 1 6|       |2 5 1 6|
|4 2 5 1|       |4 2 6 1|
|7 4 2 5|       |7 4 2 5|
|9 7 4 2|       |9 7 4 2|

la primera es una matriz de Toeplitz y la segunda no lo es.

Las anteriores matrices se pueden definir por

ej1, ej2 :: Array (Int,Int) Int
ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2]
ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]

Definir la función

esToeplitz :: Eq a => Array (Int,Int) a -> Bool

tal que (esToeplitz p) se verifica si la matriz p es de Toeplitz. Por ejemplo,

esToeplitz ej1  ==  True
esToeplitz ej2  ==  False

Leer más…

El período de una lista xs es la lista más corta ys tal que xs se puede obtener concatenando varias veces la lista ys. Por ejemplo, el período "abababab" es "ab" ya que "abababab" se obtiene repitiendo tres veces la lista "ab".

Definir la función

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

tal que (periodo xs) es el período de xs. Por ejemplo,

periodo "ababab"      ==  "ab"
periodo "buenobueno"  ==  "bueno"
periodo "oooooo"      ==  "o"
periodo "sevilla"     ==  "sevilla"

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
mayorCapicuaP 6  ==  999000000999
mayorCapicuaP 7  ==  99956644665999

Leer más…

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

• Inicialmente todas las puertas están cerradas.
• El primer camarero cambia de estado las puertas de todas las habitaciones.
• El segundo cambia de estado de las puertas de las habitaciones pares.
• El tercero cambia de estado todas las puertas que son múltiplos de 3.
• El cuarto cambia de estado todas las puertas que son múltiplos de 4
• Así hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

Pase    | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5
Inicial | Cerrada  | Cerrada  | Cerrada  | Cerrada  | Cerrada
Pase 1  | Abierta  | Abierta  | Abierta  | Abierta  | Abierta
Pase 2  | Abierta  | Cerrada  | Abierta  | Cerrada  | Abierta
Pase 3  | Abierta  | Cerrada  | Cerrada  | Cerrada  | Abierta
Pase 4  | Abierta  | Cerrada  | Cerrada  | Abierta  | Abierta
Pase 5  | Abierta  | Cerrada  | Cerrada  | Abierta  | Cerrada

Los estados de las puertas se representan por el siguiente tipo de datos

data Estado = Abierta | Cerrada deriving Show

Definir la función

final :: Int -> [Estado]

tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,

λ> final 5
[Abierta,Cerrada,Cerrada,Abierta,Cerrada]
λ> final 7
[Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]

Leer más…

El sistema D'Hondt es una fórmula creada por Victor d'Hondt, que permite obtener el número de cargos electos asignados a las candidaturas, en proporción a los votos conseguidos.

Tras el recuento de los votos, se calcula una serie de divisores para cada partido. La fórmula de los divisores es V/N, donde V representa el número total de votos recibidos por el partido, y N representa cada uno de los números enteros desde 1 hasta el número de cargos electos de la circunscripción objeto de escrutinio. Una vez realizadas las divisiones de los votos de cada partido por cada uno de los divisores desde 1 hasta N, la asignación de cargos electos se hace ordenando los cocientes de las divisiones de mayor a menor y asignando a cada uno un escaño hasta que éstos se agoten

Definir la función

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

tal que (reparto n vs) es la lista de los pares formados por los números de los partidos y el número de escaño que les corresponden al repartir n escaños en función de la lista de sus votos. Por ejemplo,

λ> reparto 7 [340000,280000,160000,60000,15000]
[(1,3),(2,3),(3,1)]
λ> reparto 21 [391000,311000,184000,73000,27000,12000,2000]
[(1,9),(2,7),(3,4),(4,1)]

es decir, en el primer ejemplo,

• al 1º partido (que obtuvo 340000 votos) le corresponden 3 escaños,
• al 2º partido (que obtuvo 280000 votos) le corresponden 3 escaños,
• al 3º partido (que obtuvo 160000 votos) le corresponden 1 escaño.

Leer más…

La conjetura de las familias estables por uniones fue planteada por Péter Frankl en 1979 y aún sigue abierta.

Una familia de conjuntos es estable por uniones si la unión de dos conjuntos cualesquiera de la familia pertenece a la familia. Por ejemplo, {∅, {1}, {2}, {1,2}, {1,3}, {1,2,3}} es estable por uniones; pero {{1}, {2}, {1,3}, {1,2,3}} no lo es.

La conjetura afirma que toda familia no vacía estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de la familia.

Definir las funciones

esEstable :: Ord a => Set (Set a) -> Bool
familiasEstables :: Ord a => Set a -> Set (Set (Set a))
mayoritarios :: Ord a => Set (Set a) -> [a]
conjeturaFrankl :: Int -> Bool

tales que

• (esEstable f) se verifica si la familia f es estable por uniones. Por ejemplo,

λ> esEstable (fromList [empty, fromList [1,2], fromList [1..5]])
True
λ> esEstable (fromList [empty, fromList [1,7], fromList [1..5]])
False
λ> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]])
True

• (familiasEstables c) es el conjunto de las familias estables por uniones formadas por elementos del conjunto c. Por ejemplo,

λ> familiasEstables (fromList [1..2])
fromList
  [ fromList []
  , fromList [fromList []]
  , fromList [fromList [],fromList [1]]
  , fromList [fromList [],fromList [1],fromList [1,2]],
    fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]
  , fromList [fromList [],fromList [1,2]]
  , fromList [fromList [],fromList [1,2],fromList [2]]
  , fromList [fromList [],fromList [2]]
  , fromList [fromList [1]]
  , fromList [fromList [1],fromList [1,2]]
  , fromList [fromList [1],fromList [1,2],fromList [2]]
  , fromList [fromList [1,2]]
  , fromList [fromList [1,2],fromList [2]]
  , fromList [fromList [2]]]
λ> size (familiasEstables (fromList [1,2]))
14
λ> size (familiasEstables (fromList [1..3]))
122
λ> size (familiasEstables (fromList [1..4]))
4960

• (mayoritarios f) es la lista de elementos que pertenecen al menos a la mitad de los conjuntos de la familia f. Por ejemplo,

mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3]
mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == []

• (conjeturaFrankl n) se verifica si para toda familia f formada por elementos del conjunto {1,2,...,n} no vacía, estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de f. Por ejemplo.

conjeturaFrankl 2  ==  True
conjeturaFrankl 3  ==  True
conjeturaFrankl 4  ==  True

Leer más…

Un número de Aquiles es un número natural n que es potente (es decir, si p es un divisor primo de n, entonces p² también lo es) y no es una potencia perfecta (es decir, no existen números naturales m y k tales que n es igual a m^k). Por ejemplo,

• 108 es un número de Aquiles proque es un número potente (ya que su factorización es 2^2 · 3^3, sus divisores primos son 2 and 3 y sus cuadrados (2^2 = 4 y 3^2 = 9) son divisores de 108. Además, 108 no es una potencia perfecta.
• 360 no es un número de Aquiles ya que 5 es un divisor primo de 360, pero 5^2 = 15 no lo es.
• 784 no es un número de Aquiles porque, aunque es potente, es una potencia perfecta ya que 784 = 28^2.

Los primeros números de Aquiles son

72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, ...

Definir las funciones

esAquiles              :: Integer -> Bool
huecosDeAquiles        :: [Integer]
graficaHuecosDeAquiles :: Int -> IO ()

tales que

• (esAquiles x) se verifica si x es un número de Aquiles. Por ejemplo,

esAquiles 108         ==  True
esAquiles 360         ==  False
esAquiles 784         ==  False
esAquiles 5425069447  ==  True
esAquiles 5425069448  ==  True

• huecosDeAquiles es la sucesión de la diferencias entre los números de Aquiles consecutivos. Por ejemplo,

λ> take 15 huecosDeAquiles
[36,92,88,104,40,68,148,27,125,64,104,4,153,27,171]

• (graficaHuecosDeAquiles n) dibuja la gráfica de los n primeros huecos de Aquiles. Por ejemplo, (graficaHuecosDeAquiles 160) dibuja

Leer más…

Definir las funciones

minimasDistancias             :: Matrix Int -> Matrix Int
sumaMinimaDistanciasIdentidad :: Int -> Int

tales que

• (mininasDistancias a) es la matriz de las mínimas distancias de cada elemento de a hasta alcanzar un 1 donde un paso es un movimiento hacia la izquierda, derecha, arriba o abajo. Por ejemplo,

λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]])
( 1 0 0 )
( 2 1 0 )
λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]])
( 1 1 0 )
( 0 1 1 )
λ> minimasDistancias (identity 5)
( 0 1 2 3 4 )
( 1 0 1 2 3 )
( 2 1 0 1 2 )
( 3 2 1 0 1 )
( 4 3 2 1 0 )

• (sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las mínimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo,

sumaMinimaDistanciasIdentidad 5       ==  40
sumaMinimaDistanciasIdentidad (10^2)  ==  333300
sumaMinimaDistanciasIdentidad (10^4)  ==  333333330000
sumaMinimaDistanciasIdentidad (10^6)  ==  333333333333000000

Leer más…

Definir la función

tieneCombinacionDivisible :: [Int] -> Int -> Bool

tal que (tieneCombinacionDivisible xs m) se verifica si existe alguna forma de combinar todos los elementos de la lista (con las operaciones suma o resta) de forma que el resultado sea divisible por m. Por ejemplo,

tieneCombinacionDivisible [1,3,4,6] 4  ==  True
tieneCombinacionDivisible [1,3,9]   2  ==  False

En el primer ejemplo, 1 - 2 + 3 + 4 + 6 = 12 es una combinación divisible por 4. En el segundo ejemplo, las combinaciones de [1,3,9] son

 1 + 3 + 9 =  13
-1 + 3 + 9 =  11
 1 - 3 + 9 =   7
-1 - 3 + 9 =   5
 1 + 3 - 9 =  -5
-1 + 3 - 9 =  -7
 1 - 3 - 9 = -11
-1 - 3 - 9 = -13

y ninguna de las 4 es divisible por 2.

Leer más…

Los segmentos iniciales de [3,1,2,5] son [3], [3,1], [3,1,2] y [3,1,2,5]. Sus sumas son 3, 4, 6 y 9, respectivamente. La suma de dichas sumas es 24.

Definir la función

sumaSegmentosIniciales :: [Integer] -> Integer

tal que (sumaSegmentosIniciales xs) es la suma de las sumas de los segmentos iniciales de xs. Por ejemplo,

sumaSegmentosIniciales [3,1,2,5]     ==  24
sumaSegmentosIniciales3 [1..3*10^6]  ==  4500004500001000000

Comprobar con QuickCheck que la suma de las sumas de los segmentos iniciales de la lista formada por n veces el número uno es el n-ésimo número triangular; es decir que

sumaSegmentosIniciales (genericReplicate n 1)

es igual a

n * (n + 1) `div` 2

Leer más…

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol = N Int [Arbol]
     deriving Show

Por ejemplo, los árboles

     1             1             1
    /  \          / \           / \
   /    \        8   3         8   3
  2      6          /|\       /|\  |
 / \    / \        4 2 6     4 5 6 2
4   5  5   7

se representan por

ej1, ej2, ej3 :: Arbol
ej1 = N 1 [N 2 [N 4 [], N 5 []], N 6 [N 5 [], N 7 []]]
ej2 = N 1 [N 8 [], N 3 [N 4 [], N 2 [], N 6 []]]
ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 2 []]]

Definir la función

hojasEnNoDecreciente :: Arbol -> [Int]

tal que (hojasEnNoDecreciente a) es el conjunto de las hojas de a que se encuentran en alguna rama no decreciente. Por ejemplo,

hojasEnNoDecreciente ej1  ==  [4,5,7]
hojasEnNoDecreciente ej2  ==  [4,6,8]
hojasEnNoDecreciente ej3  ==  []

Leer más…

Las matrices de Hadamard se definen recursivamente como sigue

λ> hadamard 0
( 1 )

λ> hadamard 1
(  1  1 )
(  1 -1 )

λ> hadamard 2
(  1  1  1  1 )
(  1 -1  1 -1 )
(  1  1 -1 -1 )
(  1 -1 -1  1 )

λ> hadamard 3
(  1  1  1  1  1  1  1  1 )
(  1 -1  1 -1  1 -1  1 -1 )
(  1  1 -1 -1  1  1 -1 -1 )
(  1 -1 -1  1  1 -1 -1  1 )
(  1  1  1  1 -1 -1 -1 -1 )
(  1 -1  1 -1 -1  1 -1  1 )
(  1  1 -1 -1 -1 -1  1  1 )
(  1 -1 -1  1 -1  1  1 -1 )

En general, la n-ésima matriz de Hadamard, H(n), es

( H(n-1)  H(n-1) )
( H(n-1) -H(n-1) )

Definir la función

hadamard :: Int -> Matrix Int

tal que (hadamard n) es la n-ésima matriz de Hadamard.

Comprobar con QuickCheck que para todo número natural n, el producto de la n-ésima matriz de Hadamard y su traspuesta es igual al producto de 2^n por la matriz identidad de orden 2^n.

Leer más…

Definir la función

menorNoSuma :: [Integer] -> Integer

tal que (menorNoSuma xs) es el menor número que no se puede escribir como suma de un subconjunto de xs, donde se supone que xs es un conjunto de números enteros positivos. Por ejemplo,

menorNoSuma [6,1,2]    ==  4
menorNoSuma [1,2,3,9]  ==  7
menorNoSuma [5]        ==  1
menorNoSuma [1..20]    ==  211
menorNoSuma [1..10^6]  ==  500000500001

Comprobar con QuickCheck que para todo n,

menorNoSuma [1..n] == 1 + sum [1..n]

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

ordenDeDivisibilidad :: Integer -> Int

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

ordenDeDivisibilidad 74156                      ==  3
ordenDeDivisibilidad 3608528850368400786036725  ==  25

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

Leer más…

En 1999, L.J. Lange publicó el artículo An elegant new continued fraction for π.

En el primer teorema del artículo se demuestra la siguiente expresión de π mediante una fracción continua

La primeras aproximaciones son

a(1) = 3+1                = 4.0
a(2) = 3+(1/(6+9))        = 3.066666666666667
a(3) = 3+(1/(6+9/(6+25))) = 3.158974358974359

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: [Int] -> IO ()

tales que

• (aproximacionPi n) es la n-ésima aproximación de pi con la fracción continua de Lange. Por ejemplo,

aproximacionPi 1     ==  4.0
aproximacionPi 2     ==  3.066666666666667
aproximacionPi 3     ==  3.158974358974359
aproximacionPi 10    ==  3.141287132741557
aproximacionPi 100   ==  3.141592398533554
aproximacionPi 1000  ==  3.1415926533392926

• (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..10]) dibuja (grafica [10..100]) dibuja y (grafica [100..200]) dibuja

Leer más…

En el artículo El desarrollo más bello de Pi como suma infinita, Miguel Ángel Morales comenta el desarrollo de pi publicado por Leonhard Euler en su libro "Introductio in Analysis Infinitorum" (1748).

El desarrollo es el siguiente y se obtiene a partir de la serie armónica modificando sólo el signo de algunos términos según el siguiente criterio:

• Dejamos un + cuando el denominador de la fracción sea un 2 o un primo de la forma 4m-1.
• Cambiamos a - si el denominador de la fracción es un primo de la forma 4m+1.
• Si el número es compuesto ponemos el signo que quede al multiplicar los signos correspondientes a cada factor.

Por ejemplo,

• la de denominador 3 = 4x1-1 lleva un +,
• la de denominador 5 = 4x1+1 lleva un -,
• la de denominador 13 = 4x3+1 lleva un -,
• la de denominador 6 = 2x3 lleva un + (porque los dos llevan un +),
• la de denominador 10 = 2x5 lleva un - (porque el 2 lleva un + y el 5 lleva un -) y
• la de denominador 50 = 5x5x2 lleva un + (un - por el primer 5, otro - por el segundo 5 y un + por el 2).

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: Int -> IO ()

tales que

• (aproximacionPi n) es la aproximación de pi obtenida sumando los n primeros términos de la serie de Euler. Por ejemplo.

aproximacionPi 1        ==  1.0
aproximacionPi 10       ==  2.3289682539682537
aproximacionPi 100      ==  2.934318000847734
aproximacionPi 1000     ==  3.0603246224585128
aproximacionPi 10000    ==  3.1105295744825403
aproximacionPi 100000   ==  3.134308801935256
aproximacionPi 1000000  ==  3.1395057903490806

• (grafica n) dibuja la gráfica de las aproximaciones de pi usando k sumando donde k toma los valores de la lista [100,110..n]. Por ejemplo, al evaluar (grafica 4000) se obtiene

Leer más…

Se pueden generar los dígitos de Pi, como se explica en el artículo Unbounded spigot algorithms for the digits of pi c0on la función digitosPi definida por

digitosPi :: [Integer]
digitosPi = g(1,0,1,1,3,3) where
g (q,r,t,k,n,l) =
if 4*q+r-t < n*t
then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)
else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

Por ejemplo,

λ> take 25 digitosPi
[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3]

La distribución de los primeros 25 dígitos de pi es [0,2,3,5,3,3,3,1,2,3] ya que el 0 no aparece, el 1 ocurre 2 veces, el 3 ocurre 3 veces, el 4 ocurre 5 veces, ...

Usando digitosPi, definir las siguientes funciones

distribucionDigitosPi :: Int -> [Int]
frecuenciaDigitosPi   :: Int -> [Double]

tales que

• (distribucionDigitosPi n) es la distribución de los n primeros dígitos de pi. Por ejemplo,

λ> distribucionDigitosPi 10
[0,2,1,2,1,2,1,0,0,1]
λ> distribucionDigitosPi 100
[8,8,12,12,10,8,9,8,12,13]
λ> distribucionDigitosPi 1000
[93,116,103,103,93,97,94,95,101,105]
λ> distribucionDigitosPi 5000
[466,531,496,460,508,525,513,488,492,521]

• (frecuenciaDigitosPi n) es la frecuencia de los n primeros dígitos de pi. Por ejemplo,

λ> frecuenciaDigitosPi 10
[0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0]
λ> frecuenciaDigitosPi 100
[8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0]
λ> frecuenciaDigitosPi 1000
[9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5]
λ> frecuenciaDigitosPi 5000
[9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

Leer más…

La fórmula de Gregory-Leibniz para calcular pi es

y la de Beeler es

Definir las funciones

aproximaPiGL     :: Int -> Double
aproximaPiBeeler :: Int -> Double
graficas         :: [Int] -> IO ()

tales que

• (aproximaPiGL n) es la aproximación de pi con los primeros n términos de la fórmula de Gregory-Leibniz. Por ejemplo,

aproximaPiGL 1       ==  4.0
aproximaPiGL 2       ==  2.666666666666667
aproximaPiGL 3       ==  3.466666666666667
aproximaPiGL 10      ==  3.0418396189294032
aproximaPiGL 100     ==  3.1315929035585537
aproximaPiGL 1000    ==  3.140592653839794
aproximaPiGL 10000   ==  3.1414926535900345
aproximaPiGL 100000  ==  3.1415826535897198

• (aproximaPiBeeler n) es la aproximación de pi con los primeros n términos de la fórmula de Beeler. Por ejemplo,

aproximaPiBeeler 1   ==  2.0
aproximaPiBeeler 2   ==  2.6666666666666665
aproximaPiBeeler 3   ==  2.933333333333333
aproximaPiBeeler 10  ==  3.140578169680337
aproximaPiBeeler 60  ==  3.141592653589793
pi                   ==  3.141592653589793

• (graficas xs) dibuja la gráfica de las k-ésimas aproximaciones de pi, donde k toma los valores de la lista xs, con las fórmulas de Gregory-Leibniz y de Beeler. Por ejemplo, (graficas [1..25]) dibuja donde la línea morada corresponde a la aproximación de Gregory-Leibniz y la verde a la de Beeler.

Leer más…

El producto de Wallis es una expresión, descubierta por John Wallis en 1655, para representar el valor de π y que establece que:

 π     2     2     4     4     6     6     8     8
--- = --- · --- · --- · --- · --- · --- · --- · --- ···
 2     1     3     3     5     5     7     7     9

Definir las funciones

factoresWallis  :: [Rational]
productosWallis :: [Rational]
aproximacionPi  :: Int -> Double
errorPi         :: Double -> Int

ales que

• factoresWallis es la sucesión de los factores del productos de Wallis. Por ejemplo,

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

• productosWallis es la sucesión de los productos de los primeros factores de Wallis. Por ejemplo,

λ> take 7 productosWallis
[2 % 1,4 % 3,16 % 9,64 % 45,128 % 75,256 % 175,2048 % 1225]

• (aproximacionPi n) es la aproximación de pi obtenida multiplicando los n primeros factores de Wallis. Por ejemplo,

aproximacionPi 20     ==  3.2137849402931895
aproximacionPi 200    ==  3.1493784731686008
aproximacionPi 2000   ==  3.142377365093878
aproximacionPi 20000  ==  3.141671186534396

• (errorPi x) es el menor número de factores de Wallis necesarios para obtener pi con un error menor que x. Por ejemplo,

errorPi 0.1     ==  14
errorPi 0.01    ==  155
errorPi 0.001   ==  1569
errorPi 0.0001  ==  15707

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…

La conjetura de Goldbach afirma que

Todo número entero mayor que 5 se puede escribir como suma de tres números primos.

En este ejercicio consideraremos la variación consistente en exigir que los tres sumandos sean distintos.

Definir las funciones

sumas3PrimosDistintos      :: Int -> [(Int,Int,Int)]
conKsumas3PrimosDistintos  :: Int -> Int -> [Int]
noSonSumas3PrimosDistintos :: Int -> [Int]

tales que

• (sumas3PrimosDistintos n) es la lista de las descomposiciones decrecientes de n como tres primos distintos. Por ejemplo,

sumas3PrimosDistintos 26  ==  [(13,11,2),(17,7,2),(19,5,2)]
sumas3PrimosDistintos 18  ==  [(11,5,2),(13,3,2)]
sumas3PrimosDistintos 10  ==  [(5,3,2)]
sumas3PrimosDistintos 11  ==  []

• (conKsumas3PrimosDistintos k n) es la lista de los números menores o iguales que n que se pueden escribir en k forma distintas como suma de tres primos distintos. Por ejemplo,

conKsumas3PrimosDistintos 3 99  ==  [26,27,29,32,36,42,46,48,54,58,60]
conKsumas3PrimosDistintos 2 99  ==  [18,20,21,22,23,24,25,28,30,34,64,70]
conKsumas3PrimosDistintos 1 99  ==  [10,12,14,15,16,19,40]
conKsumas3PrimosDistintos 0 99  ==  [11,13,17]

• (noSonSumas3PrimosDistintos n) es la lista de los números menores o iguales que n que no se pueden escribir como suma de tres primos distintos. Por ejemplo,

noSonSumas3PrimosDistintos 99   ==  [11,13,17]
noSonSumas3PrimosDistintos 500  ==  [11,13,17]

Leer más…

Una forma de la conjetura de Golbach afirma que todo entero mayor que 1 se puede escribir como la suma de uno, dos o tres números primos.

Si se define el índice de Goldbach de n > 1 como la mínima cantidad de primos necesarios para que su suma sea n, entonces la conjetura de Goldbach afirma que todos los índices de Goldbach de los enteros mayores que 1 son menores que 4.

Definir las siguientes funciones

indiceGoldbach  :: Int -> Int
graficaGoldbach :: Int -> IO ()

tales que

• (indiceGoldbach n) es el índice de Goldbach de n. Por ejemplo,

indiceGoldbach 2                        ==  1
indiceGoldbach 4                        ==  2
indiceGoldbach 27                       ==  3
sum (map indiceGoldbach [2..5000])      ==  10619
maximum (map indiceGoldbach [2..5000])  ==  3

• (graficaGoldbach n) dibuja la gráfica de los índices de Goldbach de los números entre 2 y n. Por ejemplo, (graficaGoldbach 150) dibuja

Comprobar con QuickCheck la conjetura de Goldbach anterior.

Leer más…

Hyman Levy observó que

7 = 3 + 2 x 2
9 = 3 + 2 x 3 =  5 + 2 x 2
11 = 5 + 2 x 3 =  7 + 2 x 2
13 = 3 + 2 x 5 =  7 + 2 x 3
15 = 3 + 2 x 5 = 11 + 2 x 2
17 = 3 + 2 x 7 =  7 + 2 x 5 = 11 + 2 x 3 = 13 + 2 x 2
19 = 5 + 2 x 7 = 13 + 2 x 3

y conjeturó que todos los número impares mayores o iguales que 7 se pueden escribir como la suma de un primo y el doble de un primo. El objetivo de los siguientes ejercicios es comprobar la conjetura de Levy.

Definir las siguientes funciones

descomposicionesLevy :: Integer -> [(Integer,Integer)]
graficaLevy          :: Integer -> IO ()

tales que

• (descomposicionesLevy x) es la lista de pares de primos (p,q) tales que x = p + 2q. Por ejemplo,

descomposicionesLevy  7  ==  [(3,2)]
descomposicionesLevy  9  ==  [(3,3),(5,2)]
descomposicionesLevy 17  ==  [(3,7),(7,5),(11,3),(13,2)]

• (graficaLevy n) dibuja los puntos (x,y) tales que x pertenece a [7,9..7+2x(n-1)] e y es el número de descomposiciones de Levy de x. Por ejemplo, (graficaLevy 200) dibuja

Comprobar con QuickCheck la conjetura de Levy.

Leer más…

Partiendo de los 5 primeros números primos y calculando el valor absoluto de la diferencia de cada dos números consecutivos hasta quedarse con un único número se obtiene la siguiente tabla:

2, 3, 5, 7, 11
1, 2, 2, 4
1, 0, 2
1, 2
1

Se observa que todas las filas, salvo la inicial, comienzan con el número 1.

Repitiendo el proceso pero empezando con los 8 primeros números primos se obtiene la siguiente tabla:

2, 3, 5, 7, 11, 13, 17, 19
1, 2, 2, 4,  2,  4,  2
1, 0, 2, 2,  2,  2
1, 2, 0, 0,  0
1, 2, 0, 0
1, 2, 0
1, 2
1

Se observa que, de nuevo, todas las filas, salvo la inicial, comienza con el número 1.

La conjetura de Gilbreath afirma que si escribimos la sucesión de números primos completa y después construimos las correspondientes sucesiones formadas por el valor absoluto de la resta de cada pareja de números consecutivos, entonces todas esas filas que obtenemos comienzan siempre por 1.

El objetivo de este ejercicio es comprobar experimentalmente dicha conjetura.

Para la representación, usaremos la simétrica de la que hemos comentado anteriormente; es decir,

2
3, 1
5, 2, 1
7, 2, 0, 1
11, 4, 2, 2, 1
13, 2, 2, 0, 2, 1
17, 4, 2, 0, 0, 2, 1
19, 2, 2, 0, 0, 0, 2, 1

en la que la primera columna son los números primos y el elemento de la fila i y columna j (con i, j > 1) es el valor absoluto de la diferencia de los elementos (i,j-1) e (i-1,j-1).

Definir las siguientes funciones

siguiente           :: Integer -> [Integer] -> [Integer]
triangulo           :: [[Integer]]
conjetura_Gilbreath :: Int -> Bool

tales que

• (siguiente x ys) es la línea siguiente de la ys que empieza por x en la tabla de Gilbreath; es decir, si ys es [y1,y2,...,yn], entonces (siguiente x ys) es [x,|y1-x|,|y2-|y1-x||,...]. Por ejemplo,

siguiente  7 [5,2,1]               ==  [7,2,0,1]
siguiente 29 [23,4,2,0,0,0,0,2,1]  ==  [29,6,2,0,0,0,0,0,2,1]

• triangulo es el triángulo de Gilbreath. Por ejemplo,

λ> take 10 triangulo
[[ 2],
[ 3,1],
[ 5,2,1],
[ 7,2,0,1],
[11,4,2,2,1],
[13,2,2,0,2,1],
[17,4,2,0,0,2,1],
[19,2,2,0,0,0,2,1],
[23,4,2,0,0,0,0,2,1],
[29,6,2,0,0,0,0,0,2,1]]

• (conjeturaGilbreath n) se verifica si se cumple la conjetura de Gilbreath para los n primeros números primos; es decir, en el triángulo de Gilbreath cuya primera columna son los n primeros números primos, todas las filas a partir de la segunda terminan en 1. Por ejemplo,

λ> conjeturaGilbreath 1000
True

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…

Leer más…

Los intervalos se pueden representar por pares de enteros (a,b) con a < b. Los elementos del intervalo (2,5) son 2, 3, 4 y 5; por tanto, su longitud es 4. Para calcular la suma de los longitudes de una lista de intervalos hay que tener en cuenta de quw si hay intervalos superpuestos sus elementos deben de contarse sólo una vez. Por ejemplo, la suma de los intervalos de [(1,4),(7,10),(3,5)] es 7 ya que, como los intervalos (1,4) y (3,5) se solapan, los podemos ver como el intervalo (1,5) que tiene una longitud de 4.

Definir la función

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

tal que (sumaIntervalos xs) es la suma de las longitudes de los intervalos de xs contando los superpuestos sólo una vez. Por ejemplo,

sumaIntervalos [(1, 5)]                  == 4
sumaIntervalos [(1, 5), (6, 10)]         == 8
sumaIntervalos [(1, 5), (5, 10)]         == 9
sumaIntervalos [(1, 5), (1, 5)]          == 4
sumaIntervalos [(1, 4), (7, 10), (3, 5)] == 7

Leer más…

En este ejercicio, se representa un mapa mediante una lista de listas de la misma longitud donde todos sus elementos son 0 menos uno (que es un 1) que es donde se encuentra la mina. Por ejemplo, en el mapa

0 0 0 0
0 0 0 0
0 1 0 0

la posición de la mina es (2,1).

Definir la función

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

tal que (posicionMina m) es la posición de la mina en el mapa m, Por ejemplo,

posicionMina [[0,0,0,0],[0,0,0,0],[0,1,0,0]]  ==  (2,1)

Leer más…

Un número primo distinto de 2 tiene la forma 4k + 1 o 4k + 3. Chebyshev notó en 1853 que la mayoría de las veces hay más números primos de la forma 4k + 3 que números primos de la forma 4k + 1 menores que un número dado. Esto se llama el sesgo de Chebyshev.

Definir las funciones

distribucionPrimosModulo4 :: [(Integer, Integer, Integer)]
empatesRestosModulo4 :: [Integer]
mayoria1RestosModulo4 :: [Integer]
grafica_Chebyshev :: Int -> IO ()

tales que

• distribucionPrimosModulo4 es la lista de las ternas (p,a,b) tales que p es un números primo, a es la cantidad de primos menores o iguales que p congruentes con 1 módulo 4 y b es la cantidad de primos menores o iguales que p congruentes con 3 módulo 4. Por ejemplo,

λ> take 7 distribucionPrimosModulo4
[(2,0,0),(3,0,1),(5,1,1),(7,1,2),(11,1,3),(13,2,3),(17,3,3)]
λ> distribucionPrimosModulo4 !! (5*10^5)
(7368791,249888,250112)

• empatesRestosModulo4 es la lista de los primos p tales que la cantidad de primos menores o iguales que p congruentes con 1 módulo 4 es igual a la cantidad de primos menores o iguales que p congruentes con 3 módulo 4. Por ejemplo,

λ> take 10 empatesRestosModulo4
[2,5,17,41,461,26833,26849,26863,26881,26893]
λ> length (takeWhile (<= 10^6) empatesRestosModulo4)
112

• mayoria1RestosModulo4 es la lista de los primos p tales que la cantidad de primos menores o iguales que p congruentes con 1 módulo 4 es mayor que la cantidad de primos menores o iguales que p congruentes con 3 módulo 4. Por ejemplo,

λ> take 10 mayoria1RestosModulo4
[26861,616841,616849,616877,616897,616909,616933,616943,616951,616961]
λ> length (takeWhile (<= 10^6) mayoria1RestosModulo4)
239

• (graficaChebyshev n) dibuja la gráfica de los puntos (p,b-a) donde p es uno de los n primeros primos impares, a es la cantidad de primos menores o iguales que p congruentes con 1 módulo 4 y b es la cantidad de primos menores o iguales que p congruentes con 3 módulo 4. Por ejemplo, (graficaChebyshev 5000) dibuja la figura

Leer más…

Un número magnánimo es un número tal que las sumas obtenidas insertando un "+" entre sus dígitos en cualquier posición son números primos. Por ejemplo, 4001 es un número magnánimo porque los números 4+001=5, 40+01=41 y 400+1=401 son primos.

Definir las funciones

esMagnanimo :: Integer -> Bool
primosMagnanimos :: [Integer]

tales que

• (esMagnanimo n) se verifica si n es un número magnánimo. Por ejemplo,

esMagnanimo 4001  ==  True
esMagnanimo 2019  ==  False

• primosMagnanimos es la lista de los números primos magnánimos. Por ejemplo,

λ> take 20 primosMagnanimos
[2,3,5,7,11,23,29,41,43,47,61,67,83,89,101,227,229,281,401,443]

Leer más…

Definir la función

diagonalesInvertidas :: Matrix a -> Matrix a

tal que (diagonalesInvertidas q) es la matriz obtenida invirtiendo el orden de los elementos de la diagonal principal y de la diagonal secundaria de q. Por ejemplo,

λ> fromList 5 5 [1..]
┌                ┐
│  1  2  3  4  5 │
│  6  7  8  9 10 │
│ 11 12 13 14 15 │
│ 16 17 18 19 20 │
│ 21 22 23 24 25 │
└                ┘
λ> diagonalesInvertidas (fromList 5 5 [1..])
┌                ┐
│ 25  2  3  4 21 │
│  6 19  8 17 10 │
│ 11 12 13 14 15 │
│ 16  9 18  7 20 │
│  5 22 23 24  1 │
└                ┘
λ> fromList 3 3 ['a','b'..]
┌             ┐
│ 'a' 'b' 'c' │
│ 'd' 'e' 'f' │
│ 'g' 'h' 'i' │
└             ┘
λ> diagonalesInvertidas (fromList 3 3 ['a','b'..])
┌             ┐
│ 'i' 'b' 'g' │
│ 'd' 'e' 'f' │
│ 'c' 'h' 'a' │
└             ┘

Leer más…

El método de Newton para el cálculo de pi se basa en la relación

y en el desarrollo del arco seno

de donde se obtiene la fórmula

La primeras aproximaciones son

a(0) = 6*(1/2)                               = 3.0
a(1) = 6*(1/2+1/(2*3*2^3))                   = 3.125
a(2) = 6*(1/2+1/(2*3*2^3)+(1*3)/(2*4*5*2^5)) = 3.1390625

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: [Int] -> IO ()

tales que

• (aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Newton. Por ejemplo,

aproximacionPi 0   ==  3.0
aproximacionPi 1   ==  3.125
aproximacionPi 2   ==  3.1390625
aproximacionPi 10  ==  3.1415926468755613
aproximacionPi 21  ==  3.141592653589793
pi                 ==  3.141592653589793

• (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..30]) dibuja

Leer más…

Se dice que una palabra tiene una repetición en una frase si es igual a una, o más, de las palabras consecutivas sin distinguir mayúsculas de minúsculas.

Definir la función

nRepeticionesConsecutivas :: String ->Int

tal que (nRepeticionesConsecutivas cs) es el número de repeticiones de palabras consecutivas de la cadena cs. Por ejemplo,

nRepeticionesConsecutivas "oso rana"                    == 0
nRepeticionesConsecutivas "oso rana oso"                == 0
nRepeticionesConsecutivas "oso oSo rana"                == 1
nRepeticionesConsecutivas "oso oso oso rana"            == 1
nRepeticionesConsecutivas "coronavirus virus oso rana"  == 0
nRepeticionesConsecutivas "virus     virus oso rana"    == 1
nRepeticionesConsecutivas "virus oso virus oso rana"    == 0
nRepeticionesConsecutivas "oso oso oso oso oso oso"     == 1
nRepeticionesConsecutivas "oso oso oso oso rana rana"   == 2
nRepeticionesConsecutivas "rana rana oso oso rana rana" == 3

Leer más…

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir las funciones

mediasDigitosDePi        :: IO [Double]
graficaMediasDigitosDePi :: Int -> IO ()

tales que

• mediasDigitosDePi es la sucesión cuyo n-ésimo elemento es la media de los n primeros dígitos de pi. Por ejemplo,

λ> xs <- mediasDigitosDePi
λ> take 5 xs
[1.0,2.5,2.0,2.75,4.0]
λ> take 10 xs
[1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]
λ> take 10 <$> mediasDigitosDePi
[1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]

• (graficaMediasDigitosDePi n) dibuja la gráfica de los n primeros términos de mediasDigitosDePi. Por ejemplo,
• (graficaMediasDigitosDePi 20) dibuja
• (graficaMediasDigitosDePi 200) dibuja
• (graficaMediasDigitosDePi 2000) dibuja

Leer más…

Definir, por simulación, la función

distanciaEsperada :: Int -> IO Double

tal que (distanciaEsperada n) es la distancia esperada entre n puntos del cuadrado unitario de vértices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,

distanciaEsperada 10     ==  0.43903617921423593
distanciaEsperada 10     ==  0.6342350621260004
distanciaEsperada 100    ==  0.5180418995364429
distanciaEsperada 100    ==  0.5288261085653962
distanciaEsperada 1000   ==  0.5143804432569616
distanciaEsperada 10000  ==  0.5208360147922616

El valor exacto de la distancia esperada es

ve = (sqrt(2) + 2 + 5*log(1+sqrt(2)))/15 = 0.5214054331647207

Definir la función

graficaDistanciaEsperada :: [Int] -> IO ()

tal que (graficaDistanciaEsperadan n) dibuja las gráficas de los pares (n, distanciaEsperada n) para n en la lista creciente ns junto con la recta y = ve, donde ve es el valor exacto. Por ejemplo, (graficaDistanciaEsperada [10,30..4000]) dibuja

Leer más…

Una serie infinita para el cálculo de pi, publicada por Nilakantha en el siglo XV, es

           4       4       4       4
pi = 3 + ----- - ----- + ----- - ------ + ···
         2x3x4   4x5x6   6x7x8   8x9x10

Definir las funciones

aproximacionPi :: Int -> Double
tabla          :: FilePath -> [Int] -> IO ()

tales que

• (aproximacionPi n) es la n-ésima aproximación de pi obtenido sumando los n primeros términos de la serie de Nilakantha. Por ejemplo,

aproximacionPi 0        ==  3.0
aproximacionPi 1        ==  3.1666666666666665
aproximacionPi 2        ==  3.1333333333333333
aproximacionPi 3        ==  3.145238095238095
aproximacionPi 4        ==  3.1396825396825396
aproximacionPi 5        ==  3.1427128427128426
aproximacionPi 10       ==  3.1414067184965018
aproximacionPi 100      ==  3.1415924109719824
aproximacionPi 1000     ==  3.141592653340544
aproximacionPi 10000    ==  3.141592653589538
aproximacionPi 100000   ==  3.1415926535897865
aproximacionPi 1000000  ==  3.141592653589787
pi                      ==  3.141592653589793

• (tabla f ns) escribe en el fichero f las n-ésimas aproximaciones de pi, donde n toma los valores de la lista ns, junto con sus errores. Por ejemplo, al evaluar la expresión

tabla "AproximacionesPi.txt" [0,10..100]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|   10 | 3.141406718497 | 0.000185935093 |
|   20 | 3.141565734659 | 0.000026918931 |
|   30 | 3.141584272675 | 0.000008380915 |
|   40 | 3.141589028941 | 0.000003624649 |
|   50 | 3.141590769850 | 0.000001883740 |
|   60 | 3.141591552546 | 0.000001101044 |
|   70 | 3.141591955265 | 0.000000698325 |
|   80 | 3.141592183260 | 0.000000470330 |
|   90 | 3.141592321886 | 0.000000331704 |
|  100 | 3.141592410972 | 0.000000242618 |
+------+----------------+----------------+

al evaluar la expresión

tabla "AproximacionesPi.txt" [0,500..5000]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|  500 | 3.141592651602 | 0.000000001988 |
| 1000 | 3.141592653341 | 0.000000000249 |
| 1500 | 3.141592653516 | 0.000000000074 |
| 2000 | 3.141592653559 | 0.000000000031 |
| 2500 | 3.141592653574 | 0.000000000016 |
| 3000 | 3.141592653581 | 0.000000000009 |
| 3500 | 3.141592653584 | 0.000000000006 |
| 4000 | 3.141592653586 | 0.000000000004 |
| 4500 | 3.141592653587 | 0.000000000003 |
| 5000 | 3.141592653588 | 0.000000000002 |
+------+----------------+----------------+

Leer más…

Definir la función

division :: String -> [String]

tal que (division cs) es la lista de las palabras formadas por dos elementos consecutivos de cs y, en el caso de que la longitud de cs sea impar, el último elemento de la última palabra es el carácter de subrayado. Por ejemplo,

division "pandemia"    ==  ["pa","nd","em","ia"]
division "covid2019"   ==  ["co","vi","d2","01","9_"]
division "covid 2019"  ==  ["co","vi","d ","20","19"]

Leer más…

Definir la función

palabrasInvertidas :: String -> String

tal que (palabrasInvertidas cs) es la cadena obtenida invirtiendo las palabras de cs. Por ejemplo,

λ> palabrasInvertidas "Del principio al final"
"final al principio Del"
λ> palabrasInvertidas "una a una"
"una a una"

Leer más…

Definir la función

primeroNoConsecutivo :: (Eq a,Enum a) => [a] -> Maybe a

tal que (primeroNoConsecutivo xs) es el primer elemento de la lista xs que no es igual al siguiente de su elemento anterior en xs o Nothing si tal elemento no existe. Por ejemplo

primeroNoConsecutivo [1,2,3,4,6,7,8] == Just 6
primeroNoConsecutivo "bcdfg"         == Just 'f'
primeroNoConsecutivo "bcdef"         == Nothing

Leer más…

Los números de Fibonacci son los números F(n) de la siguiente sucesión

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

que comienza con 0 y 1 y los siguientes términos son las sumas de los dos anteriores.

Un número x es el producto de dos números de Fibonacci consecutivos si existe un n tal que

F(n) * F(n+1) = x

y su prueba es (F(n),F(n+1),True). Por ejemplo, 714 es el producto de dos números de Fibonacci consecutivos ya que

F(8) = 21, F(9) = 34 y 714 = 21 * 34.

Su prueba es (21, 34, True).

Un número x no es el producto de dos números de Fibonacci consecutivos si no existe un n tal que

F(n) * F(n+1) = x

y su prueba es (F(m),F(m+1),False) donde m es el menor número tal que

F(m) * F(m+1) > x

Por ejemplo, 800 no es el producto de dos números de Fibonacci consecutivos, ya que

F(8) = 21, F(9) = 34, F(10) = 55 y 21 * 34 < 800 < 34 * 55.

Su prueba es (34, 55, False),

Definir la función

productoFib :: Integer -> (Integer, Integer, Bool)

tal que (productoFib x) es la prueba de que es, o no es, el producto de dos números de Fibonacci consecutivos. Por ejemplo,

productoFib 714  == (21,  34, True)
productoFib 800  == (34,  55, False)
productoFib 4895 == (55,  89, True)
productoFib 5895 == (89, 144, False)

Leer más…

La ordenación pendular de una lista xs es la lista obtenida organizando sus elementos de manera similar al movimiento de ida y vuelta de un péndulo; es decir,

• El menor elemento de xs se coloca en el centro de la lista.
• El siguiente elemento se coloca a la derecha del menor.
• El siguiente elemento se coloca a la izquierda del menor y así sucesivamente, de una manera similar a la de un péndulo.

Por ejemplo, la ordenación pendular de [6,6,8,5,10] es [10,6,5,6,8].

Definir la función

pendulo :: [Int] -> [Int]

tal que (pendulo xs) es la ordenación pendular de xs. Por ejemplo,

pendulo [6,6,8,5,10]                 == [10,6,5,6,8]
pendulo [-9,-2,-10,-6]               == [-6,-10,-9,-2]
pendulo [11,-16,-18,13,-11,-12,3,18] == [13,3,-12,-18,-16,-11,11,18]

Leer más…

Un niño está jugando con una pelota en el noveno piso de un edificio alto. La altura de este piso, h, es conocida. Deja caer la pelota por la ventana. La pelota rebota una r-ésima parte de su altura (por ejemplo, dos tercios de su altura). Su madre mira por una ventana a w metros del suelo (por ejemplo, a 1.5 metros). ¿Cuántas veces verá la madre a la pelota pasar frente a su ventana incluyendo cuando está cayendo y rebotando?

Se deben cumplir tres condiciones para que el experimento sea válido:

• La altura "h" debe ser mayor que 0
• El rebote "r" debe ser mayor que 0 y menor que 1
• La altura de la ventana debe ser mayor que 0 y menor que h.

Definir la función

numeroAvistamientos :: Double -> Double -> Double -> Integer

tal que (numeroAvistamientos h r v) es el número de avistamientos de la pelota si se cumplen las tres condiciones anteriores y es -1 en caso contrario. Por ejemplo,

numeroAvistamientos 3    0.66 1.5  ==  3
numeroAvistamientos 30   0.66 1.5  ==  15
numeroAvistamientos (-3) 0.66 1.5  ==  -1
numeroAvistamientos 3    (-1) 1.5  ==  -1
numeroAvistamientos 3    2    1.5  ==  -1
numeroAvistamientos 3    0.5  (-1) ==  -1
numeroAvistamientos 3    0.5  4    ==  -1

Leer más…

Definir la función

mayorEquidigital :: Integer -> Integer

tal que (mayorEquidigital n) es el mayor número que se puede formar con los dígitos de n. Por ejemplo,

mayorEquidigital 325271  ==  753221

Leer más…

¡El mundo está en cuarentena! Hay una nueva pandemia que lucha contra la humanidad. Cada continente está aislado de los demás, pero las personas infectadas se han propagado antes de la advertencia.

En este problema se representará el mundo por una cadena como la siguiente

"01000000X000X011X0X"

donde 0 representa no infectado, 1 representa infectado y X representa un océano

Las reglas de propagación son:

• El virus no puede propagarse al otro lado de un océano.
• Si una persona se infecta, todas las personas de este continente se infectan también.
• El primer y el último continente no están conectados.

El problema consiste en encontrar el porcentaje de la población humana que se infectó al final. Por ejemplo,

inicio:     "01000000X000X011X0X"
final:      "11111111X000X111X0X"
total:      15
infectados: 11
porcentaje: 100*11/15 = 73.33333333333333

Definir la función

porcentajeInfectados :: String -> Double

tal que (porcentajeInfectados xs) es el porcentaje final de infectados para el mapa inicial xs. Por ejemplo,

porcentajeInfectados "01000000X000X011X0X"  == 73.33333333333333
porcentajeInfectados "01X000X010X011XX"     == 72.72727272727273
porcentajeInfectados "XXXXX"                == 0.0
porcentajeInfectados "0000000010"           == 100.0
porcentajeInfectados "X00X000000X10X0100"   == 42.857142857142854

Leer más…

Si \(A\) es una matriz \(m \times n\) y \(B\) es una matriz \(p \times q\), entonces el producto de Kronecker \(A \otimes B\) es la matriz bloque \(mp \times nq\)

Más explícitamente, tenemos

Por ejemplo,

Definir la función

kronecker :: Num t => Matrix t -> Matrix t -> Matrix t

tal que (kronecker a b) es el producto de Kronecker de las matrices a y b. Por ejemplo,

λ> kronecker (fromLists [[1,2],[3,1]]) (fromLists [[0,3],[2,1]])
┌         ┐
│ 0 3 0 6 │
│ 2 1 4 2 │
│ 0 9 0 3 │
│ 6 3 2 1 │
└         ┘
λ> kronecker (fromLists [[1,2],[3,4]]) (fromLists [[2,1],[-1,0],[3,2]])
┌             ┐
│  2  1  4  2 │
│ -1  0 -2  0 │
│  3  2  6  4 │
│  6  3  8  4 │
│ -3  0 -4  0 │
│  9  6 12  8 │
└             ┘
λ> kronecker (fromLists [[2,1],[-1,0],[3,2]]) (fromLists [[1,2],[3,4]])
┌             ┐
│  2  4  1  2 │
│  6  8  3  4 │
│ -1 -2  0  0 │
│ -3 -4  0  0 │
│  3  6  2  4 │
│  9 12  6  8 │
└             ┘

Leer más…

Nota: En este ejercicio se usa la misma notación que en los anteriores importando los módulos

• Evaluacion_de_FNC
• Modelos_de_FNC
• Problema_SAT_para_FNC
• Cliques
• KCliques
• Grafo_FNC

Definir las funciones

cliquesFNC :: FNC -> [[(Int,Literal)]]
cliquesCompletos :: FNC -> [[(Int,Literal)]]
esSatisfaciblePorClique :: FNC -> Bool