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 |