Menu Close

Suma de las sumas de los cuadrados de los divisores

 

La suma de las sumas de los cuadrados de los divisores de los 6 primeros números enteros positivos es

     1² + (1²+2²) + (1²+3²) + (1²+2²+4²) + (1²+5²) + (1²+2²+3²+6²)
   = 1  + 5       + 10      + 21         + 26      + 50
   = 113

Definir la función

   sumaSumasCuadradosDivisores :: Integer -> Integer

tal que (sumaSumasCuadradosDivisores n) es la suma de las sumas de los cuadrados de los divisores de los n primeros números enteros positivos. Por ejemplo,

   sumaSumasCuadradosDivisores 6       ==  113
   sumaSumasCuadradosDivisores (10^6)  ==  400686363385965077

Soluciones

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)
Medio

5 soluciones de “Suma de las sumas de los cuadrados de los divisores

  1. pabhueacu
    sumaSumasCuadradosDivisores :: Integer -> Integer
    sumaSumasCuadradosDivisores n = sum $ zipWith (*) ((map (^2)  xs)) (zipWith div (repeat n) xs) 
                    where xs = takeWhile (<= n) [1..]
  2. albcarcas1
     
    sumaSumasCuadradosDivisores :: Integer -> Integer
    sumaSumasCuadradosDivisores n = sum[(div n x)*(x^2) | x <- [1..n]]
  3. migtruale
    import Data.List
    --Primera definicion
    sumaSumasCuadradosDivisores :: Integer -> Integer
    sumaSumasCuadradosDivisores x = sum (map (^2) (listadeDivisores [1..x]))
     
    --divisores x es la lista de divisores de un numero x
     
    divisores:: Integer -> [Integer]
    divisores x = [y | y <- [1..x], x `mod`y == 0]
     
    --listadeDivisores xs es la lista de los  divisores de cada uno de los elementos
    --de la lista xs
     
    listadeDivisores :: [Integer] -> [Integer]
    listadeDivisores  [] = []
    listadeDivisores (x:xs) = divisores x++listadeDivisores xs
     
    --Segunda definicion 
    sumaSumasCuadradosDivisores2:: Integer -> Integer
    sumaSumasCuadradosDivisores2 x = sum (zipWith (*) (map (x `div`) xs) (map (^2) xs))
                                     where xs = [1..x]
  4. carbremor

    En Maxima:

    /* divisoresCuadrados(n) devuelve la suma de los divisores de n elevados al
       cuadrado. Por ejemplo,
       divisoresCuadrados(6);
        50
    */
     
    divisoresCuadrados(n) :=
       divsum(n,2)$
     
    sumaSumasCuadradosDivisores(n) :=
        sum(divisoresCuadrados(k), k, 1, n)$
        memoize(sumaSumasCuadradosDivisores);
     
    /* La función memoize se aplica a funciones que siempre dan los mismos
       resultados, pues guarda los valores así la segunda vez que se ejecuta es
       instantánea  aquellos resultados ya calculados
    */
     
    /* Ejemplos:
     
    (%i1) showtime : true$
    Evaluation took 0.0000 seconds (0.0000 elapsed)
    (%i2) sumaSumasCuadradosDivisores(6);
    Evaluation took 0.0600 seconds (0.0600 elapsed)
    (%o2)                                 113
    (%i3) sumaSumasCuadradosDivisores(10^6);
    Evaluation took 5.0600 seconds (6.4900 elapsed)
    (%o3)                         400686363385965077
     
    */
  5. anadebla
     
    aplica n = sum [x^2 | x <- (divisores n)]
     
    sumaSumasCuadradosDivisores :: Integer -> Integer
    sumaSumasCuadradosDivisores n = sum [fromIntegral (aplica (fromIntegral x)) | x <- [1..n]]
     
    divisores:: Int -> [Int]
    divisores n = [m | m <- [1..n-1], mod n m == 0] ++ [n]

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.