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
1 2 3 |
esPerfecto :: Integer -> Bool esCojonudo :: Integer -> Bool equivalencia_CojonudosPerfectos :: Integer -> Bool |
tales que
- (esPerfecto x) se verifica si x es perfecto. Por ejemplo,
1 2 |
esPerfecto 28 == True esPerfecto 30 == False |
- (esCojonudo x) se verifica si x es cojonudo. Por ejemplo,
1 2 3 |
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,
1 |
equivalenciaCojonudosPerfectos 3000 == True |
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 |
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]] |