Definir la función

clasesEquivalencia :: Ord a =>
Set a -> (a -> a -> Bool) -> Set (Set a)

tal que (clasesEquivalencia xs r) es el conjunto de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

λ> let c = fromList [-3..3]
λ> clasesEquivalencia c (\x y -> x `mod` 3 == y `mod` 3)
fromList [fromList [-3,0,3],fromList [-2,1],fromList [-1,2]]
λ> clasesEquivalencia c (\x y -> (x - y) `mod` 2 == 0)
fromList [fromList [-3,-1,1,3],fromList [-2,0,2]]

Leer más…

Sea f la siguiente función, aplicable a cualquier número entero positivo:

• Si el número es par, se divide entre 2.
• Si el número es impar, se multiplica por 3 y se suma 1.

La carrera de Collatz consiste en, dada una lista de números ns, sustituir cada número n de ns por f(n) hasta que alguno sea igual a 1. Por ejemplo, la siguiente sucesión es una carrera de Collatz

[ 3, 6,20, 49, 73]
[10, 3,10,148,220]
[ 5,10, 5, 74,110]
[16, 5,16, 37, 55]
[ 8,16, 8,112,166]
[ 4, 8, 4, 56, 83]
[ 2, 4, 2, 28,250]
[ 1, 2, 1, 14,125]

En esta carrera, los ganadores son 3 y 20.

Definir la función

ganadores :: [Int] -> [Int]

tal que (ganadores ns) es la lista de los ganadores de la carrera de Collatz a partir de la lista inicial ns. Por ejmplo,

ganadores [3,6,20,49,73]  ==  [3,20]

Leer más…

Definir la función

maximoIntercambio :: Int -> Int

tal que (maximoIntercambio x) es el máximo número que se puede obtener intercambiando dos dígitos de x. Por ejemplo,

maximoIntercambio 983562  ==  986532
maximoIntercambio 31524   ==  51324
maximoIntercambio 897     ==  987

Leer más…

Definir la lista

antecesoresYsucesores :: [[Integer]]

cuyos elementos son

[[1],[0,2],[-1,1,1,3],[-2,2,0,0,2,0,2,2,4],...]

donde cada una de las listas se obtiene de la anterior sustituyendo cada elemento por su antecesor y su sucesor; es decir, el 1 por el 0 y el 2, el 0 por el -1 y el 1, el 2 por el 1 y el 3, etc. Por ejemplo,

λ> take 4 antecesoresYsucesores
[[1],[0,2],[-1,1,1,3],[-2,0,0,2,0,2,2,4]]

Comprobar con Quickcheck que la suma de los elementos de la lista n-ésima de antecesoresYsucesores es 2^n.

Nota. Limitar la búsqueda a ejemplos pequeños usando

quickCheckWith (stdArgs {maxSize=7}) prop_suma

Leer más…

Definir las siguientes funciones

arbolSubconjuntos       :: [a] -> Tree [a]
nNodosArbolSubconjuntos :: Integer -> Integer
sumaNNodos              :: Integer -> Integer

tales que

• (arbolSubconjuntos xs) es el árbol de los subconjuntos de xs. Por ejemplo.

λ> putStrLn (drawTree (arbolSubconjuntos "abc"))
abc
|
+- bc
|  |
|  +- c
|  |
|  `- b
|
+- ac
|  |
|  +- c
|  |
|  `- a
|
`- ab
   |
   +- b
   |
   `- a

• (nNodosArbolSubconjuntos xs) es el número de nodos del árbol de xs. Por ejemplo

nNodosArbolSubconjuntos "abc"  ==  10
nNodosArbolSubconjuntos [1..4*10^4] `mod` (7+10^9) == 546503960

• (sumaNNodos n) es la suma del número de nodos de los árboles de los subconjuntos de [1..k] para 1 <= k <= n. Por ejemplo,

λ> sumaNNodos 3  ==  14
sumaNNodos (4*10^4) `mod` (7+10^9)  ==  249479844

Leer más…

El número 15 se puede escribir de 5 formas como suma de números naturales consecutivos:

15 = 0+1+2+3+4+5 = 1+2+3+4+5 = 4+5+6 = 7+8 = 15.

Definir las funciones

sucesionesConSuma        :: Int -> [(Int,Int)]
graficaSucesionesConSuma :: Int -> IO ()

tales que

• (sucesionesConSuma n) es la lista de los pares formados por el primero y por el último elemento de las sucesiones de números naturales consecutivos con suma n. Por ejemplo,

sucesionesConSuma 15             ==  [(0,5),(1,5),(4,6),(7,8),(15,15)]
length (sucesionesConSuma 3000)  ==  8

• (graficaSucesionesConSuma n) dibuja la gráfica del número de formas de escribir los n primeros números como suma de números naturales consecutivos. Por ejemplo, (graficaSucesionesConSuma 100) dibuja

Leer más…

Entre dos matrices de la misma dimensión se pueden aplicar distintas operaciones binarias entre los elementos en la misma posición. Por ejemplo, si a y b son las matrices

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

entonces a+b y a-b son, respectivamente

|4 8 8|     |2 0 4|
|7 7 9|     |3 5 5

Definir la función

opMatriz :: (Int -> Int -> Int) ->
Matriz Int -> Matriz Int -> Matriz Int

tal que (opMatriz f p q) es la matriz obtenida aplicando la operación f entre los elementos de p y q de la misma posición. Por ejemplo,

λ> a = listArray ((1,1),(2,3)) [3,4,6,5,6,7]
λ> b = listArray ((1,1),(2,3)) [1,4,2,2,1,2]
λ> elems (opMatriz (+) a b)
[4,8,8,7,7,9]
λ> elems (opMatriz max a b)
[3,4,6,5,6,7]
λ> c = listArray ((1,1),(2,2)) ["ab","c","d","ef"]
λ> d = listArray ((1,1),(2,2)) [3,1,0,5]
λ> elems (opMatriz menor c d)
[True,False,False,True]

Leer más…

Los números tetranacci son una generalización de los números de Fibonacci definidos por

T(0) = 0,
T(1) = 1,
T(2) = 1,
T(3) = 2,
T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4), para n > 3.

Los primeros números tetranacci son

0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208

Definir las funciones

tetranacci        :: Int -> Integer
graficaTetranacci :: Int -> IO ()

tales que

• (tetranacci n) es el n-ésimo número tetranacci. Por ejemplo,

λ> tetranacci 10
208
λ> map tetranacci [0..10]
[0,1,1,2,4,8,15,29,56,108,208]
λ> length (show (tetranacci5 (10^5)))
28501

• (graficaTetranacci n) dibuja la gráfica de los cocientes de n primeros pares de número tetranacci. Por ejemplo, (graficaTetranacci 300) dibuja

Leer más…

El ejercicio 4 de la Olimpiada Matemáticas de 1993 es el siguiente:

Demostrar que para todo número primo p distinto de 2 y de 5, existen infinitos múltiplos de p de la forma 1111......1 (escrito sólo con unos).

Definir la función

multiplosRepitunos :: Integer -> Integer -> [Integer]

tal que (multiplosRepitunos p n) es la lista de los múltiplos repitunos de p (es decir, de la forma 1111...1 escrito sólo con unos), donde p es un número primo distinto de 2 y 5. Por ejemplo,

head (multiplosRepitunos  7 10)       == 111111
head (multiplosRepitunos  7 (10^10))  == 111111111111
head (multiplosRepitunos  7 (10^20))  == 111111111111111111111111
head (multiplosRepitunos 19 (10^10))  == 111111111111111111

Comprobar con QuickCheck que para todo primo p mayor que 5 y todo número entero positivo n, existe un mútiplo repituno de p mayor que n.

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

Leer más…