Un número n es abundante si la suma de los divisores propios de n es mayor que n. El primer número abundante es el 12 (cuyos divisores propios son 1, 2, 3, 4 y 6 cuya suma es 16). Por tanto, el menor número que es la suma de dos números abundantes es el 24.
Definir la sucesión
sumasDeDosAbundantes :: [Integer] |
cuyos elementos son los números que se pueden escribir como suma de dos números abundantes. Por ejemplo,
take 10 sumasDeDosAbundantes == [24,30,32,36,38,40,42,44,48,50] |
Definir la función
sumaDivisores :: Integer -> Integer |
tal que (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
sumaDivisores 12 == 28 sumaDivisores 25 == 31 sumaDivisores (product [1..25]) == 93383273455325195473152000 length (show (sumaDivisores (product [1..30000]))) == 121289 maximum (map sumaDivisores [1..10^5]) == 403200 |
Definir la función
numeroDivisores :: Integer -> Integer |
tal que (numeroDivisores x) es el número de divisores de x. Por ejemplo,
numeroDivisores 12 == 6 numeroDivisores 25 == 3 length (show (numeroDivisores (product [1..3*10^4]))) == 1948 |
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 23 == 8
minimoSumandosDigitos 232 == 78
minimoSumandosDigitos 2323 == 775
map minimoSumandosDigitos [10..20] == [10,11,6,5,5,3,6,5,4,3,10] |
import Test.QuickCheck import Graphics.Gnuplot.Simple import Data.List (nub, genericLength, sort) import Data.Array (array, (!)) minimoSumandosDigitos :: Integer -> Integer minimoSumandosDigitos n = minimoSumandos (digitos n) n -- (digitos n) es el conjunto de los dígitos no nulos de n. Por ejemplo, -- digitos 2032 == [2,3] digitos :: Integer -> [Integer] digitos n = nub [read [c] | c <- show n, c /= '0'] -- (minimoSumandos xs n) es el menor número de elementos de la lista de -- enteros positivos xs (con posibles repeticiones) cuya suma es n. Por -- ejemplo, -- minimoSumandos [7,2,4] 11 == 2 minimoSumandos :: [Integer] -> Integer -> Integer minimoSumandos xs n = minimum (map genericLength (sumas xs n)) -- (sumas xs n) es la lista de elementos de la lista de enteros -- positivos xs (con posibles repeticiones) cuya suma es n. Por ejemplo, -- sumas [7,2,4] 11 == [[7,2,2],[7,4]] sumas :: [Integer] -> Integer -> [[Integer]] sumas [] 0 = [[]] sumas [] _ = [] sumas (x:xs) n | x <= n = map (x:) (sumas (x:xs) (n-x)) ++ sumas xs n | otherwise = sumas xs n -- 2ª solución -- =========== minimoSumandosDigitos2 :: Integer -> Integer minimoSumandosDigitos2 n = aux n where aux 0 = 0 aux k = 1 + minimo [aux (k - x) | x <- ds, k >= x] ds = digitos n infinito = 10^100 minimo xs | null xs = infinito | otherwise = minimum xs -- 3ª solución -- =========== minimoSumandosDigitos3 :: Integer -> Integer minimoSumandosDigitos3 n = v ! n where v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f k = 1 + minimo [v ! (k - x) | x <- ds, k >= x] ds = digitos n infinito = 10^100 minimo xs | null xs = infinito | otherwise = minimum xs -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_minimoSumandosDigitos :: Positive Integer -> Bool prop_minimoSumandosDigitos (Positive n) = r1 == r2 && r2 == r3 where r1 = minimoSumandosDigitos n r2 = minimoSumandosDigitos n r3 = minimoSumandosDigitos n -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=9}) prop_minimoSumandosDigitos -- +++ OK, passed 100 tests. -- Definición de graficaMinimoSumandosDigitos -- ========================================== graficaMinimoSumandosDigitos :: Integer -> IO () graficaMinimoSumandosDigitos n = plotList [ Key Nothing -- , PNG "Numero_como_suma_de_sus_digitos.png" ] [minimoSumandosDigitos k | k <- [0..n-1]] |
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
λ> 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] |
import Data.Char (digitToInt) import Data.List (genericLength, inits, tails) import Graphics.Gnuplot.Simple ( Attribute (Key, PNG) , plotList ) -- Definición de mediasDigitosDePi -- =============================== mediasDigitosDePi :: IO [Double] mediasDigitosDePi = do (_:_:ds) <- readFile "Digitos_de_pi.txt" return (medias (digitos ds)) -- (digitos cs) es la lista de los digitos de cs. Por ejempplo, -- digitos "1415926535" == [1,4,1,5,9,2,6,5,3,5] digitos :: String -> [Int] digitos = map digitToInt -- (medias xs) es la lista de las medias de los segmentos iniciales de -- xs. Por ejemplo, -- λ> medias [1,4,1,5,9,2,6,5,3,5] -- [1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1] medias :: [Int] -> [Double] medias xs = map media (tail (inits xs)) -- (media xs) es la media aritmética de xs. Por ejemplo, -- media [1,4,1,5,9] == 4.0 media :: [Int] -> Double media xs = fromIntegral (sum xs) / genericLength xs -- Definición de graficaMediasDigitosDePi -- ====================================== graficaMediasDigitosDePi :: Int -> IO () graficaMediasDigitosDePi n = do xs <- mediasDigitosDePi plotList [ Key Nothing , PNG ("Medias_de_digitos_de_pi_" ++ show n ++ ".png") ] (take n xs) |
Es el mejor de los buenos
quien sabe que en esta vida
todo es cuestión de medida:
un poco más, algo menos.Antonio Machado
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:
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 |
import Data.List (genericLength) -- 1ª solución -- ============ numeroAvistamientos :: Double -> Double -> Double -> Integer numeroAvistamientos h r v | adecuados h r v = 2 * n - 1 | otherwise = -1 where n = genericLength (takeWhile (>=v) (iterate (*r) h)) -- (adecuados h r v) se verifica si los datos cumplen las condiciones -- para que el experimento sea válido. adecuados :: Double -> Double -> Double -> Bool adecuados h r v = h > 0 && 0 < r && r < 1 && 0 < v && v < h -- 2ª solución -- =========== numeroAvistamientos2 :: Double -> Double -> Double -> Integer numeroAvistamientos2 h r v | adecuados h r v = 2 + numeroAvistamientos2 (h * r) r v | otherwise = -1 -- 3ª solución numeroAvistamientos3 :: Double -> Double -> Double -> Integer numeroAvistamientos3 h r v | adecuados h r v = 1 + 2 * floor (logBase r (v / h)) | otherwise = -1 |
“Los patrones del matemático, como los del pintor o el poeta deben ser hermosos; las ideas, como los colores o las palabras deben encajar de manera armoniosa. La belleza es la primera prueba: no hay lugar permanente en este mundo para las matemáticas feas.”
¡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 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 |
import Data.List (genericLength) import Data.List.Split (splitOn) -- 1ª solución -- =========== porcentajeInfectados :: String -> Double porcentajeInfectados xs | nh == 0 = 0 | otherwise = 100 * ni / nh where ni = fromIntegral (numeroInfectados xs) nh = fromIntegral (numeroHabitantes xs) -- (continentes xs) es la lista de las poblaciones de los continentes -- del mapa xs. Por ejemplo, -- continentes "01000000X000X011X0X" == ["01000000","000","011","0"] -- continentes "01X000X010X011XX" == ["01","000","010","011"] -- continentes "XXXXX" == [""] -- continentes "0000000010" == ["0000000010"] -- continentes "X00X000000X10X0100" == ["","00","000000","10","0100"] continentes :: String -> [String] continentes [] = [] continentes xs = as : continentes (dropWhile (=='X') bs) where (as,bs) = break (=='X') xs -- (numeroInfectados xs) es el número final de infectados a partir del -- mapa xs. Por ejemplo, -- numeroInfectados "01000000X000X011X0X" == 11 numeroInfectados :: String -> Int numeroInfectados xs = sum [length ys | ys <- continentes xs , '1' `elem` ys] -- (numeroHabitantes xs) es el número final de habitantes del mapa -- xs. Por ejemplo, -- numeroHabitantes "01000000X000X011X0X" == 15 numeroHabitantes :: String -> Int numeroHabitantes xs = length (filter (/='X') xs) -- 2ª solución -- =========== porcentajeInfectados2 :: String -> Double porcentajeInfectados2 xs | nh == 0 = 0 | otherwise = 100 * ni / nh where ni = sum [genericLength ys | ys <- splitOn "X" xs, '1' `elem` ys] nh = genericLength (filter (/='X') xs) |
“El avance de las matemáticas puede ser visto como un progreso de lo infinito a lo finito.”
El triágulo de Bell es el triángulo numérico, cuya primera fila es [1] y en cada fila, el primer elemento es el último de la fila anterior y el elemento en la posición j se obtiene sumando el elemento anterior de su misma fila y de la fila anterior. Sus primeras filas son
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 52 67 87 114 151 203 |
Definir la función
trianguloDeBell :: [[Integer]] |
tal que trianguloDeBell es la lista con las filas de dicho triángulo. Por ejemplo
λ> take 5 trianguloDeBell [[1],[1,2],[2,3,5],[5,7,10,15],[15,20,27,37,52]] |
Comprobar con QuickCheck que los números que aparecen en la primera columna del triángulo coinciden con los números de Bell; es decir, el primer elemento de la n-ésima fila es el n-ésimo número de Bell.
import Data.List (genericIndex, genericLength) import Test.QuickCheck trianguloDeBell :: [[Integer]] trianguloDeBell = iterate siguiente [1] -- (siguiente xs) es la fila siguiente de xs en el triángulo de -- Bell. Por ejemplo, -- siguiente [1] == [1,2] -- siguiente [1,2] == [2,3,5] -- siguiente [2,3,5] == [5,7,10,15] siguiente :: [Integer] -> [Integer] siguiente xs = last xs : zipWith (+) xs (siguiente xs) -- Propiedad -- ========= -- La propiedad es prop_TrianguloDeBell :: Integer -> Property prop_TrianguloDeBell n = n > 0 ==> head (trianguloDeBell `genericIndex` n) == bell n -- (bell n) es el n-ésimo número de Bell definido en el ejercicio -- anterior. bell :: Integer -> Integer bell n = genericLength (particiones [1..n]) particiones :: [a] -> [[[a]]] particiones [] = [[]] particiones (x:xs) = concat [([x] : yss) : inserta x yss | yss <- ysss] where ysss = particiones xs inserta :: a -> [[a]] -> [[[a]]] inserta _ [] = [] inserta x (ys:yss) = ((x:ys):yss) : [ys : zs | zs <- inserta x yss] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_TrianguloDeBell -- +++ OK, passed 100 tests. |
“La ciencia es lo que entendemos lo suficientemente bien como para explicarle a una computadora. El arte es todo lo demás.”
Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:
{{1}, {2}, {3}}
{{1,2}, {3}}
{{1,3}, {2}}
{{1}, {2,3}}
{{1,2,3}} |
El n-ésimo número de Bell, B(n), es el número de particiones de un conjunto de n elementos. Por lo visto anteriormentem B(3) = 5.
Definir las funciones
particiones :: [a] -> [[[a]]] bell :: Integer -> Integer |
tales que
λ> particiones [1,2]
[[[1,2]],[[1],[2]]]
λ> particiones [1,2,3]
[[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[2],[1,3]],[[1],[2],[3]]]
λ> particiones "abcd"
[["abcd"],["a","bcd"],["ab","cd"],["b","acd"],["abc","d"],["bc","ad"],
["ac","bd"],["c","abd"],["a","b","cd"],["a","bc","d"],["a","c","bd"],
["ab","c","d"],["b","ac","d"],["b","c","ad"],["a","b","c","d"]] |
λ> bell 3
5
λ> map bell [0..10]
[1,1,2,5,15,52,203,877,4140,21147,115975] |
Comprobar con QuickCheck que (bell n) es equivalente a la función B(n) definida por
import Data.List (genericLength) import Test.QuickCheck -- Definición de particiones -- ========================= particiones :: [a] -> [[[a]]] particiones [] = [[]] particiones (x:xs) = concat [([x] : yss) : inserta x yss | yss <- ysss] where ysss = particiones xs -- (inserta x yss) es la lista obtenida insertando x en cada uno de los -- elementos de yss. Por ejemplo, -- λ> inserta 1 [[2,3],[4],[5,6,7]] -- [[[1,2,3],[4],[5,6,7]],[[2,3],[1,4],[5,6,7]],[[2,3],[4],[1,5,6,7]]] inserta :: a -> [[a]] -> [[[a]]] inserta _ [] = [] inserta x (ys:yss) = ((x:ys):yss) : [ys : zs | zs <- inserta x yss] -- Definición de Bell -- ================== bell :: Integer -> Integer bell n = genericLength (particiones [1..n]) -- Propiedad -- ========= prop_Bell :: Integer -> Property prop_Bell n = n >= 0 ==> bell n == b n b :: Integer -> Integer b 0 = 1 b n = sum [comb (n-1) k * b k | k <- [0..n-1]] comb :: Integer -> Integer -> Integer comb n k = product [n-k+1..n] `div` product [1..k] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_Bell -- +++ OK, passed 100 tests. |
“Cambiemos nuestra actitud tradicional en la construcción de programas. En lugar de imaginar que nuestra tarea principal es indicarle a una computadora lo que debe hacer, concentrémonos más bien en explicarle a los seres humanos lo que queremos que haga una computadora.”
La conjetura de Goldbach afirma que todo número entero mayor que 2 se puede expresar como suma de dos primos.
Las descomposiciones de Goldbach son las maneras de expresar un número como suma de dos primos. Por ejemplo, el número 10 tiene dos descomposiciones de Goldbach ya que se puede expresar como la suma de 3 y 7 y la suma de 5 y 5.
Definir las funciones
descomposicionesGoldbach :: Integer -> [(Integer,Integer)] numeroGoldbach :: Integer -> Integer tieneMaximoLocalGoldbach :: Integer -> Bool |
tales que
descomposicionesGoldbach 5 == [(2,3)]
descomposicionesGoldbach 10 == [(3,7),(5,5)]
descomposicionesGoldbach 22 == [(3,19),(5,17),(11,11)]
descomposicionesGoldbach 34 == [(3,31),(5,29),(11,23),(17,17)]
descomposicionesGoldbach 35 == []
descomposicionesGoldbach (9+10^9) == [(2,1000000007)] |
numeroGoldbach 5 == 1
numeroGoldbach 10 == 2
numeroGoldbach 22 == 3
numeroGoldbach 34 == 4
numeroGoldbach 35 == 0
numeroGoldbach (9+10^9) == 1
maximum [numeroGoldbach n | n <- [2..3000]] == 128 |
λ> filter tieneMaximoLocalGoldbach [1..45]
[1,2,4,5,6,7,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44] |
En el ejemplo anterior se comprueba que en los múltiplos de 6 (es decir, en 6, 12, 18, 24, 30, 36 y 42), el número de descomposiciones de Goldbach alcanza un máximo local. Comprobar con QuickCheck que esta propiedad se cumple en general; es decir, para todo entero positivo n, el número de descomposiciones de Goldbach en 6n es un máximo local.
import Data.List (genericLength) import Data.Numbers.Primes (primes, isPrime) import Test.QuickCheck -- Definiciones de descomposicionesGoldbach -- ======================================== -- 1ª definición descomposicionesGoldbach1 :: Integer -> [(Integer,Integer)] descomposicionesGoldbach1 n = [(p,n-p) | p <- takeWhile (<= n `div` 2) primes , isPrime (n-p)] -- 2ª definición descomposicionesGoldbach2 :: Integer -> [(Integer,Integer)] descomposicionesGoldbach2 n | odd n = [(2,n-2) | isPrime (n-2)] | otherwise = [(p,n-p) | p <- takeWhile (<= n `div` 2) primes , isPrime (n-p)] -- Comparación de eficiencia -- λ> descomposicionesGoldbach1 (9+10^8) -- [(2,100000007)] -- (10.75 secs, 32,177,389,480 bytes) -- λ> descomposicionesGoldbach2 (9+10^8) -- [(2,100000007)] -- (0.01 secs, 3,228,912 bytes) -- En lo que sigue, usaremos la 2ª definición descomposicionesGoldbach :: Integer -> [(Integer,Integer)] descomposicionesGoldbach = descomposicionesGoldbach2 -- Definición de numeroGolbach -- =========================== numeroGoldbach :: Integer -> Integer numeroGoldbach = genericLength . descomposicionesGoldbach -- Definición de tieneMaximoLocalGoldbach -- ====================================== tieneMaximoLocalGoldbach :: Integer -> Bool tieneMaximoLocalGoldbach n = numeroGoldbach (n-1) <= x && x >= numeroGoldbach (n+1) where x = numeroGoldbach n -- La propiedad es prop_Goldbach :: Integer -> Property prop_Goldbach n = n > 0 ==> tieneMaximoLocalGoldbach (6*n) -- La comprobación es -- λ> quickCheck prop_Goldbach -- +++ OK, passed 100 tests. |
Te abanicaras
con un madrigal que diga:
en amor el olvido pone la sal.Antonio Machado
José A. Alonso