Números perfectos y cojonudos
Un número perfecto es un número entero positivo que es igual a la suma de sus divisores propios. Por ejemplo, el 28 es perfecto porque sus divisores propios son 1, 2, 4, 7 y 14 y 1+2+4+7+14 = 28.
Un entero positivo x es un número cojonudo si existe un n tal que n > 0, x = 2^n·(2^(n+1)-1) y 2^(n+1)-1 es primo. Por ejemplo, el 28 es cojonudo ya que para n = 2 se verifica que 2 > 0, 28 = 2^2·(2^3-1) y 2^3-1 = 7 es primo.
Definir la funciones
esPerfecto :: Integer -> Bool esCojonudo :: Integer -> Bool equivalencia_CojonudosPerfectos :: Integer -> Bool
tales que
- (esPerfecto x) se verifica si x es perfecto. Por ejemplo,
esPerfecto 28 == True esPerfecto 30 == False
- (esCojonudo x) se verifica si x es cojonudo. Por ejemplo,
esCojonudo 28 == True esCojonudo 30 == False esCojonudo 2305843008139952128 == True
- (equivalenciaCojonudosPerfectos n) se verifica si para todos los números x menores o iguales que n se tiene que x es perfecto si, y sólo si, x es cojonudo. Por ejemplo,
equivalenciaCojonudosPerfectos 3000 == True
Soluciones
import Data.Numbers.Primes import Data.List -- 1ª definición de esPerfecto -- =========================== esPerfecto1 :: Integer -> Bool esPerfecto1 x = sum (divisoresPropios1 x) == x divisoresPropios1 :: Integer -> [Integer] divisoresPropios1 x = [y | y <- [1..x-1] , x `mod` y == 0] -- 2ª definición de esPerfecto -- =========================== esPerfecto2 :: Integer -> Bool esPerfecto2 n = sum (divisoresPropios2 n) == n divisoresPropios2 :: Integer -> [Integer] divisoresPropios2 n = (delete n . nub . map product . subsequences) (primeFactors n) -- Comparación de eficiencia -- ========================= -- λ> esPerfecto1 33550336 -- True -- (48.70 secs, 6,976,432,536 bytes) -- λ> esPerfecto2 33550336 -- True -- (0.01 secs, 0 bytes) -- -- λ> [x | x <- [1..10^4], esPerfecto1 x] -- [6,28,496,8128] -- (72.88 secs, 10,411,693,760 bytes) -- λ> [x | x <- [1..10^4], esPerfecto2 x] -- [6,28,496,8128] -- (0.69 secs, 311,388,248 bytes) -- 1ª definición de esCojonudo -- =========================== esCojonudo1 :: Integer -> Bool esCojonudo1 x = pertenece x cojonudos cojonudos :: [Integer] cojonudos = [2^n*p | n <- [1..] , let p = 2^(n+1) - 1 , isPrime p] pertenece :: Integer -> [Integer] -> Bool pertenece x ys = head (dropWhile (<x) ys) == x -- 2ª definición de esCojonudo -- =========================== esCojonudo2 :: Integer -> Bool esCojonudo2 n | length p /= 1 = False | otherwise = head p == 2 * product d -1 where (d,p) = partition (==2) (primeFactors n) -- Comparación de eficiencia -- ========================= -- λ> length [x | x <- [1..10^5], esCojonudo1 x] -- 4 -- (0.37 secs, 23,492,384 bytes) -- λ> length [x | x <- [1..10^5], esCojonudo2 x] -- 4 -- (7.46 secs, 4,245,266,408 bytes) -- Comprobación de equivalencia -- ============================ equivalencia_CojonudosPerfectos :: Integer -> Bool equivalencia_CojonudosPerfectos n = and [esCojonudo1 x == esPerfecto2 x | x <- [1..n]]