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]] |
En
equivalenciaCojonudosPerfectos
estás comprobando que todo número perfecto es número cojonudo, pero no al revés, que todo número cojonudo sea número perfecto.En
equivalenciaCojonudosPerfectos
estás comprobando que todo número cojonudo es nùmero perfecto, pero faltaría comprobar también lo contrario.Referencias:
Teorema de Euclides-Euler
vídeo 1
Prueba de la equivalencia cojonuda-perfecta