Menu Close

Números completos

José A. Alonso---7 Comentarios
 

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

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]

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   ==  []
  • 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

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
Inicial
, , , , , , , , ,

7 soluciones de “Números completos”

  1. jaibengue 
    import Data.List
 
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n = [(x,y) | y<-[1..floor(sqrt(fromIntegral n))],
                              n `mod` ((y+1)^2) == 0,
                              let x = n `div` ((y+1)^2) * y]
 
completos :: [Integer]
completos = [m | m<-[1..],
                 not(null(descomposiciones m))]

    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”.

    • alegardia

      ¿Puedes explicar tu definición de descomposiciones y por qué los números completos son los que no son libres de cuadrados?

      • jaibengue

        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.

  2. angruicam1 
    descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n = [(x,y) | x <- [1..(n `div` 4)],
                              y <- [1..x],
                              x `rem` y == 0,
                              (x + y) + (x - y) + (x * y) + (x `div` y) == n]
 
completos :: [Integer]
completos = [n | n <- [1..],
                 not (null (descomposiciones n))]
  3. pabhueacu 
    descomposiciones :: Integer -> [(Integer, Integer)]
descomposiciones n =
  [(x,y) | y <- [1..round (sqrt (fromIntegral n))]
         , x <- [y, 2*y..n], aux x y ]
  where aux x y | 2*x + x*y + x `div` y == n = True
                | otherwise                  = False
 
completos :: [Integer]
completos = [x | x <- [1..], not (null(descomposiciones x))]
  4. marsilrey 
    descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n=
  reverse [(x,y) | x <- reverse [1..n]
                 , y <- [1..x]
                 , (x+y)+(x*y)+(x-y)+(div x y) == n
                 , rem x y==0]
 
completos :: [Integer]
completos = [x | x <- [1..]
               , esCompleto x]
 
esCompleto :: Integer -> Bool
esCompleto x = descomposiciones x /= []
  5. marmazalb1 
    descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones a =
  [(x,y) | x <- [1..a]
         , y <- [1..x]
         , (x+y) + (x*y) + (x-y) + (div x y) == a
         , rem x y == 0]
 
completos :: [Integer]
completos = [a | a <- [1..], descomposiciones a /= []]

Los comentarios están cerrados.