Números completos
Las descomposiciones de un número n son las parejas de números (x,y) tales que x >= y y la suma de las cuatro operaciones básicas (suma, producto, resta (el mayor menos el menor) y cociente (el mayor entre el menor)) es el número n. Por ejemplo, (8,2) es una descomposición de 36 ya que
1 |
(8 + 2) + (8 - 2) + (8 * 2) + (8 / 2) = 36 |
Un número es completo si tiene alguna descomposición como las anteriores. Por ejemplo, el 36 es completo pero el 21 no lo es.
Definir las siguientes funciones
1 2 |
descomposiciones :: Integer -> [(Integer,Integer)] completos :: [Integer] |
tales que
- (descomposiciones n) es la lista de las descomposiones de n. Por ejemplo,
1 2 3 4 5 |
descomposiciones 12 == [(3,1)] descomposiciones 16 == [(3,3),(4,1)] descomposiciones 36 == [(5,5),(8,2),(9,1)] descomposiciones 288 == [(22,11),(40,5),(54,3),(64,2),(72,1)] descomposiciones 21 == [] |
- completos es la lista de los números completos. Por ejemplo,
1 2 |
take 15 completos == [4,8,9,12,16,18,20,24,25,27,28,32,36,40,44] completos !! 100 == 261 |
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 |
-- 1ª solución de descomposiciones descomposiciones1 :: Integer -> [(Integer,Integer)] descomposiciones1 n = [(x,y) | x <- [1..n] , y <- [1..x] , x `rem` y == 0 , (x + y) + (x - y) + (x * y) + (x `div` y) == n] -- 2ª solución de descomposiciones descomposiciones2 :: Integer -> [(Integer,Integer)] descomposiciones2 n = [(n `div` ((y+1)^2) * y,y) | y <- [1..(floor . sqrt . fromIntegral) n] , n `mod` ((y+1)^2) == 0] -- Comparación de eficiencia -- λ> length (descomposiciones1 4000) -- 5 -- (3.16 secs, 1,618,693,272 bytes) -- λ> length (descomposiciones2 4000) -- 5 -- (0.00 secs, 188,208 bytes) -- Usaremos la 2ª definició de descomposiciones descomposiciones :: Integer -> [(Integer,Integer)] descomposiciones = descomposiciones2 -- 1ª definición de completos completos1 :: [Integer] completos1 = [n | n <- [1..] , not (null (descomposiciones n))] -- 2ª definición de completos completos2 :: [Integer] completos2 = filter (not . null . descomposiciones) [1..] -- Usaremos la 2ª definición de completos completos :: [Integer] completos = completos2 |
Además, es fácil demostrar que un número es completo si y solo si no es libre de cuadrados, luego podemos usar el ejercicio del Viernes pasado para hacer mas eficiente la función «completos».
¿Puedes explicar tu definición de descomposiciones y por qué los números completos son los que no son libres de cuadrados?
La función «descomposiciones n» te da todos todos los pares (x,y) tales que [(x+y) + (x-y) + xy + x/y == n].
Operando vemos que esto es equivalente a que (x,y) cumpla [x(y+1)²/y == n].
De donde se sigue [x == ny/(y+1)²].
Es fácil ver que [gcd(y, y+1) == gcd(y, 1) == 1], luego si x es entero, (y+1)² divide a n.
Ahora es sencillo entender la definición:
Elegimos un y entero, entre 1 y la raiz cuadrada de n, ya que si y es mayor que la raiz cuadrada de n es fácil ver que (y+1)²>n y por tanto (y+1)² no podrá dividir a n.
Ahora comprobamos que (y+1)² divida a n y si esto es así fijamos x igual a ny/(y+1)², y ya hemos encontrado un par (x,y) que cumple [(x+y) + (x-y) + xy + x/y == n], además es fácil ver que x será mayor o igual que y ya que [n/(y+1)² >= 1].
Con este conocimiento es fácil ver que n es completo si y solo si es libre de cuadrados, porque debe existir al menos un cuadrado, (y+1)², que lo divida para que exista un par (x,y) que cumpla [(x+y) + (x-y) + xy + x/y == n] y además si no es libre de cuadrados existirá y tal que (y+1)² divida a n.