Sumas de divisores propios
Definir la función
|
1 |
sumaDivisoresHasta :: Integer -> [(Integer,Integer)] |
tal que (sumaDivisoresHasta n) es la lista de los pares (a,b) tales que a es un número entre 1 y n y b es la suma de los divisores propios de a. Por ejemplo,
|
1 2 3 4 |
λ> sumaDivisoresHasta 12 [(1,0),(2,1),(3,1),(4,3),(5,1),(6,6),(7,1),(8,7),(9,4),(10,8),(11,1),(12,16)] λ> last (sumaDivisoresHasta2 (10^7)) (10000000,14902280) |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
import Data.Array (accumArray, assocs) import Data.List (genericLength, group) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck -- 1ª solución -- =========== sumaDivisoresHasta1 :: Integer -> [(Integer,Integer)] sumaDivisoresHasta1 n = [(x, sum (divisores x)) | x <- [1..n]] divisores :: Integer -> [Integer] divisores n = [x | x <- [1..n `div` 2], n `mod` x == 0] -- 2ª solución -- =========== sumaDivisoresHasta2 :: Integer -> [(Integer,Integer)] sumaDivisoresHasta2 n = [(x, sumaDivisores x) | x <- [1..n]] sumaDivisores :: Integer -> Integer sumaDivisores x = product [(p^(e+1)-1) `div` (p-1) | (p,e) <- factorizacion x] - x -- (factorizacion x) es 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) -- 3ª solución -- =========== sumaDivisoresHasta3 :: Integer -> [(Integer,Integer)] sumaDivisoresHasta3 n = assocs (accumArray (+) 0 (1,n) (divisoresHasta n)) -- (divisoresHasta n) es la lista de los pares (a,b) tales que a es -- un número entre 2 y n y b es un divisor propio e x. Por ejemplo, -- λ> divisoresHasta 6 -- [(2,1),(3,1),(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)] -- λ> divisoresHasta 8 -- [(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(4,2),(6,2),(8,2),(6,3),(8,4)] divisoresHasta :: Integer -> [(Integer,Integer)] divisoresHasta n = [(a,b) | b <- [1..n `div` 2], a <- [b*2, b*3..n]] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_sumaDivisoresHasta :: Positive Integer -> Bool prop_sumaDivisoresHasta (Positive n) = all (== sumaDivisoresHasta1 n) [ sumaDivisoresHasta2 n , sumaDivisoresHasta3 n ] -- La comprobación es -- λ> quickCheck prop_sumaDivisoresHasta -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (sumaDivisoresHasta1 (10^6)) -- (1000000,1480437) -- (0.47 secs, 308,542,392 bytes) -- λ> last (sumaDivisoresHasta2 (10^6)) -- (1000000,2480437) -- (0.26 secs, 208,548,944 bytes) -- λ> last (sumaDivisoresHasta3 (10^6)) -- (1000000,1480437) -- (6.65 secs, 3,249,831,856 bytes) -- -- λ> last (sumaDivisoresHasta1 (5*10^6)) -- (5000000,7402312) -- (2.27 secs, 1,540,543,352 bytes) -- λ> last (sumaDivisoresHasta2 (5*10^6)) -- (5000000,12402312) -- (1.19 secs, 1,040,549,800 bytes) |
El código se encuentra en GitHub.