Divisores propios maximales
Se dice que a es un divisor propio maximal de un número b si a es un divisor de b distinto de b y no existe ningún número c tal que a < c < b, a es un divisor de c y c es un divisor de b. Por ejemplo, 15 es un divisor propio maximal de 30, pero 5 no lo es.
Definir las funciones
1 2 |
divisoresPropiosMaximales :: Integer -> [Integer] nDivisoresPropiosMaximales :: Integer -> Integer |
tales que
- (divisoresPropiosMaximales x) es la lista de los divisores propios maximales de x. Por ejemplo,
1 2 3 4 |
divisoresPropiosMaximales 30 == [6,10,15] divisoresPropiosMaximales 420 == [60,84,140,210] divisoresPropiosMaximales 7 == [1] length (divisoresPropiosMaximales (product [1..3*10^4])) == 3245 |
- (nDivisoresPropiosMaximales x) es el número de divisores propios maximales de x. Por ejemplo,
1 2 3 4 |
nDivisoresPropiosMaximales 30 == 3 nDivisoresPropiosMaximales 420 == 4 nDivisoresPropiosMaximales 7 == 1 nDivisoresPropiosMaximales (product [1..3*10^4]) == 3245 |
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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
import Data.Numbers.Primes (primeFactors) import Data.List (genericLength, group, nub) import Test.QuickCheck -- 1ª definición de divisoresPropiosMaximales -- ========================================== divisoresPropiosMaximales :: Integer -> [Integer] divisoresPropiosMaximales x = [y | y <- divisoresPropios x , null [z | z <- divisoresPropios x , y < z , z `mod` y == 0]] -- (divisoresPropios x) es la lista de los divisores propios de x; es -- decir, de los divisores de x distintos de x. Por ejemplo, -- divisoresPropios 30 == [1,2,3,5,6,10,15] divisoresPropios :: Integer -> [Integer] divisoresPropios x = [y | y <- [1..x-1] , x `mod` y == 0] -- 2ª definición de divisoresPropiosMaximales -- ========================================== divisoresPropiosMaximales2 :: Integer -> [Integer] divisoresPropiosMaximales2 x = reverse [x `div` y | y <- nub (primeFactors x)] -- Equivalencia de las definiciones de divisoresPropiosMaximales -- ============================================================= -- La propiedad es prop_divisoresPropiosMaximales_equiv :: (Positive Integer) -> Bool prop_divisoresPropiosMaximales_equiv (Positive x) = divisoresPropiosMaximales x == divisoresPropiosMaximales2 x -- La comprobación es -- λ> quickCheck prop_divisoresPropiosMaximales_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia de divisoresPropiosMaximales -- ====================================================== -- λ> length (divisoresPropiosMaximales (product [1..10])) -- 4 -- (13.33 secs, 7,037,241,776 bytes) -- λ> length (divisoresPropiosMaximales2 (product [1..10])) -- 4 -- (0.00 secs, 135,848 bytes) -- 1ª definición de nDivisoresPropiosMaximales -- =========================================== nDivisoresPropiosMaximales :: Integer -> Integer nDivisoresPropiosMaximales = genericLength . divisoresPropiosMaximales -- 2ª definición de nDivisoresPropiosMaximales -- =========================================== nDivisoresPropiosMaximales2 :: Integer -> Integer nDivisoresPropiosMaximales2 = genericLength . divisoresPropiosMaximales2 -- 3ª definición de nDivisoresPropiosMaximales -- =========================================== nDivisoresPropiosMaximales3 :: Integer -> Integer nDivisoresPropiosMaximales3 = genericLength . group . primeFactors -- Equivalencia de las definiciones de nDivisoresPropiosMaximales -- ============================================================== -- La propiedad es prop_nDivisoresPropiosMaximales_equiv :: (Positive Integer) -> Bool prop_nDivisoresPropiosMaximales_equiv (Positive x) = nDivisoresPropiosMaximales x == nDivisoresPropiosMaximales3 x && nDivisoresPropiosMaximales2 x == nDivisoresPropiosMaximales3 x -- La comprobación es -- λ> quickCheck prop_nDivisoresPropiosMaximales_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia de nDivisoresPropiosMaximales -- ======================================================= -- λ> nDivisoresPropiosMaximales2 (product [1..10]) -- 4 -- (13.33 secs, 7,037,242,536 bytes) -- λ> nDivisoresPropiosMaximales2 (product [1..10]) -- 4 -- (0.00 secs, 135,640 bytes) -- λ> nDivisoresPropiosMaximales3 (product [1..10]) -- 4 -- (0.00 secs, 135,232 bytes) -- -- λ> nDivisoresPropiosMaximales2 (product [1..3*10^4]) -- 3245 -- (3.12 secs, 4,636,274,040 bytes) -- λ> nDivisoresPropiosMaximales3 (product [1..3*10^4]) -- 3245 -- (3.06 secs, 4,649,295,056 bytes) |
Pensamiento
«Moneda que está en la mano
quizá se deba guardar;
la monedita del alma
se pierde si no se da.»Antonio Machado