import Data.List (genericIndex)
-- 1ª solución
-- ===========
sumaSumasCuadradosDivisores :: Integer -> Integer
sumaSumasCuadradosDivisores n =
sum [sumaCuadradosDivisores k | k <- [1..n]]
-- (sumaCuadradosDivisores n) es la suma de los cuadrados de los
-- divisores de n. Por ejemplo,
-- sumaCuadradosDivisores 6 == 50
sumaCuadradosDivisores :: Integer -> Integer
sumaCuadradosDivisores n = sum (map (^2) (divisores n))
-- (divisores n) es la lista de los divisores de n. Por ejemplo,
-- divisores 6 == [1,6,2,3]
divisores :: Integer -> [Integer]
divisores 1 = [1]
divisores n = 1 : n : [x | x <- [2..n `div` 2], n `mod` x == 0]
-- 2ª solución
-- ===========
sumaSumasCuadradosDivisores2 :: Integer -> Integer
sumaSumasCuadradosDivisores2 n =
sumasSumasCuadradosDivisores `genericIndex` (n-1)
-- sumasSumasCuadradosDivisores es la sucesión cuyo n-ésimo término es
-- la suma de las sumas de los cuadrados de los divisores de n. Por
-- ejemplo,
-- take 6 sumasSumasCuadradosDivisores == [1,6,16,37,63,113]
sumasSumasCuadradosDivisores :: [Integer]
sumasSumasCuadradosDivisores = 1 : sig 1 2
where sig m n = y : sig y (n+1)
where y = m + sumaCuadradosDivisores n
-- 3ª solución
-- ===========
sumaSumasCuadradosDivisores3 :: Integer -> Integer
sumaSumasCuadradosDivisores3 n =
last (sumasSumasCuadradosDivisores3 n)
-- (sumasSumasCuadradosDivisores3 n) es la sucesión cuyo k-ésimo término
-- es la suma de las sumas de los cuadrados de los divisores de k, para
-- k entre 0 y n. Por ejemplo,
-- sumasSumasCuadradosDivisores3 6 == [0,6,18,36,52,77,113]
sumasSumasCuadradosDivisores3 :: Integer -> [Integer]
sumasSumasCuadradosDivisores3 n = scanl f 0 [1..n]
where f x k = x + k^2 * (n `div` k)
-- 4ª solución
-- ===========
sumaSumasCuadradosDivisores4 :: Integer -> Integer
sumaSumasCuadradosDivisores4 n =
last (sumasSumasCuadradosDivisores4 n)
-- (sumasSumasCuadradosDivisores4 n) es la sucesión cuyo k-ésimo término
-- es la suma de las sumas de los cuadrados de los divisores de k, para
-- k entre 0 y n. Por ejemplo,
-- sumasSumasCuadradosDivisores4 6 == [0,6,18,36,52,77,113]
sumasSumasCuadradosDivisores4 :: Integer -> [Integer]
sumasSumasCuadradosDivisores4 n = scanl1 f [0,1..n]
where f x k = x + k^2 * (n `div` k)
-- 5ª solución
-- ===========
sumaSumasCuadradosDivisores5 :: Integer -> Integer
sumaSumasCuadradosDivisores5 n =
last (sumasSumasCuadradosDivisores5 n)
-- (sumasSumasCuadradosDivisores5 n) es la sucesión cuyo k-ésimo término
-- es la suma de las sumas de los cuadrados de los divisores de k, para
-- k entre 0 y n. Por ejemplo,
-- sumasSumasCuadradosDivisores5 6 == [0,6,18,36,52,77,113]
sumasSumasCuadradosDivisores5 :: Integer -> [Integer]
sumasSumasCuadradosDivisores5 n = scanl1 f [0,1..n]
where f x k = x + k * (n - (n `mod` k))
-- 6ª solución
-- ===========
-- Cada elemento k de [1..n], al cuadrado, aparece tantas veces como la
-- parte entera de n/k; luego,
-- sumaSumasCuadradosDivisores n =
-- 1^2*n + 2^2*(n `div` 2) + 3^2*(n `div` 3) + ... + n^2*1
sumaSumasCuadradosDivisores6 :: Integer -> Integer
sumaSumasCuadradosDivisores6 n = sum (zipWith (*) ds vs)
where ds = map (^2) [1..n]
vs = [n `div` k | k <- [1..n]]
-- Comparación de eficiencia:
-- =========================
-- λ> sumaSumasCuadradosDivisores (3*10^3)
-- 10825397502
-- (3.29 secs, 468,721,192 bytes)
-- λ> sumaSumasCuadradosDivisores2 (3*10^3)
-- 10825397502
-- (3.25 secs, 469,462,600 bytes)
-- λ> sumaSumasCuadradosDivisores3 (3*10^3)
-- 10825397502
-- (0.03 secs, 2,788,752 bytes)
-- λ> sumaSumasCuadradosDivisores4 (3*10^3)
-- 10825397502
-- (0.03 secs, 2,813,304 bytes)
-- λ> sumaSumasCuadradosDivisores5 (3*10^3)
-- 10825397502
-- (0.03 secs, 1,467,056 bytes)
-- λ> sumaSumasCuadradosDivisores6 (3*10^3)
-- 10825397502
-- (0.03 secs, 3,291,664 bytes)
--
-- λ> sumaSumasCuadradosDivisores3 (5*10^5)
-- 50085873311988831
-- (2.34 secs, 440,961,640 bytes)
-- λ> sumaSumasCuadradosDivisores4 (5*10^5)
-- 50085873311988831
-- (2.29 secs, 444,962,904 bytes)
-- λ> sumaSumasCuadradosDivisores5 (5*10^5)
-- 50085873311988831
-- (1.23 secs, 220,960,152 bytes)
-- λ> sumaSumasCuadradosDivisores6 (5*10^5)
-- 50085873311988831
-- (2.76 secs, 524,962,464 bytes)