La cadena infinita "1234321234321234321...", formada por la repetición de los dígitos 123432, tiene una propiedad (en la que se basa el funcionamiento del reloj astronómico de Praga: la cadena se puede partir en una sucesión de números, de forma que la suma de los dígitos de dichos números es la serie de los números naturales, como se observa a continuación:

1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, ...
1, 2, 3, 4,  5,   6,  7,    8,   9,   10,    11, ...

Definir la lista

reloj :: [Integer]

cuyos elementos son los términos de la sucesión anterior. Por ejemplo,

λ> take 11 reloj
[1,2,3,4,32,123,43,2123,432,1234,32123]

Nota: La relación entre la sucesión y el funcionamiento del reloj se puede ver en The Mathematics Behind Prague's Horloge Introduction.

Leer más…

Sea p(n) el n-ésimo primo y sea r el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2. Por ejemplo,

si n = 3, entonces p(3) =  5 y r = ( 4^3 +  6^3) mod  (5^2) =   5
si n = 7, entonces p(7) = 17 y r = (16^7 + 18^7) mod (17^2) = 238

Definir la función

menorPR :: Integer -> Integer

tal que (menorPR x) es el menor n tal que el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2 es mayor que x. Por ejemplo,

menorPR 100     == 5
menorPR 345     == 9
menorPR 1000    == 13
menorPR (10^9)  == 7037
menorPR (10^10) == 21035
menorPR (10^12) == 191041

Leer más…

El polinomio cromático de un grafo calcula el número de maneras en las cuales puede ser coloreado el grafo usando un número de colores dado, de forma que dos vértices adyacentes no tengan el mismo color.

En el caso del grafo completo de n vértices, su polinomio cromático es

P(n,x) = x(x-1)(x-2) ... (x-(n-1))

Por ejemplo,

P(3,x) = x(x-1)(x-2)      = x^3 - 3·x^2 + 2·x
P(4,x) = x(x-1)(x-2)(x-3) = x^4 - 6·x^3 + 11·x^2 - 6·x

Lo que significa que P(4)(x) es el número de formas de colorear el grafo completo de 4 vértices con x colores. Por tanto,

P(4,2) =  0 (no se puede colorear con 2 colores)
P(4,4) = 24 (hay 24 formas de colorearlo con 4 colores)

Definir la función

polGC:: Int -> Polinomio Int

tal que (polGC n) es el polinomio cromático del grafo completo de n vértices. Por ejemplo,

polGC 4  ==  x^4 + -6*x^3 + 11*x^2 + -6*x
polGC 5  ==  x^5 + -10*x^4 + 35*x^3 + -50*x^2 + 24*x

Comprobar con QuickCheck que si el número de colores (x) coincide con el número de vértices del grafo (n), el número de maneras de colorear el grafo es n!.

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

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

Nota 2: Este ejercicio debe realizarse usando únicamente las funciones de la librería de polinomios (I1M.PolOperaciones) que aquí.

Leer más…

Definir la función

sumaPosteriores :: [Int] -> [Int]

tal que (sumaPosteriores xs) es la lista obtenida sustituyendo cada elemento de xs por la suma de los elementos posteriores. Por ejemplo,

sumaPosteriores [1..8]        == [35,33,30,26,21,15,8,0]
sumaPosteriores [1,-3,2,5,-8] == [-4,-1,-3,-8,0]

Comprobar con QuickCheck que el último elemento de la lista (sumaPosteriores xs) siempre es 0.

Leer más…

Un sistema de ecuaciones lineales Ax = b es triangular inferior si todos los elementos de la matriz A que están por encima de la diagonal principal son nulos; es decir, es de la forma

a(1,1)·x(1)                                               = b(1)
a(2,1)·x(1) + a(2,2)·x(2)                                 = b(2)
a(3,1)·x(1) + a(3,2)·x(2) + a(3,3)·x(3)                   = b(3)
...
a(n,1)·x(1) + a(n,2)·x(2) + a(n,3)·x(3) +...+ a(x,x)·x(n) = b(n)

El sistema es compatible si, y sólo si, el producto de los elementos de la diagonal principal es distinto de cero. En este caso, la solución se puede calcular mediante el algoritmo de bajada:

x(1) = b(1) / a(1,1)
x(2) = (b(2) - a(2,1)·x(1)) / a(2,2)
x(3) = (b(3) - a(3,1)·x(1) - a(3,2)·x(2)) / a(3,3)
...
x(n) = (b(n) - a(n,1)·x(1) - a(n,2)·x(2) -...- a(n,n-1)·x(n-1)) / a(n,n)

Definir la función

bajada :: Matrix Double -> Matrix Double -> Matrix Double

tal que (bajada a b) es la solución, mediante el algoritmo de bajada, del sistema compatible triangular superior ax = b. Por ejemplo,

λ> let a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]]
λ> let b = fromLists [[3],[6.5],[10]]
λ> bajada a b
( 1.5 )
( 2.0 )
( 0.0 )

Es decir, la solución del sistema

2x            = 3
3x + y        = 6.5
4x + 2y + 5 z = 10

es x=1.5, y=2 y z=0.

Leer más…

Definir la función

mayorProductoAdyacentes :: (Num a, Ord a) => Int -> Matriz a -> [[a]]

tal que (mayorProductoAdyacentes n p) es la lista de los segmentos formados por n elementos adyacentes en la misma fila, columna o diagonal de la matriz p cuyo productos son máximo. Por ejemplo,

λ> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1..12])
[[10,11,12]]
λ> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1])
[[3,7,9]]
λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,3,4, 0,3,2])
[[3,4],[4,3]]
λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,0,3])
[[2,3],[2,3]]
λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,4,3])
[[3,4],[4,3]]
λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,5,1, 3,4,3])
[[5,4]]
λ> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1])
[[3,7,9]]

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…

Un número n es especial si mcm(1,2,...,n-1) = mcm(1,2,...,n). Por ejemplo, el 6 es especial ya que

mcm(1,2,3,4,5) = 60 = mcm(1,2,3,4,5,6)

Definir la sucesión

especiales :: [Integer]

cuyos términos son los números especiales. Por ejemplo,

take 10 especiales     ==  [1,6,10,12,14,15,18,20,21,22]
especiales !! 50       ==  84
especiales !! 500      ==  638
especiales !! 5000     ==  5806
especiales !! 50000    ==  55746

Leer más…

Definir la función

suma :: Integer -> Integer

tal que (suma n) es la suma 1 * 1! + 2 * 2! + 3 * 3! + ... + n * n!. Por ejemplo,

suma 1  ==  1
suma 2  ==  5
suma 3  ==  23
suma 4  ==  119
suma 5  ==  719
take 9 (show (suma (70000)))  ==  "823780458"

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) + \dots + f\left(a + nh + \frac{h}{2}\right) \right) \] con \[ a + n h + \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…