Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

 6/2  = 3                  se representa por (3,[],[])
 1/2  = 0.5                se representa por (0,[5],[])
 1/3  = 0.333333...        se representa por (0,[],[3])
23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

type Decimal = (Integer,[Integer],[Integer])

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

type Racional = (Integer,Integer)

Definir las funciones

decimal  :: Racional -> Decimal
racional :: Decimal -> Racional

tales que

• (decimal r) es la representación decimal del número racional r. Por ejemplo,

decimal (1,4)    ==  (0,[2,5],[])
decimal (1,3)    ==  (0,[],[3])
decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])

• (racional d) es el número racional cuya representación decimal es d. Por ejemplo,

racional (0,[2,5],[])           ==  (1,4)
racional (0,[],[3])             ==  (1,3)
racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

λ> let (_,_,p) = decimal (23,14) in concatMap show p
"428571"
λ> let (_,_,p) = decimal (1,47) in concatMap show p
"0212765957446808510638297872340425531914893617"
λ> let (_,_,p) = decimal (1,541) in length (concatMap show p)
540

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

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…

Un número n es especial si al unir los dígitos de sus factores primos, se obtienen exactamente los dígitos de n, aunque puede ser en otro orden. Por ejemplo, 1255 es especial, pues los factores primos de 1255 son 5 y 251.

Definir la función

esEspecial :: Integer -> Bool

tal que (esEspecial n) se verifica si un número n es especial. Por ejemplo,

esEspecial 1255 == True
esEspecial 125  == False

Comprobar con QuickCheck que todo número primo es especial.

Calcular los 5 primeros números especiales que no son primos.

Leer más…

Las expresiones aritméticas se pueden definir mediante el siguiente tipo de dato

data Expr  = N Int | V Char | Sum Expr Expr | Mul Expr Expr
             deriving Show

Por ejemplo, (x+3)+(7*y) se representa por

ejExpr :: Expr
ejExpr = Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))

Definir la función

valor :: Expr -> Maybe Int

tal que (valor e) es 'Just v' si la expresión e es numérica y v es su valor, o bien 'Nothing' si e no es numérica. Por ejemplo:

valor (Sum (N 7) (N 9))                            == Just 16
valor (Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))) == Nothing
valor (Sum (Sum (N 1) (N 3))(Mul (N 7) (N 2)))     == Just 18

Leer más…

Los vectores se definen usando tablas como sigue:

type Vector a = Array Int a

Un elemento de un vector es un máximo local si no tiene ningún elemento adyacente mayor o igual que él.

Definir la función

posMaxVec :: Ord a => Vector a -> [Int]

tal que (posMaxVec p) devuelve las posiciones del vector p en las que p tiene un máximo local. Por ejemplo,

posMaxVec (listArray (1,6) [3,2,6,7,5,3]) == [1,4]
posMaxVec (listArray (1,2) [5,5])         == []
posMaxVec (listArray (1,1) [5])           == [1]

Leer más…

El pasado 11 de marzo se ha publicado el artículo Unexpected biases in the distribution of consecutive primes en el que muestra que los números primos repelen a otros primos que terminan en el mismo dígito.

La lista de los últimos dígitos de los 30 primeros números es

[2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1,3,9,3,9,7,1,3,7,9,3]

Se observa que hay 6 números que su último dígito es un 1 y de sus consecutivos 4 terminan en 3 y 2 terminan en 7.

Definir la función

distribucionUltimos :: Int -> M.Matrix Integer

tal que (distribucionUltimos n) es la matriz cuyo elemento (i,j) indica cuántos de los n primeros números primos terminan en i y su siguiente número primo termina en j. Por ejemplo,

λ> distribucionUltimos 30
( 0 0 4 0 0 0 2 0 0 )
( 0 0 1 0 0 0 0 0 0 )
( 0 0 0 0 1 0 4 0 4 )
( 0 0 0 0 0 0 0 0 0 )
( 0 0 0 0 0 0 1 0 0 )
( 0 0 0 0 0 0 0 0 0 )
( 4 0 1 0 0 0 0 0 2 )
( 0 0 0 0 0 0 0 0 0 )
( 2 0 3 0 0 0 1 0 0 )

λ> distribucionUltimos (10^5)
( 4104    0 7961    0    0    0 8297    0 4605 )
(    0    0    1    0    0    0    0    0    0 )
( 5596    0 3604    0    1    0 7419    0 8387 )
(    0    0    0    0    0    0    0    0    0 )
(    0    0    0    0    0    0    1    0    0 )
(    0    0    0    0    0    0    0    0    0 )
( 6438    0 6928    0    0    0 3627    0 8022 )
(    0    0    0    0    0    0    0    0    0 )
( 8830    0 6513    0    0    0 5671    0 3995 )

Nota: Se observa cómo se "repelen" ya que en las filas del 1, 3, 7 y 9 el menor elemento es el de la diagonal.

Leer más…

Definir la función

sumaMaxima :: [Integer] -> Integer

tal que (sumaMaxima xs) es el valor máximo de la suma de elementos consecutivos de la lista xs. Por ejemplo,

sumaMaxima []             ==  0
sumaMaxima [2,-2,3,-3,4]  ==  4
sumaMaxima [-1,-2,-3]     ==  0
sumaMaxima [2,-1,3,-2,3]  ==  5
sumaMaxima [1,-1,3,-2,4]  ==  5
sumaMaxima [2,-1,3,-2,4]  ==  6
sumaMaxima [1..10^6]      ==  500000500000

Comprobar con QuickCheck que

sumaMaxima xs == sumaMaxima (reverse xs)

Leer más…

En la siguiente figura, al rotar girando 90 grados en el sentido del reloj la matriz de la izquierda, obtenemos la de la derecha

1 2 3        7 4 1
4 5 6        8 5 2
7 8 9        9 6 3

Definir la función

rota :: Matrix Int -> Matrix Int

tal que (rota p) es la matriz obtenida girando en el sentido del reloj la matriz cuadrada p. Por ejemplo,

λ> rota (fromList 3 3 [1..9])
( 7 4 1 )
( 8 5 2 )
( 9 6 3 )

λ> rota (fromList 3 3 [7,4,1,8,5,2,9,6,3])
( 9 8 7 )
( 6 5 4 )
( 3 2 1 )

Leer más…

Definir la función

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

tal que (seccion xs) es el mayor sección inicial de xs que no contiene ningún elemento repetido. Por ejemplo:

seccion [1,2,3,2,4,5]                      == [1,2,3]
seccion "caceres"                          == "ca"
length (seccion ([1..7531] ++ [1..10^9]))  ==  7531

Leer más…

Definir la sucesión

primosSumaDe2Cuadrados :: [Integer]

cuyos elementos son los números primos que se pueden escribir como sumas de dos cuadrados. Por ejemplo,

λ> take 20 primosSumaDe2Cuadrados
[2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181]
λ> primosSumaDe2Cuadrados !! (2*10^5)
5803241

En el ejemplo anterior,

• 13 está en la sucesión porque es primo y 13 = 2²+3².
• 11 no está en la sucesión porque no se puede escribir como suma de dos cuadrados (en efecto, 11-1=10, 11-2²=7 y 11-3²=2 no son cuadrados).
• 20 no está en la sucesión porque, aunque es suma de dos cuadrados (20=4²+2²), no es primo.

Leer más…

Las matrices puede representarse mediante tablas cuyos índices son pares de números naturales:

type Matriz = Array (Int,Int) Int

Definir la función

maximaSuma :: Matriz -> Int

tal que (maximaSuma p) es el máximo de las sumas de las listas de elementos de la matriz p tales que cada elemento pertenece sólo a una fila y a una columna. Por ejemplo,

λ> maximaSuma (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])
17

ya que las selecciones, y sus sumas, de la matriz

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

son

[1,4,7] --> 12
[1,9,6] --> 16
[2,8,7] --> 17
[2,9,5] --> 16
[3,8,6] --> 17
[3,4,5] --> 12

Hay dos selecciones con máxima suma: [2,8,7] y [3,8,6].

Leer más…

Definir la función

nDivisoresPar :: Integer -> Bool

tal que (nDivisoresPar n) se verifica si n tiene un número par de divisores. Por ejemplo,

nDivisoresPar 12                     ==  True
nDivisoresPar 16                     ==  False
nDivisoresPar (product [1..2*10^4])  ==  True

Leer más…

Las sublistas comunes de "1325" y "36572" son "", "3","32", "35", "2" y "5". El máximo de sus longitudes es 2.

Definir la función

maximo :: Eq a => [a] -> [a] -> Int

tal que (maximo xs ys) es el máximo de las longitudes de las sublistas comunes de xs e ys. Por ejemplo,

maximo "1325" "36572"       == 2
maximo [1,4..33] [2,4..33]  == 5
maximo [1..10^6] [1..10^6]  == 100000

Leer más…

Sea xs una lista y n su longitud. Se dice que xs es casi completa si sus elementos son los números enteros entre 0 y n excepto uno. Por ejemplo, la lista [3,0,1] es casi completa.

Definir la función

ausente :: [Integer] -> Integer

tal que (ausente xs) es el único entero (entre 0 y la longitud de xs) que no pertenece a la lista casi completa xs. Por ejemplo,

ausente [3,0,1]               ==  2
ausente [1,2,0]               ==  3
ausente (1+10^7:[0..10^7-1])  ==  10000000

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…

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…

La sucesión A114258 de la OEIS está formada por los números n tales que el número de ocurrencia de cada dígito d de n en n² es el doble del número de ocurrencia de d en n. Por ejemplo, 72576 es un elemento de A114258 porque tiene un 2, un 5, un 6 y dos 7 y su cuadrado es 5267275776 que tiene exactamente dos 2, dos 5, dos 6 y cuatro 7.

Un número es especial si pertenece a la sucesión A114258.

Definir la sucesión

especiales :: [Integer]

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

take 5 especiales  ==  [72576,406512,415278,494462,603297]

Leer más…

Los primeros términos de la sucesión de Fibonacci son

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

Se observa que el 6º término de la sucesión (comenzando a contar en 0) es el número 8.

Definir la función

indiceFib :: Integer -> Maybe Integer

tal que (indiceFib x) es justo el número n si x es el n-ésimo términos de la sucesión de Fibonacci o Nothing en el caso de que x no pertenezca a la sucesión. Por ejemplo,

indiceFib 8                                           == Just 6
indiceFib 9                                           == Nothing
indiceFib 21                                          == Just 8
indiceFib 22                                          == Nothing
indiceFib 280571172992510140037611932413038677189525  == Just 200
indiceFib 123456789012345678901234567890123456789012  == Nothing

Leer más…

La integral definida de una función \( f \) entre los límites \( a \) y \( b \) puede calcularse mediante la regla del rectángulo usando la fórmula \[ h \cdot \left( f\left(a + \frac{h}{2}\right) + f\left(a + h + \frac{h}{2}\right) + f\left(a + 2h + \frac{h}{2}\right) + \cdots + f\left(a + nh + \frac{h}{2}\right) \right) \] con \[ a+nh+\frac{h}{2} \leq b < a+(n+1)h+\frac{h}{2} \] y usando valores pequeños para \( h \).

Definir la función

integral :: (Fractional a, Ord a) => a -> a -> (a -> a) -> a -> a

tal que (integral a b f h) es el valor de dicha expresión. Por ejemplo, el cálculo de la integral de f(x) = x^3 entre 0 y 1, con paso 0.01, es

integral 0 1 (^3) 0.01  ==  0.24998750000000042

Otros ejemplos son

integral 0 1 (^4) 0.01                        ==  0.19998333362500048
integral 0 1 (\x -> 3*x^2 + 4*x^3) 0.01       ==  1.9999250000000026
log 2 - integral 1 2 (\x -> 1/x) 0.01         ==  3.124931644782336e-6
pi - 4 * integral 0 1 (\x -> 1/(x^2+1)) 0.01  ==  -8.333333331389525e-6

Leer más…

El método de bisección para calcular un cero de una función en el intervalo [a,b] se basa en el teorema de Bolzano:

Si f(x) es una función continua en el intervalo [a, b], y si, además, en los extremos del intervalo la función f(x) toma valores de signo opuesto (f(a) * f(b) < 0), entonces existe al menos un valor c en (a, b) para el que f(c) = 0".

El método para calcular un cero de la función f en el intervalo [a,b] con un error menor que e consiste en tomar el punto medio del intervalo c = (a+b)/2 y considerar los siguientes casos:

• Si |f(c)| < e, hemos encontrado una aproximación del punto que anula f en el intervalo con un error aceptable.
• Si f(c) tiene signo distinto de f(a), repetir el proceso en el intervalo [a,c].
• Si no, repetir el proceso en el intervalo [c,b].

Definir la función

biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double

tal que (biseccion f a b e) es una aproximación del punto del intervalo [a,b] en el que se anula la función f, con un error menor que e, calculada mediante el método de la bisección. Por ejemplo,

biseccion (\x -> x^2 - 3) 0 5 0.01             ==  1.7333984375
biseccion (\x -> x^3 - x - 2) 0 4 0.01         ==  1.521484375
biseccion cos 0 2 0.01                         ==  1.5625
biseccion (\x -> log (50-x) - 4) (-10) 3 0.01  ==  -5.125

Leer más…

Definir las funciones

particionesCuadradas :: Integer -> [[Integer]]
nParticionesCuadradas :: Integer -> Integer
graficaParticionesCuadradas :: Integer -> IO ()

tales que

• (particionesCuadradas n) es la listas de conjuntos de cuadrados cuya suma es n. Por ejemplo,

particionesCuadradas 3  ==  [[1,1,1]]
particionesCuadradas 4  ==  [[4],[1,1,1,1]]
particionesCuadradas 9  ==  [[9],[4,4,1],[4,1,1,1,1,1],[1,1,1,1,1,1,1,1,1]]

• (nParticionesCuadradas n) es el número de conjuntos de cuadrados cuya suma es n. Por ejemplo,

nParticionesCuadradas 3    ==  1
nParticionesCuadradas 4    ==  2
nParticionesCuadradas 9    ==  4
nParticionesCuadradas 50   ==  104
nParticionesCuadradas 100  ==  1116
nParticionesCuadradas 200  ==  27482

• (graficaParticionesCuadradas n) dibuja la gráfica de la sucesión

[nParticionesCuadradas k | k <- [0..n]]

Por ejemplo, con (graficaParticionesCuadradas 100) se obtiene

Leer más…

Un número n es automórfico si los últimos dígitos de su cuadrado son los dígitos de n. Por ejemplo, 5, 6, 76 y 890625 son números automórficos ya que 5² = 25, 6² = 36, 76² = 5776 y 890625² = 793212890625.

Definir la sucesión

automorficos :: [Integer]

tal que sus elementos son los números automórficos. Por ejemplo,

λ> take 11 automorficos
[1,5,6,25,76,376,625,9376,90625,109376,890625]
λ> automorficos !! 30
56259918212890625

Leer más…

Los primeros números de la forma p²+q³+r⁴, con p, q y r primos son

28 = 2² + 2³ + 2⁴
33 = 3² + 2³ + 2⁴
47 = 2² + 3³ + 2⁴
49 = 5² + 2³ + 2⁴

Definir la sucesión

sumas3potencias :: [Integer]

cuyos elementos son los números que se pueden escribir de la forma p²+q³+r⁴, con p, q y r primos. Por ejemplo,

λ> take 15 sumas3potencias
[28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]
λ> sumas3potencias !! 234567
8953761

Leer más…

Se observa que todos los primeros números naturales tienen al menos un múltiplo no nulo que está formado solamente por ceros y unos. Por ejemplo, 1x10=10, 2x5=10, 3x37=111, 4x25=100, 5x2=10, 6x185=1110; 7x143=1001; 8X125=1000; 9x12345679=111111111.

Definir la función

multiplosCon1y0 :: Integer -> [Integer]

tal que (multiplosCon1y0 n) es la lista de los múltiplos de n cuyos dígitos son 1 ó 0. Por ejemplo,

take 4 (multiplosCon1y0 3)      ==  [111,1011,1101,1110]
take 3 (multiplosCon1y0 23)     ==  [110101,1011011,1101010]
head (multiplosCon1y0 1234658)  ==  110101101101000000110

Comprobar con QuickCheck que todo entero positivo tiene algún múltiplo cuyos dígitos son 1 ó 0.

Leer más…

Dadas dos listas de valores

xs = [x(1), x(2), ..., x(n)]
ys = [y(1), y(2), ..., y(n)]

la ecuación de la recta de regresión de ys sobre xs es y = a+bx, donde \[ b = \frac{n \sum x_i y_i - \sum x_i \sum y_i}{n \sum x_i^2 - \left( \sum x_i \right)^2} \]

\[ a = \frac{\sum y_i - b \sum x_i}{n} \]

Definir la función

regresionLineal :: [Double] -> [Double] -> (Double,Double)

tal que (regresionLineal xs ys) es el par (a,b) de los coeficientes de la recta de regresión de ys sobre xs. Por ejemplo, para los valores

ejX, ejY :: [Double]
ejX = [5,  7, 10, 12, 16, 20, 23, 27, 19, 14]
ejY = [9, 11, 15, 16, 20, 24, 27, 29, 22, 20]

se tiene

λ> regresionLineal ejX ejY
(5.195045748716805,0.9218924347243919)

Definir el procedimiento

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

tal que (grafica xs ys) pinte los puntos correspondientes a las listas de valores xs e ys y su recta de regresión. Por ejemplo, con (grafica ejX ejY) se obtiene el siguiente dibujo

Leer más…

El enunciado del problema 652 de Números y algo más es el siguiente

Si factorizamos los factoriales de un número en función de sus divisores primos y sus potencias, ¿Cuál es el menor número n tal que entre los factores primos y los exponentes de estos, n! contiene los dígitos del cero al nueve? Por ejemplo

• 6! = 2⁴x3²x5¹, le faltan los dígitos 0,6,7,8 y 9
• 12! = 2¹⁰x3⁵x5²x7¹x11¹, le faltan los dígitos 4,6,8 y 9

Definir la función

digitosDeFactorizacion :: Integer -> [Integer]

tal que (digitosDeFactorizacion n) es el conjunto de los dígitos que aparecen en la factorización de n. Por ejemplo,

digitosDeFactorizacion (factorial 6)   ==  [1,2,3,4,5]
digitosDeFactorizacion (factorial 12)  ==  [0,1,2,3,5,7]

Usando la función anterior, calcular la solución del problema.

Comprobar con QuickCheck que si n es mayor que 100, entonces

digitosDeFactorizacion (factorial n) == [0..9]

Leer más…

Los números de Pentanacci se definen mediante las ecuaciones

P(0) = 0
P(1) = 1
P(2) = 1
P(3) = 2
P(4) = 4
P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4

Los primeros números de Pentanacci son

0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

Se observa que

• hasta P(5) hay 1 impar: el 1 (aunque aparece dos veces);
• hasta P(7) hay 2 impares distintos: 1 y 31;
• hasta P(10) hay 3 impares distintos: 1, 31 y 61;
• hasta P(15) hay 5 impares distintos: 1, 31 y 61, 1793 y 3525.

Definir la función

nPentanacciImpares :: Integer -> Integer

tal que (nPentanacciImpares n) es la cantidad de números impares distintos desde P(0) hasta P(n). Por ejemplo,

nPentanacciImpares 5                             ==  1
nPentanacciImpares 7                             ==  2
nPentanacciImpares 10                            ==  3
nPentanacciImpares 15                            ==  5
nPentanacciImpares 100                           ==  33
nPentanacciImpares 1000                          ==  333
nPentanacciImpares 10000                         ==  3333
nPentanacciImpares (10^(10^6)) `mod` (10^9)      ==  333333333
length (show (nPentanacciImpares2 (10^(10^6))))  ==  1000000

Leer más…

Los números de Fibonacci se definen mediante las ecuaciones

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2), si n > 1

Los primeros números de Fibonacci son

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

Una generalización de los anteriores son los números de Pentanacci definidos por las siguientes ecuaciones

P(0) = 0
P(1) = 1
P(2) = 1
P(3) = 2
P(4) = 4
P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4

Los primeros números de Pentanacci son

0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

Definir la sucesión

pentanacci :: [Integer]

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

λ> take 15 pentanacci
[0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525]
λ> (pentanacci !! 70000) `mod` (10^30)
231437922897686901289110700696
λ> length (show (pentanacci !! 70000))
20550

Leer más…

Las matrices se pueden representar como lista de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.

Definir la función

diagonal       :: [[a]] -> [a]

tal que (diagonal xss) es la diagonal de la matriz xss. Por ejemplo,

diagonal [[3,5,2],[4,7,1],[6,9,0]]           ==  [3,7,0]
diagonal [[3,5],[4,7],[6,9]]                 ==  [3,7]
diagonal [[3,5,2],[4,7,1]]                   ==  [3,7]
sum (diagonal (replicate 20000 [1..20000]))  ==  200010000

Leer más…

Definir la función

sumas :: Int -> [Int] -> [Int]

tal que (sumas n xs) es la lista de los números que se pueden obtener como suma de n, o menos, elementos de xs. Por ejemplo,

sumas 0 [2,5]              ==  [0]
sumas 1 [2,5]              ==  [0,2,5]
sumas 2 [2,5]              ==  [0,2,4,5,7,10]
sumas 3 [2,5]              ==  [0,2,4,5,6,7,9,10,12,15]
sumas 2 [2,3,5]            ==  [0,2,3,4,5,6,7,8,10]
sumas 3 [2,3,5]            ==  [0,2,3,4,5,6,7,8,9,10,11,12,13,15]
length (sumas 8 [1..200])  ==  1601

Leer más…

Los árboles binarios con datos en los nodos y hojas se definen por

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

Por ejemplo, el árbol

       3
      / \
     /   \
    4     7
   / \   / \
  5   0 0   3
 / \
2   0

se representa por

ejArbol :: Arbol Integer
ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

Anotando cada elemento del árbol anterior con su profundidad, se obtiene el árbol siguiente

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

Definir la función

anotado :: Arbol a -> Arbol (a,Int)

tal que (anotado x) es el árbol obtenido anotando los elementos de x con su profundidad. Por ejemplo,

λ> anotado ejArbol
N (3,0)
  (N (4,1)
     (N (5,2) (H (2,3)) (H (0,3)))
     (H (0,2)))
  (N (7,1) (H (0,2)) (H (3,2)))

Leer más…

Definir la función

compactada :: [Maybe Int] -> [Int]

tal que (compacta xs) es la lista obtenida al compactar xs con las siguientes reglas:

1. se eliminan los elementos Nothing;
2. si dos elementos consecutivos tienen el mismo valor, se sustituyen por el sucesor de su valor y
3. los restantes elementos no se cambian.

Por ejemplo,

λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6]
[2,5,3,6]
λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6]
[2,1,4,3,6]
λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6]
[2,1,5,6]
λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4]
[2,1,4,3,4]
λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4]
[2,2,4,3,4]

Leer más…

Definir la función

sinEspaciosExtremos :: String -> String

tal que (sinEspaciosExtremos cs) es la cadena obtenida eliminando los espacios blancos de los extremos de la cadena cs. Por ejemplo,

λ> sinEspaciosExtremos "   El lunes a las 12:30.     "
"El lunes a las 12:30."

Leer más…

Sea \( n \) un número natural cuya factorización prima es \[ n = 2^a \cdot p_1^{b_1} \cdots p_n^{b_n} \cdot q_1^{c_1} \cdots q_m^{c_m} \] donde los \( p_i \) son los divisores primos de \( n \) congruentes con \( 3 \) módulo \( 4 \) y los \( q_j \) son los divisores primos de \( n \) congruentes con \( 1 \) módulo \( 4 \). Entonces, el número de formas de descomponer \( n \) como suma de dos cuadrados es \( 0 \), si algún \( b_i \) es impar y es el techo (es decir, el número entero más próximo por exceso) de \[ \frac{(1+c_1) \cdots (1+c_m)}{2} \] en caso contrario. Por ejemplo, el número \( 2^3 \cdot (3^9 \cdot 7^8) \cdot (5^3 \cdot 13^6) \) no se puede descomponer como sumas de dos cuadrados (porque el exponente de \( 3 \) es impar) y el número \( 2^3 \cdot (3^2 \cdot 7^8) \cdot (5^3 \cdot 13^6) \) tiene \( 14 \) descomposiciones como suma de dos cuadrados (porque los exponentes de \( 3 \) y \( 7 \) son pares y el techo de \( \frac{(1+3)(1+6)}{2} \) es \( 14 \)).

Definir la función

   nRepresentaciones :: Integer -> Integer

tal que (nRepresentaciones n) es el número de formas de representar n como suma de dos cuadrados. Por ejemplo,

   nRepresentaciones (2^3*3^9*5^3*7^8*13^6)        ==  0
   nRepresentaciones (2^3*3^2*5^3*7^8*13^6)        ==  14
   head [n | n <- [1..], nRepresentaciones n > 8]  ==  71825

Usando la función representaciones del ejercicio anterior, comprobar con QuickCheck la siguiente propiedad

prop_nRepresentaciones :: Integer -> Property
prop_nRepresentaciones n =
    n > 0 ==>
      nRepresentaciones2 n == genericLength (representaciones n)

Leer más…

Definir la función

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

tal que (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2. Por ejemplo.

representaciones  20           ==  [(2,4)]
representaciones  25           ==  [(0,5),(3,4)]
representaciones 325           ==  [(1,18),(6,17),(10,15)]
representaciones 100000147984  ==  [(0,316228)]

Comprobar con QuickCheck que un número natural n se puede representar como suma de dos cuadrados si, y sólo si, en la factorización prima de n todos los exponentes de sus factores primos congruentes con 3 módulo 4 son pares.

Leer más…

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...

Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...

Definir la función

factorizacionesH :: Integer -> [[Integer]]

tal que (factorizacionesH n) es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,

factorizacionesH  25  ==  [[5,5]]
factorizacionesH  45  ==  [[5,9]]
factorizacionesH 441  ==  [[9,49],[21,21]]

Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque laa factorización, como para el 441, puede no ser única).

Leer más…

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...

Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...

Definir la sucesión

primosH :: [Integer]

tal que sus elementos son los primos de Hilbert. Por ejemplo,

take 15 primosH  == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]
primosH !! 20000 == 203221

Leer más…

La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son

[0]
[0,1]
[0,1,1,0]
[0,1,1,0,1,0,0,1]
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]

De esta forma se va formando una sucesión

0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,...

que se conoce como la sucesión de Thue-Morse.

Definir la sucesión

sucThueMorse :: [Int]

cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,

λ> take 30 sucThueMorse
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]
λ> map (sucThueMorse4 !!) [1234567..1234596]
[1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0]
λ> map (sucThueMorse4 !!) [4000000..4000030]
[1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1]

Comprobar con QuickCheck que si s(n) representa el término n-ésimo de la sucesión de Thue-Morse, entonces

s(2n)   = s(n)
s(2n+1) = 1 - s(n)

Leer más…

Definir la función

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

tal que (ordPorFrecuencia xs) es la lista obtenidas ordenando los elementos de xs por su frecuencia, de los que aparecen menos a los que aparecen más. Por ejemplo,

ordPorFrecuencia "canalDePanama"  ==  "DPcelmnnaaaaa"
ordPorFrecuencia "20012016"       ==  "61122000"

Leer más…

El máximo común divisor (mcd) de dos números enteros no negativos se puede calcular mediante un algoritmo binario basado en las siguientes propiedades:

1. Si a,b son pares, entonces mcd(a,b) = 2*mcd(a/2,b/2)
2. Si a es par y b impar, entonces mcd(a,b) = mcd(a/2,b)
3. Si a es impar y b par, entonces mcd(a,b) = mcd(a,b/2)
4. Si a y b son impares y a > b, entonces mcd(a,b) = mcd((a-b)/2,b)
5. Si a y b son impares y a < b, entonces mcd(a,b) = mcd(a,(b-a)/2)
6. mcd(a,0) = a
7. mcd(0,b) = b
8. mcd(a,a) = a

Por ejemplo, el cálculo del mcd(660,420) es

mcd(660,420)
= 2*mcd(330,210)    [por 1]
= 2*2*mcd(165,105)  [por 1]
= 2*2*mcd(30,105)   [por 4]
= 2*2*mcd(15,105)   [por 2]
= 2*2*mcd(15,45)    [por 4]
= 2*2*mcd(15,15)    [por 4]
= 2*2*15            [por 8]
= 60

Definir la función

mcd :: Integer -> Integer -> Integer

Definir la función

tal que (mcd a b) es el máximo común divisor de a y b calculado mediante el algoritmo binario del mcd. Por ejemplo,

mcd 660 420  ==  60
mcd 3 0      ==  3
mcd 0 3      ==  3

Comprobar con QuickCheck que, para los enteros no negativos, las funciones mcd y gcd son equivalentes.

Leer más…

Definir la función

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

tal que (agrupa p xs) es la lista obtenida separando los elementos consecutivos de xs que verifican la propiedad p de los que no la verifican. Por ejemplo,

agrupa odd   [1,2,0,4,9,6,4,5,7,2]  ==  [[1],[2,0,4],[9],[6,4],[5,7],[2]]
agrupa even  [1,2,0,4,9,6,4,5,7,2]  ==  [[],[1],[2,0,4],[9],[6,4],[5,7],[2]]
agrupa (> 4) [1,2,0,4,9,6,4,5,7,2]  ==  [[],[1,2,0,4],[9,6],[4],[5,7],[2]]
agrupa (< 4) [1,2,0,4,9,6,4,5,7,2]  ==  [[1,2,0],[4,9,6,4,5,7],[2]]

Comprobar con QuickCheck que para cualquier propiedad p y cualquier lista xs, la concatenación de (agrupa p xs) es xs; es decir,

prop_agrupa :: Blind (Int -> Bool) -> [Int] -> Bool
prop_agrupa (Blind p) xs =
    concat (agrupa1 p xs) == xs

Nota. Usar la librería Test.QuickCheck.Modifiers.

Leer más…

Definir la sucesión

sumasDeDosPrimos :: [Integer]

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

λ> take 23 sumasDeDosPrimos
[4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31]

Leer más…

Los árboles binarios con datos en nodos y hojas se definen por

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

Por ejemplo, el árbol

       3
      / \
     /   \
    4     7
   / \   / \
  5   0 0   3
 / \
2   0

se representa por

ejArbol :: Arbol Integer
ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

Definir la función

sucesores :: Arbol a -> [(a,[a])]

tal que (sucesores t) es la lista de los pares formados por los elementos del árbol t junto con sus sucesores. Por ejemplo,

λ> sucesores ejArbol
[(3,[4,7]),(4,[5,0]),(5,[2,0]),(2,[]),(0,[]),(0,[]),
 (7,[0,3]),(0,[]),(3,[])]

Leer más…

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

• [(1,2),(3,6)] es una función de [1,3] en [2,4,6];
• [(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
• [(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primera coordenada es 1.

Definir la función

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

tal que (funciones xs ys) es el conjunto de las funciones de xs en ys. Por ejemplo,

λ> funciones [] [2,4,6]
[[]]
λ> funciones [3] [2,4,6]
[[(3,2)],[(3,4)],[(3,6)]]
λ> funciones [1,3] [2,4,6]
[[(1,2),(3,2)], [(1,2),(3,4)], [(1,2),(3,6)], [(1,4),(3,2)], [(1,4),(3,4)],
 [(1,4),(3,6)], [(1,6),(3,2)], [(1,6),(3,4)], [(1,6),(3,6)]]

Comprobar con QuickCheck que si xs es un conjunto con n elementos e ys un conjunto con m elementos, entonces (funciones xs ys) tiene m^n elementos.

Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación

λ> quickCheckWith (stdArgs {maxSize=7}) prop_funciones
+++ OK, passed 100 tests.

Leer más…

La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son

[0]
[0,1]
[0,1,1,0]
[0,1,1,0,1,0,0,1]
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]

Definir la lista

serieThueMorse :: [[Integer]]

tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,

λ> take 4 serieThueMorse
[[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]

Comprobar con QuickCheck que cada término de la serie de Thue-Morse se obtiene del anterior sustituyendo los 1 por 1, 0 y los 0 por 0, 1.

Leer más…

Definir la función

primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]

tal que (primosConsecutivosConSumasDigitalesPrimas k) es la sucesión de lista de k primos consecutivos tales que las sumas ordenadas de sus dígitos también son primos consecutivos. Por ejemplo,

λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 2)
[[2,3],[3,5],[5,7],[41,43],[43,47]]
λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 3)
[[2,3,5],[3,5,7],[41,43,47],[191,193,197],[193,197,199]]
λ> take 4 (primosConsecutivosConSumasDigitalesPrimas 4)
[[2,3,5,7],[3,5,7,11],[191,193,197,199],[821,823,827,829]]
λ> primosConsecutivosConSumasDigitalesPrimas 4 !! 50
[129197,129209,129221,129223]

Leer más…

Un número n es k-belga si la sucesión cuyo primer elemento es k y cuyos elementos se obtienen sumando reiteradamente las cifras de n contiene a n. Por ejemplo,

• El 18 es 0-belga, porque a partir del 0 vamos a ir sumando sucesivamente 1, 8, 1, 8, ... hasta llegar o sobrepasar el 18: 0, 1, 9, 10, 18, ... Como se alcanza el 18, resulta que el 18 es 0-belga.
• El 19 no es 1-belga, porque a partir del 1 vamos a ir sumando sucesivamente 1, 8, 1, 8, ... hasta llegar o sobrepasar el 18: 0, 1, 10, 11, 20, 21, ... Como no se alcanza el 19, resulta que el 19 no es 1-belga.

Definir la función

esBelga :: Int -> Int -> Bool

tal que (esBelga k n) se verifica si n es k-belga. Por ejemplo,

esBelga 0 18                              ==  True
esBelga 1 19                              ==  False
esBelga 0 2016                            ==  True
[x | x <- [0..30], esBelga 7 x]           ==  [7,10,11,21,27,29]
[x | x <- [0..30], esBelga 10 x]          ==  [10,11,20,21,22,24,26]
length [n | n <- [1..9000], esBelga 0 n]  ==  2857

Comprobar con QuickCheck que para todo número entero positivo n, si k es el resto de n entre la suma de los dígitos de n, entonces n es k-belga.

Leer más…

Definir la función

antiimagen :: (Int -> Int) -> Int -> Maybe Int

tal que (antiimagen f y) es justo el x tal que f(x) = y, si y pertenece a la imagen de la función creciente f, o nada, en caso contrario. Por ejemplo,

antiimagen (^2) 25  ==  Just 5
antiimagen (^3) 25  ==  Nothing

Nota. Se supone que f está definida sobre los números naturales.

Leer más…

Dada una matriz cuyos elementos son 0 ó 1, su relleno es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen algún uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha:

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

Las matrices se pueden representar mediante tablas cuyos índices son pares de enteros

type Matriz = Array (Int,Int) Int

por ejemplo, la matriz de la izquierda de la figura anterior se define por

ej :: Matriz
ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
                              0, 0, 0, 0, 0,
                              0, 0, 0, 1, 0,
                              1, 0, 0, 0, 0,
                              0, 0, 0, 0, 0]

Definir la función

relleno :: Matriz -> Matriz

tal que (relleno p) es el relleno de la matriz p. Por ejemplo,

λ> elems (relleno ej)
[1,0,0,1,0,
 1,0,0,1,0,
 1,1,1,1,1,
 1,1,1,1,1,
 1,0,0,1,0]

Leer más…

Definir la sucesión

primosCon2016 :: [Integer]

tal que sus elementos son los números primos que contienen al 2016. Por ejemplo,

take 5 primosCon2016  ==  [20161,120163,120167,201611,201623]
primosCon2016 !! 111  ==  3020167

Leer más…

El hueco de un número primo p es la distancia entre p y primo siguiente de p. Por ejemplo, el hueco de 7 es 4 porque el primo siguiente de 7 es 11 y 4 = 11-7. Los huecos de los primeros números son

Primo Hueco
 2    1
 3    2
 7    4
11    2

El hueco de un número primo p es maximal si es mayor que los huecos de todos los números menores que p. Por ejemplo, 4 es un hueco maximal de 7 ya que los huecos de los primos menores que 7 son 1 y 2 y ambos son menores que 4. La tabla de los primeros huecos maximales es

Primo Hueco
  2    1
  3    2
  7    4
 23    6
 89    8
113   14
523   18
887   20

Definir la sucesión

primosYhuecosMaximales :: [(Integer,Integer)]

cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,

λ> take 8 primosYhuecosMaximales
[(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)]
λ> primosYhuecosMaximales !! 20
(2010733,148)

Leer más…

En lógica matemática, un literal es una fórmula atómica o su negación. Se puede definir por el tipo de dato

data Literal = Atom String
             | Neg Literal
             deriving (Eq, Show)

Por ejemplo, el literal los literales p y ¬q se representan por las expresiones (Atom "p") y (Neg (Atom "q")), respectivamente.

Una lista de literales (que se interpreta como su disyunción) es un tautología si contiene a una fórmula atómica y su negación.

Definir la función

tautologia :: [Literal] -> Bool

tal que (tautologia xs) se verifica si la lista de literales xs es una tautología. Por ejemplo,

λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "p")]
True
λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "r")]
False
λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "q")]
False