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
(8 + 2) + (8 - 2) + (8 * 2) + (8 / 2) = 36 |
(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
descomposiciones :: Integer -> [(Integer,Integer)]
completos :: [Integer] |
descomposiciones :: Integer -> [(Integer,Integer)]
completos :: [Integer]
tales que
- (descomposiciones n) es la lista de las descomposiones de n. Por ejemplo,
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 == [] |
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,
take 15 completos == [4,8,9,12,16,18,20,24,25,27,28,32,36,40,44]
completos !! 100 == 261 |
take 15 completos == [4,8,9,12,16,18,20,24,25,27,28,32,36,40,44]
completos !! 100 == 261
Soluciones
-- 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 |
-- 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.