Definir la funci\u00f3n<\/p>\n
\n sumaDivisores :: Integer -> Integer\n<\/pre>\ntal que sumaDivisores x<\/code> es la suma de los divisores de x<\/code>. Por ejemplo,<\/p>\n\n sumaDivisores 12 == 28\n sumaDivisores 25 == 31\n sumaDivisores (product [1..25]) == 93383273455325195473152000\n length (show (sumaDivisores (product [1..30000]))) == 121289\n maximum (map sumaDivisores [1..2*10^6]) == 8851392\n<\/pre>\nSoluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n<\/a>
\nSoluciones en Haskell<\/b><\/p>\n\nimport Data.List (foldl', genericLength, group, inits)\nimport Data.Set (toList)\nimport Data.Numbers.Primes (primeFactors)\nimport Math.NumberTheory.ArithmeticFunctions (divisors, sigma)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsumaDivisores1 :: Integer -> Integer\nsumaDivisores1 n = sum (divisores1 n)\n\n-- (divisores x) es la lista de los divisores de x. Por ejemplo,\n-- divisores 60 == [1,5,3,15,2,10,6,30,4,20,12,60]\ndivisores1 :: Integer -> [Integer]\ndivisores1 n = [x | x <- [1..n], n `rem` x == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Sustituyendo la definici\u00f3n de divisores de la soluci\u00f3n anterior por\n-- cada una de las del ejercicio [Divisores de un n\u00famero](https:\/\/bit.ly\/3S1HYwi)\n-- Se obtiene una nueva definici\u00f3n de sumaDivisores. La usada en la\n-- definici\u00f3n anterior es la menos eficiente y la que se usa en la\n-- siguiente definici\u00f3n es la m\u00e1s eficiente.\n\nsumaDivisores2 :: Integer -> Integer\nsumaDivisores2 = sum . divisores2\n\ndivisores2 :: Integer -> [Integer]\ndivisores2 = toList . divisors\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\n-- La soluci\u00f3n anterior se puede simplificar\n\nsumaDivisores3 :: Integer -> Integer\nsumaDivisores3 = sum . divisors\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nsumaDivisores4 :: Integer -> Integer\nsumaDivisores4 = foldl' (+) 0 . divisores2\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nsumaDivisores5 :: Integer -> Integer\nsumaDivisores5 n = aux [1..n]\n where aux [] = 0\n aux (x:xs) | n `rem` x == 0 = x + aux xs\n | otherwise = aux xs\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nsumaDivisores6 :: Integer -> Integer\nsumaDivisores6 = sum\n . map (product . concat)\n . mapM inits\n . group\n . primeFactors\n\n-- 7\u00aa soluci\u00f3n\n-- ===========\n\n-- Si la descomposici\u00f3n de x en factores primos es\n-- x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)\n-- entonces la suma de los divisores de x es\n-- p(1)^(e(1)+1) - 1 p(2)^(e(2)+1) - 1 p(n)^(e(2)+1) - 1\n-- ------------------- . ------------------- ... -------------------\n-- p(1)-1 p(2)-1 p(n)-1\n-- Ver la demostraci\u00f3n en http:\/\/bit.ly\/2zUXZPc\n\nsumaDivisores7 :: Integer -> Integer\nsumaDivisores7 x =\n product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x]\n\n-- (factorizacion x) es la lista de las bases y exponentes de la\n-- descomposici\u00f3n prima de x. Por ejemplo,\n-- factorizacion 600 == [(2,3),(3,1),(5,2)]\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion = map primeroYlongitud . group . primeFactors\n\n-- (primeroYlongitud xs) es el par formado por el primer elemento de xs\n-- y la longitud de xs. Por ejemplo,\n-- primeroYlongitud [3,2,5,7] == (3,4)\nprimeroYlongitud :: [a] -> (a,Integer)\nprimeroYlongitud (x:xs) =\n (x, 1 + genericLength xs)\n\n-- 8\u00aa soluci\u00f3n\n-- ===========\n\nsumaDivisores8 :: Integer -> Integer\nsumaDivisores8 = sigma 1\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_sumaDivisores :: Positive Integer -> Bool\nprop_sumaDivisores (Positive x) =\n all (== sumaDivisores1 x)\n [ sumaDivisores2 x\n , sumaDivisores3 x\n , sumaDivisores4 x\n , sumaDivisores5 x\n , sumaDivisores6 x\n , sumaDivisores7 x\n , sumaDivisores8 x\n ]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_sumaDivisores\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> sumaDivisores1 5336100\n-- 21386001\n-- (2.25 secs, 1,067,805,248 bytes)\n-- \u03bb> sumaDivisores2 5336100\n-- 21386001\n-- (0.01 secs, 659,112 bytes)\n-- \u03bb> sumaDivisores3 5336100\n-- 21386001\n-- (0.01 secs, 635,688 bytes)\n-- \u03bb> sumaDivisores4 5336100\n-- 21386001\n-- (0.01 secs, 648,992 bytes)\n-- \u03bb> sumaDivisores5 5336100\n-- 21386001\n-- (2.44 secs, 1,323,924,176 bytes)\n-- \u03bb> sumaDivisores6 5336100\n-- 21386001\n-- (0.01 secs, 832,104 bytes)\n-- \u03bb> sumaDivisores7 5336100\n-- 21386001\n-- (0.01 secs, 571,040 bytes)\n-- \u03bb> sumaDivisores8 5336100\n-- 21386001\n-- (0.00 secs, 558,296 bytes)\n--\n-- \u03bb> sumaDivisores2 251888923423315469521109880000000\n-- 1471072204661054993275791673480320\n-- (2.30 secs, 1,130,862,080 bytes)\n-- \u03bb> sumaDivisores3 251888923423315469521109880000000\n-- 1471072204661054993275791673480320\n-- (1.83 secs, 896,386,232 bytes)\n-- \u03bb> sumaDivisores4 251888923423315469521109880000000\n-- 1471072204661054993275791673480320\n-- (1.52 secs, 997,992,328 bytes)\n-- \u03bb> sumaDivisores6 251888923423315469521109880000000\n-- 1471072204661054993275791673480320\n-- (2.35 secs, 5,719,848,600 bytes)\n-- \u03bb> sumaDivisores7 251888923423315469521109880000000\n-- 1471072204661054993275791673480320\n-- (0.00 secs, 628,136 bytes)\n-- \u03bb> sumaDivisores8 251888923423315469521109880000000\n-- 1471072204661054993275791673480320\n-- (0.00 secs, 591,352 bytes)\n--\n-- \u03bb> length (show (sumaDivisores7 (product [1..30000])))\n-- 121289\n-- (2.76 secs, 4,864,576,304 bytes)\n-- \u03bb> length (show (sumaDivisores8 (product [1..30000])))\n-- 121289\n-- (1.65 secs, 3,173,319,312 bytes)\n<\/pre>\nEl c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n