Menu Close

Suma de divisores

 

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 sumaDivisores2 [1..10^5])  ==  403200

Soluciones

import Data.List (genericLength, group, inits, nub, sort)
import Data.Numbers.Primes (primeFactors)
 
-- 1ª solución
-- ===========
 
sumaDivisores :: Integer -> Integer
sumaDivisores = sum . divisores
 
-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 60  ==  [1,2,3,4,5,6,10,12,15,20,30,60]
divisores :: Integer -> [Integer]
divisores = sort
            . map (product . concat)
            . productoCartesiano
            . map inits
            . group
            . primeFactors
 
-- (productoCartesiano xss) es el producto cartesiano de los conjuntos
-- xss. Por ejemplo, 
--    λ> producto [[1,3],[2,5],[6,4]]
--    [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]
productoCartesiano :: [[a]] -> [[a]]
productoCartesiano []       = [[]]
productoCartesiano (xs:xss) =
  [x:ys | x <- xs, ys <- productoCartesiano xss]
 
-- 2ª solución
-- ===========
 
sumaDivisores2 :: Integer -> Integer
sumaDivisores2 = sum
               . map (product . concat)
               . sequence
               . map inits
               . group
               . primeFactors
 
-- 3ª solución
-- ===========
 
-- Si la descomposición de x en factores primos es
--    x = p(1)^e(1) . p(2)^e(2) . .... . p(n)^e(n)
-- entonces la suma de los divisores de x es
--    p(1)^(e(1)+1) - 1     p(2)^(e(2)+1) - 1       p(n)^(e(2)+1) - 1  
--   ------------------- . ------------------- ... ------------------- 
--        p(1)-1                p(2)-1                  p(n)-1         
-- Ver la demostración en http://bit.ly/2zUXZPc
 
sumaDivisores3 :: Integer -> Integer
sumaDivisores3 x =
  product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x]
 
-- (factorizacion x) ses la lista de las bases y exponentes de la
-- descomposición prima de x. Por ejemplo, 
--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion = map primeroYlongitud . group . primeFactors
 
-- (primeroYlongitud xs) es el par formado por el primer elemento de xs
-- y la longitud de xs. Por ejemplo,
--    primeroYlongitud [3,2,5,7] == (3,4)
primeroYlongitud :: [a] -> (a,Integer)
primeroYlongitud (x:xs) =
  (x, 1 + genericLength xs)
 
-- Comparación de eficiencia de sumaDivisores
-- ==========================================
 
--   λ> sumaDivisores 251888923423315469521109880000000
--   1471072204661054993275791673480320
--   (10.63 secs, 10,614,618,080 bytes)
--   λ> sumaDivisores2 251888923423315469521109880000000
--   1471072204661054993275791673480320
--   (2.51 secs, 5,719,399,056 bytes)
--   λ> sumaDivisores3 251888923423315469521109880000000
--   1471072204661054993275791673480320
--   (0.01 secs, 177,480 bytes)

Pensamiento

“Programación, en sentido amplio, es resolución de problemas.” ~ Paul Hudak

Medio

2 soluciones de “Suma de divisores

  1. juaromsan5
    import Data.Numbers.Primes
    import Data.List
     
    sumaDivisores :: Integer -> Integer
    sumaDivisores p =
      product [(x^(y+1) - 1) `div` (x-1) | (x,y) <- factorizacion p]
     
    factorizacion :: Integer -> [(Integer,Integer)]
    factorizacion x = zip (factoresprimos x) (exponentesOrdenados x)
     
    factoresprimos :: Integer -> [Integer]
    factoresprimos = nub . primeFactors
     
    exponentesOrdenados :: Integer -> [Integer]
    exponentesOrdenados = map genericLength . group . primeFactors
  2. antgongar
    import Data.List (inits, group)
    import Data.Numbers.Primes (primeFactors)
     
    sumaDivisores :: Integer -> Integer
    sumaDivisores = sum
                  . map (product . concat)
                  . sequence
                  . map inits
                  . group
                  . primeFactors

Los comentarios están cerrados.