Definir la funci\u00f3n<\/p>\n
\n sumaDivisoresHasta :: Integer -> [(Integer,Integer)]\n<\/pre>\ntal que (sumaDivisoresHasta n)<\/code> es la lista de los pares (a,b)<\/code> tales que a<\/code> es un n\u00famero entre 1 y n<\/code> y b<\/code> es la suma de los divisores propios de a<\/code>. Por ejemplo,<\/p>\n\n \u03bb> sumaDivisoresHasta 12\n [(1,0),(2,1),(3,1),(4,3),(5,1),(6,6),(7,1),(8,7),(9,4),(10,8),(11,1),(12,16)]\n \u03bb> last (sumaDivisoresHasta2 (10^7))\n (10000000,14902280)\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Array (accumArray, assocs)\nimport Data.List (genericLength, group)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsumaDivisoresHasta1 :: Integer -> [(Integer,Integer)]\nsumaDivisoresHasta1 n = [(x, sum (divisores x)) | x <- [1..n]]\n\ndivisores :: Integer -> [Integer]\ndivisores n = [x | x <- [1..n `div` 2], n `mod` x == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsumaDivisoresHasta2 :: Integer -> [(Integer,Integer)]\nsumaDivisoresHasta2 n = [(x, sumaDivisores x) | x <- [1..n]]\n\nsumaDivisores :: Integer -> Integer\nsumaDivisores x =\n product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x] - 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-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsumaDivisoresHasta3 :: Integer -> [(Integer,Integer)]\nsumaDivisoresHasta3 n = assocs (accumArray (+) 0 (1,n) (divisoresHasta n))\n\n-- (divisoresHasta n) es la lista de los pares (a,b) tales que a es\n-- un n\u00famero entre 2 y n y b es un divisor propio e x. Por ejemplo,\n-- \u03bb> divisoresHasta 6\n-- [(2,1),(3,1),(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)]\n-- \u03bb> divisoresHasta 8\n-- [(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(4,2),(6,2),(8,2),(6,3),(8,4)]\ndivisoresHasta :: Integer -> [(Integer,Integer)]\ndivisoresHasta n = [(a,b) | b <- [1..n `div` 2], a <- [b*2, b*3..n]]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_sumaDivisoresHasta :: Positive Integer -> Bool\nprop_sumaDivisoresHasta (Positive n) =\n all (== sumaDivisoresHasta1 n)\n [ sumaDivisoresHasta2 n\n , sumaDivisoresHasta3 n\n ]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_sumaDivisoresHasta\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> last (sumaDivisoresHasta1 (10^6))\n-- (1000000,1480437)\n-- (0.47 secs, 308,542,392 bytes)\n-- \u03bb> last (sumaDivisoresHasta2 (10^6))\n-- (1000000,2480437)\n-- (0.26 secs, 208,548,944 bytes)\n-- \u03bb> last (sumaDivisoresHasta3 (10^6))\n-- (1000000,1480437)\n-- (6.65 secs, 3,249,831,856 bytes)\n--\n-- \u03bb> last (sumaDivisoresHasta1 (5*10^6))\n-- (5000000,7402312)\n-- (2.27 secs, 1,540,543,352 bytes)\n-- \u03bb> last (sumaDivisoresHasta2 (5*10^6))\n-- (5000000,12402312)\n-- (1.19 secs, 1,040,549,800 bytes)\n<\/pre>\n