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 |
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 |
Goldbach, el de la famosa conjetura, hizo por lo menos otra conjetura que finalmente resultó ser falsa.
Esta última decía que todo número compuesto impar puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado. Así por ejemplo,
9 = 7 + 2×1^2 15 = 7 + 2×2^2 21 = 3 + 2×3^2 25 = 7 + 2×3^2 27 = 19 + 2×2^2 33 = 31 + 2×1^2 |
Definir las sucesiones
imparesCompuestos :: [Integer] descomposiciones :: Integer -> [(Integer,Integer)] contraejemplosGoldbach :: [Integer] |
tales que
take 9 imparesCompuestos == [9,15,21,25,27,33,35,39,45] |
descomposiciones 9 == [(7,1)] descomposiciones 21 == [(3,9),(13,4),(19,1)] descomposiciones 5777 == [] |
Las 3 descomposiciones de 21 son
21 = 3 + 2*9 = 21 + 2*3^2 21 = 13 + 2*4 = 13 + 2*3^2 21 = 19 + 2*1 = 19 + 2*1^2 |
take 2 contraejemplosGoldbach == [5777,5993] |
Comprobar con QuickCheck que la conjetura de Golbach se verifica a partir de 5993; es decir, todo número compuesto impar mayor que 5993 puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado.
Nota: Basado en el artículo La menos conocida de las conjeturas de Goldbach de Claudio Meller en el blog Números y algo más.
import Data.Numbers.Primes import Test.QuickCheck imparesCompuestos :: [Integer] imparesCompuestos = filter esCompuesto [3,5..] -- (esCompuesto x) se verifica si x es un número compuesto. Por ejemplo, -- esCompuesto 6 == True -- esCompuesto 7 == False esCompuesto :: Integer -> Bool esCompuesto = not . isPrime contraejemplosGoldbach :: [Integer] contraejemplosGoldbach = filter esContraejemplo imparesCompuestos -- (esContraejemplo x) es verifica si el número impar compuesto x es un -- contraejemplo de la conjetura de Goldbach. Por ejemplo, -- esContraejemplo 5777 == True -- esContraejemplo 15 == False esContraejemplo :: Integer -> Bool esContraejemplo = null . descomposiciones descomposiciones :: Integer -> [(Integer,Integer)] descomposiciones n = [(p,x) | p <- takeWhile (<=n) primes , (n - p) `mod` 2 == 0 , let x = (n - p) `div` 2 , esCuadrado x] -- (esCuadrado x) es verifica si x es un cuadrado perfecto. Por ejemplo, -- esCuadrado 16 == True -- esCuadrado 27 == False esCuadrado :: Integer -> Bool esCuadrado x = y^2 == x where y = ceiling (sqrt (fromIntegral x)) -- La propiedad es prop_conjetura :: Int -> Property prop_conjetura n = n >= 0 ==> not (esContraejemplo (imparesCompuestosMayore5993 !! n)) where imparesCompuestosMayore5993 = dropWhile (<=5993) imparesCompuestos -- La comprobación es -- λ> quickCheck prop_conjetura -- +++ OK, passed 100 tests. |
“Obvio es la palabra más peligrosa de las matemáticas.”
Un número entero n es libre de cuadrados si no existe un número primo p tal que p² divide a n; es decir, los factores primos de n son todos distintos.
La función de Möbius μ(n) está definida para todos los enteros positivos como sigue:
Sus primeros valores son 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, …
La función de Mertens M(n) está definida para todos los enteros positivos como la suma de μ(k) para 1 ≤ k ≤ n. Sus primeros valores son 1, 0, -1, -1, -2, -1, -2, -2, …
La conjetura de Mertens afirma que
Para todo entero x mayor que 1, el valor absoluto de la función de Mertens en x es menor que la raíz cuadrada de x.
La conjetura fue planteada por Franz Mertens en 1897. Riele Odlyzko, demostraronen 1985 que la conjetura de Mertens deja de ser cierta más o menos a partir de , cifra que luego de algunos refinamientos se redujo a
.
Definir las funciones
mobius :: Integer -> Integer mertens :: Integer -> Integer graficaMertens :: Integer -> IO () |
tales que
mobius 6 == 1 mobius 30 == -1 mobius 12 == 0 |
mertens 1 == 1 mertens 2 == 0 mertens 3 == -1 mertens 5 == -2 mertens 661 == -11 mertens 1403 == 11 |
Comprobar con QuickCheck la conjetura de Mertens.
Nota: El ejercicio está basado en La conjetura de Merterns y su relación con un número tan raro como extremada y colosalmente grande publicado por @Alvy la semana pasada en Microsiervos.
import Data.Numbers.Primes (primeFactors) import Test.QuickCheck import Graphics.Gnuplot.Simple mobius :: Integer -> Integer mobius n | tieneRepetidos xs = 0 | otherwise = (-1)^(length xs) where xs = primeFactors n tieneRepetidos :: [Integer] -> Bool tieneRepetidos xs = or [x == y | (x,y) <- zip xs (tail xs)] mertens :: Integer -> Integer mertens n = sum (map mobius [1..n]) -- Definición de graficaMertens -- ============================ graficaMertens :: Integer -> IO () graficaMertens n = do plotLists [ Key Nothing , Title "Conjetura de Mertens" , PNG "La_conjetura_de_Mertens.png" ] [ [mertens k | k <- [1..n]] , raices , map negate raices ] where raices = [ceiling (sqrt k) | k <- [1..fromIntegral n]] -- Conjetura de Mertens -- ==================== -- La conjetura es conjeturaDeMertens :: Integer -> Property conjeturaDeMertens n = n > 1 ==> abs (mertens n) < ceiling (sqrt n') where n' = fromIntegral n -- La comprobación es -- λ> quickCheck conjeturaDeMertens -- +++ OK, passed 100 tests. |
“El control de la complejidad es la esencia de la programación informática.”
Definir la función
productoSuma4Cuadrados :: Integral a => [a] -> [a] -> [a] -> [a] -> a |
tal que (productoSuma4Cuadrados as bs cs ds) es el producto de las sumas de los cuadrados de cada una de las listas que ocupan la misma posición (hasta que alguna se acaba). Por ejemplo,
productoSuma4Cuadrados [2,3] [1,5] [4,6] [0,3,9] = (2² + 1² + 4² + 0²) * (3² + 5² + 6² + 3²) = (4 + 1 + 16 + 0) * (9 + 25 + 36 + 9) = 1659 |
Comprobar con QuickCheckWith que si as, bs cs y ds son listas no vacías de enteros positivos, entonces (productoSuma4Cuadrados as bs cs ds) se puede escribir como la suma de los cuadrados de cuatro enteros positivos.
import Data.List (zip4) import Test.QuickCheck -- 1ª solución -- =========== productoSuma4Cuadrados :: Integral a => [a] -> [a] -> [a] -> [a] -> a productoSuma4Cuadrados (a:as) (b:bs) (c:cs) (d:ds) = (a^2+b^2+c^2+d^2) * productoSuma4Cuadrados as bs cs ds productoSuma4Cuadrados _ _ _ _ = 1 -- 2ª solución -- =========== productoSuma4Cuadrados2 :: Integral a => [a] -> [a] -> [a] -> [a] -> a productoSuma4Cuadrados2 as bs cs ds = product [a^2 + b^2 + c^2 + d^2 | (a,b,c,d) <- zip4 as bs cs ds] -- Propiedad -- ========= -- La propiedad es prop_productoSuma4Cuadrados :: [Integer] -> [Integer] -> [Integer] -> [Integer] -> Property prop_productoSuma4Cuadrados as bs cs ds = all (not . null) [as, bs, cs, ds] ==> esSuma4Cuadrados (productoSuma4Cuadrados as' bs' cs' ds') where as' = [1 + abs a | a <- as] bs' = [1 + abs b | b <- bs] cs' = [1 + abs c | c <- cs] ds' = [1 + abs d | d <- ds] -- (esSuma4Cuadrados n) se verifica si n es la suma de 4 cuadrados. Por -- ejemplo, -- esSuma4Cuadrados 42 == True -- esSuma4Cuadrados 11 == False -- esSuma4Cuadrados 41 == False esSuma4Cuadrados :: Integer -> Bool esSuma4Cuadrados = not . null . sumas4Cuadrados -- (sumas4Cuadrados n) es la lista de las descomposiciones de n como -- sumas de 4 cuadrados. Por ejemplo, -- sumas4Cuadrados 42 == [(16,16,9,1),(25,9,4,4),(36,4,1,1)] sumas4Cuadrados :: Integer -> [(Integer,Integer,Integer,Integer)] sumas4Cuadrados n = [(a^2,b^2,c^2,d) | a <- [1 .. floor (sqrt (fromIntegral n / 4))] , b <- [a .. floor (sqrt (fromIntegral (n-a^2) / 3))] , c <- [b .. floor (sqrt (fromIntegral (n-a^2-b^2) / 2))] , let d = n - a^2 - b^2 - c^2 , c^2 <= d , esCuadrado d] -- (esCuadrado x) se verifica si x es un número al cuadrado. Por -- ejemplo, -- esCuadrado 25 == True -- esCuadrado 26 == False esCuadrado :: Integer -> Bool esCuadrado x = x == y * y where y = raiz x -- (raiz x) es la raíz cuadrada entera de x. Por ejemplo, -- raiz 25 == 5 -- raiz 24 == 4 -- raiz 26 == 5 raiz :: Integer -> Integer raiz x = floor (sqrt (fromIntegral x)) -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=5}) prop_productoSuma4Cuadrados -- +++ OK, passed 100 tests. |
¿Vivir? Sencillamente:
la sed y el agua cerca …
o el agua lejos, más, la sed y el agua,
un poco de cansancio ¡y a beberla!.Antonio Machado
El número 42 es una suma de cuatro cuadrados de números enteros positivos ya que
42 = 16 + 16 + 9 + 1 = 4² + 4² + 3² + 1² |
Definir las funciones
sumas4Cuadrados :: Integer -> [(Integer,Integer,Integer,Integer)] graficaNumeroSumas4Cuadrados :: Integer -> IO () |
tales que
sumas4Cuadrados 42 == [(16,16,9,1),(25,9,4,4),(36,4,1,1)] sumas4Cuadrados 14 == [] length (sumas4Cuadrados (5*10^4)) == 260 |
import Graphics.Gnuplot.Simple -- 1ª definición de sumas4Cuadrados -- ================================ sumas4Cuadrados :: Integer -> [(Integer,Integer,Integer,Integer)] sumas4Cuadrados n = [(a^2,b^2,c^2,d) | a <- [1..n] , b <- [a..n] , c <- [b..n] , let d = n - a^2 - b^2 - c^2 , c^2 <= d , esCuadrado d] -- (esCuadrado x) se verifica si x es un número al cuadrado. Por -- ejemplo, -- esCuadrado 25 == True -- esCuadrado 26 == False esCuadrado :: Integer -> Bool esCuadrado x = x == y * y where y = raiz x -- (raiz x) es la raíz cuadrada entera de x. Por ejemplo, -- raiz 25 == 5 -- raiz 24 == 4 -- raiz 26 == 5 raiz :: Integer -> Integer raiz x = floor (sqrt (fromIntegral x)) -- 2ª definición de sumas4Cuadrados -- ================================ -- Los intervalos de búqueda en la definición anterior se pueden reducir -- teniendo en cuenta las siguientes restricciones -- 1 <= a <= b <= c <= d -- n = a² + b² + c² + d² >= 4a² ==> a <= sqrt (n/4) -- n - a² = b² + c² + d² >= 3b² ==> b <= sqrt ((n-a²)/3) -- n - a² - b² = c² + d² >= 2c² ==> c <= sqrt ((n-a²-b²)/2) sumas4Cuadrados2 :: Integer -> [(Integer,Integer,Integer,Integer)] sumas4Cuadrados2 n = [(a^2,b^2,c^2,d) | a <- [1 .. floor (sqrt (fromIntegral n / 4))] , b <- [a .. floor (sqrt (fromIntegral (n-a^2) / 3))] , c <- [b .. floor (sqrt (fromIntegral (n-a^2-b^2) / 2))] , let d = n - a^2 - b^2 - c^2 , c^2 <= d , esCuadrado d] -- Comparación de eficiencia -- ========================= -- La comprobación es -- λ> length (sumas4Cuadrados 300) -- 11 -- (7.93 secs, 11,280,814,312 bytes) -- λ> length (sumas4Cuadrados2 300) -- 11 -- (0.01 secs, 901,520 bytes) -- Definición de graficaConvergencia -- ================================== graficaNumeroSumas4Cuadrados :: Integer -> IO () graficaNumeroSumas4Cuadrados n = plotList [ Key Nothing , Title "Numero de sumas como 4 cuadrados" , PNG "Sumas_de_cuatro_cuadrados.png" ] [length (sumas4Cuadrados2 k) | k <- [0..n]] -- Definición de esSuma4Cuadrados -- ============================== -- (esSuma4Cuadrados n) se verifica si n es la suma de 4 cuadrados. Por -- ejemplo, -- esSuma4Cuadrados 42 == True -- esSuma4Cuadrados 11 == False -- esSuma4Cuadrados 41 == False esSuma4Cuadrados :: Integer -> Bool esSuma4Cuadrados = not . null . sumas4Cuadrados2 |
¿Cuál es el peor de todos
los afanes? Preguntar.
¿Y el mejor? – Hacer camino
sin volver la vista atrás.Antonio Machado
El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el Teorema de Navidad de Fermat.
Definir las funciones
representaciones :: Integer -> [(Integer,Integer)] primosImparesConRepresentacionUnica :: [Integer] primos4nM1 :: [Integer] |
tales que
representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] representaciones 100000147984 == [(0,316228)] length (representaciones (10^10)) == 6 length (representaciones (4*10^12)) == 7 |
λ> take 20 primosImparesConRepresentacionUnica [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193] |
λ> take 20 primos4nM1 [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193] |
El teorema de Navidad de Fermat afirma que un número primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de números naturales p = x² + y^2 (con x <= y) si, y sólo si, p se puede escribir como uno más un múltiplo de 4 (es decir, que es congruente con 1 módulo 4).
Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.
import Data.Numbers.Primes (primes) import Test.QuickCheck -- 1ª definición de representaciones -- ================================= representaciones :: Integer -> [(Integer,Integer)] representaciones n = [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y] -- 2ª definición de representaciones -- ================================= representaciones2 :: Integer -> [(Integer,Integer)] representaciones2 n = [(x,raiz z) | x <- [0..raiz (n `div` 2)] , let z = n - x*x , esCuadrado z] -- (esCuadrado x) se verifica si x es un número al cuadrado. Por -- ejemplo, -- esCuadrado 25 == True -- esCuadrado 26 == False esCuadrado :: Integer -> Bool esCuadrado x = x == y * y where y = raiz x -- (raiz x) es la raíz cuadrada entera de x. Por ejemplo, -- raiz 25 == 5 -- raiz 24 == 4 -- raiz 26 == 5 raiz :: Integer -> Integer raiz 0 = 0 raiz 1 = 1 raiz x = aux (0,x) where aux (a,b) | d == x = c | c == a = a | d < x = aux (c,b) | otherwise = aux (a,c) where c = (a+b) `div` 2 d = c^2 -- 3ª definición de representaciones -- ================================= representaciones3 :: Integer -> [(Integer,Integer)] representaciones3 n = [(x,raiz3 z) | x <- [0..raiz3 (n `div` 2)] , let z = n - x*x , esCuadrado3 z] -- (esCuadrado x) se verifica si x es un número al cuadrado. Por -- ejemplo, -- esCuadrado3 25 == True -- esCuadrado3 26 == False esCuadrado3 :: Integer -> Bool esCuadrado3 x = x == y * y where y = raiz3 x -- (raiz3 x) es la raíz cuadrada entera de x. Por ejemplo, -- raiz3 25 == 5 -- raiz3 24 == 4 -- raiz3 26 == 5 raiz3 :: Integer -> Integer raiz3 x = floor (sqrt (fromIntegral x)) -- 4ª definición de representaciones -- ================================= representaciones4 :: Integer -> [(Integer, Integer)] representaciones4 n = aux 0 (floor (sqrt (fromIntegral n))) where aux x y | x > y = [] | otherwise = case compare (x*x + y*y) n of LT -> aux (x + 1) y EQ -> (x, y) : aux (x + 1) (y - 1) GT -> aux x (y - 1) -- Equivalencia de las definiciones de representaciones -- ==================================================== -- La propiedad es prop_representaciones_equiv :: (Positive Integer) -> Bool prop_representaciones_equiv (Positive n) = representaciones n == representaciones2 n && representaciones2 n == representaciones3 n && representaciones3 n == representaciones4 n -- La comprobación es -- λ> quickCheck prop_representaciones_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia de las definiciones de representaciones -- ================================================================= -- λ> representaciones 3025 -- [(0,55),(33,44)] -- (2.86 secs, 1,393,133,528 bytes) -- λ> representaciones2 3025 -- [(0,55),(33,44)] -- (0.00 secs, 867,944 bytes) -- λ> representaciones3 3025 -- [(0,55),(33,44)] -- (0.00 secs, 173,512 bytes) -- λ> representaciones4 3025 -- [(0,55),(33,44)] -- (0.00 secs, 423,424 bytes) -- -- λ> length (representaciones2 (10^10)) -- 6 -- (3.38 secs, 2,188,903,544 bytes) -- λ> length (representaciones3 (10^10)) -- 6 -- (0.10 secs, 62,349,048 bytes) -- λ> length (representaciones4 (10^10)) -- 6 -- (0.11 secs, 48,052,360 bytes) -- -- λ> length (representaciones3 (4*10^12)) -- 7 -- (1.85 secs, 1,222,007,176 bytes) -- λ> length (representaciones4 (4*10^12)) -- 7 -- (1.79 secs, 953,497,480 bytes) -- Definición de primosImparesConRepresentacionUnica -- ================================================= primosImparesConRepresentacionUnica :: [Integer] primosImparesConRepresentacionUnica = [x | x <- tail primes , length (representaciones4 x) == 1] -- Definición de primos4nM1 -- ======================== primos4nM1 :: [Integer] primos4nM1 = [x | x <- primes , x `mod` 4 == 1] -- Teorema de Navidad de Fermat -- ============================ -- La propiedad es prop_teoremaDeNavidadDeFermat :: Positive Int -> Bool prop_teoremaDeNavidadDeFermat (Positive n) = primosImparesConRepresentacionUnica !! n == primos4nM1 !! n -- La comprobación es -- λ> quickCheck prop_teoremaDeNavidadDeFermat -- +++ OK, passed 100 tests. |
Dijo Dios: brote la nada
Y alzó su mano derecha,
hasta ocultar su mirada.
Y quedó la nada hecha.Antonio Machado
La fórmula de Vieta para el cálculo de pi es la siguiente
Definir las funciones
aproximacionPi :: Int -> Double errorPi :: Double -> Int |
tales que
aproximacionPi 5 == 3.140331156954753 aproximacionPi 10 == 3.1415914215112 aproximacionPi 15 == 3.141592652386592 aproximacionPi 20 == 3.1415926535886207 aproximacionPi 25 == 3.141592653589795 |
errorPi 0.1 == 2 errorPi 0.01 == 4 errorPi 0.001 == 6 errorPi 0.0001 == 7 errorPi 1e-4 == 7 errorPi 1e-14 == 24 pi == 3.141592653589793 aproximacionPi 24 == 3.1415926535897913 |
-- 1ª definición de aproximacionPi aproximacionPi :: Int -> Double aproximacionPi n = product [2 / aux x | x <- [0..n]] where aux 0 = 1 aux 1 = sqrt 2 aux n = sqrt (2 + aux (n-1)) -- 2ª definición de aproximacionPi aproximacionPi2 :: Int -> Double aproximacionPi2 n = product [2/x | x <- 1 : xs] where xs = take n $ iterate (\x -> sqrt (2+x)) (sqrt 2) -- 3ª definición de aproximaxionPi aproximacionPi3 :: Int -> Double aproximacionPi3 n = product (2 : take n (map (2/) xs)) where xs = sqrt 2 : [sqrt (2 + x) | x <- xs] -- 1ª definición de errorPi errorPi :: Double -> Int errorPi x = head [n | n <- [1..] , abs (pi - aproximacionPi n) < x] -- 2ª definición de errorPi errorPi2 :: Double -> Int errorPi2 x = until aceptable (+1) 1 where aceptable n = abs (pi - aproximacionPi n) < x |
El tiempo que la barba me platea,
cavó mis ojos y agrandó mi frente,
va siendo en mi recuerdo transparente,
y mientras más al fondo, más clarea.Antonio Machado
La suma de los primos menores que 10 es 2 + 3 + 5 + 7 = 17.
Definir la función
sumaPrimosMenores :: Integer -> Integer |
tal que (sumaPrimosMenores n) es la suma de los primos menores que n. Por ejemplo,
sumaPrimosMenores 10 == 17 sumaPrimosMenores (5*10^5) == 9914236195 |
Nota: Este ejercicio está basado en el problema 10 del Proyecto Euler
import Data.Numbers.Primes (primes) -- 1ª solución -- =========== sumaPrimosMenores :: Integer -> Integer sumaPrimosMenores n = sum (takeWhile (<n) primos) -- primos es la lista de los números primos. Por ejemplo, -- λ> take 12 primos -- [2,3,5,7,11,13,17,19,23,29,31,37] primos :: [Integer] primos = 2 : filter esPrimo [3,5..] esPrimo :: Integer -> Bool esPrimo n = null [x | x <- [2..(ceiling . sqrt . fromIntegral) n] , n `mod` x == 0] -- 2ª solución -- =========== sumaPrimosMenores2 :: Integer -> Integer sumaPrimosMenores2 n = sum (takeWhile (<n) primos2) primos2 :: [Integer] primos2 = 2 : filter esPrimo2 [3,5..] esPrimo2 :: Integer -> Bool esPrimo2 x = all ((/= 0) . mod x) (takeWhile (<= floor (sqrt (fromIntegral x))) primos2) -- 3ª solución -- =========== sumaPrimosMenores3 :: Integer -> Integer sumaPrimosMenores3 n = sum (takeWhile (<n) primes) -- Comparación de eficiencia -- ========================= -- λ> sumaPrimosMenores (2*10^5) -- 1709600813 -- (2.56 secs, 1,522,015,240 bytes) -- λ> sumaPrimosMenores2 (2*10^5) -- 1709600813 -- (0.56 secs, 376,951,456 bytes) -- λ> sumaPrimosMenores3 (2*10^5) -- 1709600813 -- (0.07 secs, 62,321,888 bytes) |
El movimiento no es nada esencial. La fuerza puede ser inmóvil (lo es en su estado de pureza); mas no por ello deja de ser activa.
Antonio Machado
Los divisores primos de 13195 son 5, 7, 13 y 29. Por tanto, el mayor divisor primo de 13195 es 29.
Definir la función
mayorDivisorPrimo :: Integer -> Integer |
tal que (mayorDivisorPrimo n) es el mayor divisor primo de n. Por ejemplo,
mayorDivisorPrimo 13195 == 29 mayorDivisorPrimo 152416333181401 == 12345701 |
Nota: Este ejercicio está basado en el problema 3 del Proyecto Euler
import Data.Numbers.Primes (primeFactors) -- 1ª solución (sin librerías auxiliares) -- ======================================= mayorDivisorPrimo :: Integer -> Integer mayorDivisorPrimo = last . divisoresPrimos -- (divisoresPrimos n) es la lista de los divisores primos de n. Por -- ejemplo, -- divisoresPrimos 13195 == [5,7,13,29] divisoresPrimos :: Integer -> [Integer] divisoresPrimos 0 = [] divisoresPrimos 1 = [] divisoresPrimos n = m : divisoresPrimos (n `div` m) where m = menorDivisorPrimo n -- (menorDivisorPrimo n) es el menor divisor primo de n. Por ejemplo, -- menorDivisorPrimo 24 == 2 -- menorDivisorPrimo 25 == 5 -- menorDivisorPrimo 29 == 29 menorDivisorPrimo :: Integer -> Integer menorDivisorPrimo x = head [y | y <- 2 : [3,5..(ceiling . sqrt . fromIntegral) x] ++ [x] , x `mod` y == 0] -- 2ª solución (con la librería Data.Numbers.Primes) -- ================================================= mayorDivisorPrimo2 :: Integer -> Integer mayorDivisorPrimo2 = last . primeFactors -- Comparación de eficiencia -- ========================= -- λ> mayorDivisorPrimo 152416333181401 -- 12345701 -- (1.96 secs, 1,630,201,856 bytes) -- λ> mayorDivisorPrimo2 152416333181401 -- 12345701 -- (2.01 secs, 5,445,284,432 bytes) |
“Un programa de ordenador es una demostración.” ~ Igor Rivin
En la librería Data.Tree se definen los tipos de árboles y bosques como sigue
data Tree a = Node a (Forest a) type Forest a = [Tree a] |
Se pueden definir árboles. Por ejemplo,
ej = Node 3 [Node 5 [Node 9 []], Node 7 []] |
Y se pueden dibujar con la función drawTree. Por ejemplo,
λ> putStrLn (drawTree (fmap show ej)) 3 | +- 5 | | | `- 9 | `- 7 |
Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u.v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.
El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es
6 / \ 5 3 | | 4 2 / \ | 3 2 1 | | 2 1 | 1 |
Definir las siguientes funciones
mayoresDivisores :: Int -> [Int] arbol :: Int -> Tree Int caminos :: Int -> [[Int]] caminosMinimales :: Int -> [[Int]] |
tales que
+ (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,
mayoresDivisores 24 == [12,8,6] mayoresDivisores 16 == [8,4] mayoresDivisores 10 == [5] mayoresDivisores 17 == [] |
λ> putStrLn (drawTree (fmap show (arbol 6))) 6 | +- 5 | | | `- 4 | | | +- 3 | | | | | `- 2 | | | | | `- 1 | | | `- 2 | | | `- 1 | `- 3 | `- 2 | `- 1 |
λ> caminos 6 [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]] |
λ> caminosMinimales 6 [[6,3,2,1]] λ> caminosMinimales 17 [[17,16,4,2,1]] λ> caminosMinimales 50 [[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]] |
import Data.Tree import Test.QuickCheck mayoresDivisores :: Int -> [Int] mayoresDivisores x = [max u v | u <- [2..floor (sqrt (fromIntegral x))] , x `mod` u == 0 , let v = x `div` u] arbol :: Int -> Tree Int arbol 1 = Node 1 [] arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x]) caminos :: Int -> [[Int]] caminos = caminosArbol . arbol -- λ> caminosArbol (arbol 6) -- [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]] caminosArbol :: Tree a -> [[a]] caminosArbol (Node x []) = [[x]] caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as] caminosBosque :: Forest a -> [[a]] caminosBosque = concatMap caminosArbol caminosMinimales :: Int -> [[Int]] caminosMinimales x = [ys | ys <- yss, length ys == m] where yss = caminos x m = minimum (map length yss) |
Tras el vivir y el soñar,
está lo que más importa:
despertar.Antonio Machado