Menu Close

Números libres de cuadrados

Un número entero positivo es libre de cuadrados si no es divisible por el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

   libreDeCuadrados :: Integer -> Bool

tal que (libreDeCuadrados x) se verifica si x es libre de cuadrados. Por ejemplo,

   libreDeCuadrados 70                    ==  True
   libreDeCuadrados 40                    ==  False
   libreDeCuadrados 510510                ==  True
   libreDeCuadrados (((10^10)^10)^10)     ==  False

Soluciones

import Data.List (nub)
 
-- 1ª definición
-- =============
 
libreDeCuadrados :: Integer -> Bool
libreDeCuadrados x = x == product (divisoresPrimos x)
 
-- (divisoresPrimos x) es la lista de los divisores primos de x. Por
-- ejemplo,  
--    divisoresPrimos 40  ==  [2,5]
--    divisoresPrimos 70  ==  [2,5,7]
divisoresPrimos :: Integer -> [Integer]
divisoresPrimos x = [n | n <- divisores x, primo n]
 
-- (divisores n) es la lista de los divisores del número n. Por ejemplo,
--    divisores 30  ==  [1,2,3,5,6,10,15,30]  
divisores :: Integer -> [Integer]
divisores n = [x | x <- [1..n], n `mod` x == 0]
 
-- (primo n) se verifica si n es primo. Por ejemplo,
--    primo 30  == False
--    primo 31  == True  
primo :: Integer -> Bool
primo n = divisores n == [1, n]
 
-- 2ª definición
-- =============
 
libreDeCuadrados2 :: Integer -> Bool
libreDeCuadrados2 n = 
  null [x | x <- [2..n], rem n (x^2) == 0]
 
-- 3ª definición
-- =============
 
libreDeCuadrados3 :: Integer -> Bool
libreDeCuadrados3 n = 
  null [x | x <- [2..floor (sqrt (fromIntegral n))]
          , rem n (x^2) == 0]
 
-- 4ª definición
-- =============
 
libreDeCuadrados4 :: Integer -> Bool
libreDeCuadrados4 x =
  factorizacion x == nub (factorizacion x)
 
-- (factorizacion n) es la lista de factores primos de n. Por ejemplo,  
--    factorizacion 180  ==  [2,2,3,3,5]
factorizacion :: Integer -> [Integer]
factorizacion n | n == 1    = []
                | otherwise = x : factorizacion (div n x)
  where x = menorFactor n
 
-- (menorFactor n) es el menor divisor de n. Por ejemplo,         
--    menorFactor 15  ==  3
menorFactor :: Integer -> Integer
menorFactor n = head [x | x <- [2..], rem n x == 0]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> libreDeCuadrados 510510
--    True
--    (0.76 secs, 89,522,360 bytes)
--    λ> libreDeCuadrados2 510510
--    True
--    (1.78 secs, 371,826,320 bytes)
--    λ> libreDeCuadrados3 510510
--    True
--    (0.01 secs, 0 bytes)
--    λ> libreDeCuadrados4 510510
--    True
--    (0.00 secs, 153,216 bytes)

Pensamiento

Algunos sentimientos perduran a través de los siglos, pero no por eso han de ser eternos. ¿Cuántos siglos durará todavía el sentimiento de la patria? ¿Y el sentimiento de la paternidad.

Antonio Machado

7 soluciones de “Números libres de cuadrados

  1. frahidzam
    libreDeCuadrados :: Integer -> Bool
    libreDeCuadrados n = null [x | x <- [2..n], mod n (x^2) == 0]
  2. sermurgar
    libreDeCuadrados :: Integer -> Bool
    libreDeCuadrados n = null [c | c <- ms , elem (c^2) ms]
        where ms = divisoresMenos1 n
     
    divisoresMenos1 :: Integer -> [Integer]
    divisoresMenos1 x = [m | m <- [2..x] , mod x m == 0]
  3. berarcmat
    libreDeCuadrados :: Integer -> Bool
    libreDeCuadrados x = 
      and [multiplicidad n x == 1 | n <- divisores x]
     
    multiplicidad :: Integer -> Integer -> Integer
    multiplicidad 1 _ = 1
    multiplicidad x y = 
      head [n | n <- [0..]
              , y `rem` (x^n) == 0
              , y `rem` (x^(n+1)) /= 0]
     
    divisores :: Integer -> [Integer]
    divisores n = [x | x <- [1..n]
                     , n `mod` x == 0]
  4. lucsanand
    -- Mi primera definición fue la siguiente: 
    libreDeCuadrados :: Integer -> Bool
    libreDeCuadrados x = noPotencia (factores x)
     
    factores :: Integer -> [Integer]
    factores n = [x | x <- [1..n], mod n x == 0]
     
    noPotencia :: [Integer] -> Bool
    noPotencia xs
      | [x | x <- xs, y <- xs,x/=y, x == y^2] == [] = True
      | otherwise                                   = False
     
    -- Sin embargo, aun siendo correcta en los primeros ejemplos, en el
    -- último concretamente se vuelve poco eficiente, así que la definimos
    -- de nuevo: 
    libreDeCuadrados' :: Integer -> Bool
    libreDeCuadrados' x
      | [m | m <- [2..x], x `mod` m^2 ==0] == [] = True
      | otherwise                                = False
     
    -- Pero podemos hacerla todavía más eficiente:
    libreDeCuadrados'' :: Integer -> Bool
    libreDeCuadrados'' x
      | [m | m <- [2..x `div` 2], x `mod` m^2 ==0] == [] = True
      | otherwise                                        = False
     
    -- Aquí vemos cómo varía la eficiencia en cada caso:
    --     λ> :set +s
    --    λ> libreDeCuadrados 70
    --    True
    --    (0.69 secs, 172,904 bytes)
    --    λ> libreDeCuadrados' 70
    --    True
    --    (0.03 secs, 171,408 bytes)
    --    λ> libreDeCuadrados'' 70
    --    True
    --    (0.02 secs, 141,984 bytes)
    --    λ> libreDeCuadrados 510510
    --    True
    --    (1.86 secs, 149,270,848 bytes)
    --    λ> libreDeCuadrados' 510510
    --    True
    --    (4.47 secs, 420,772,752 bytes)
    --    λ> libreDeCuadrados'' 510510
    --    True
    --    (2.25 secs, 210,444,984 bytes)
    --    λ> libreDeCuadrados (10^6)
    --    False
    --    (3.42 secs, 272,183,120 bytes)
    --    λ> libreDeCuadrados' (10^6)
    --    False
    --    (0.05 secs, 117,320 bytes)
    --    λ> libreDeCuadrados'' (10^6)
    --    False
    --    (0.03 secs, 117,456 bytes)
    • lucsanand
      import Test.QuickCheck
      import Data.List
       
      -- Otra definición más simple y eficiente:
      libreDeCuadrados''' :: Integer -> Bool
      libreDeCuadrados''' n =
        null [x | x <- factoresPrimos n
                , mod n (x^2) ==0]
       
      factoresPrimos :: Integer -> [Integer]
      factoresPrimos n =
        [x | x <- factores n
           , esPrimo x]
       
      esPrimo :: Integer -> Bool
      esPrimo n = factores n == [1,n]
       
      factores :: Integer -> [Integer]
      factores n = [x | x <- [1..n]
                      , mod n x == 0]
       
      -- Es equivalente a la última solución anterior:
      prop_libreDeCuadrados :: Integer -> Bool
      prop_libreDeCuadrados n =
        libreDeCuadrados'' n == libreDeCuadrados''' n
       
      -- λ> quickCheck prop_libreDeCuadrados
      -- +++ OK, passed 100 tests.
       
      -- A su vez, es más eficiente:
      -- λ> :set +s
      -- λ> libreDeCuadrados''' (((10^10)^10)^10)
      -- False
      -- (0.05 secs, 124,952 bytes)
      -- λ> libreDeCuadrados'' (((10^10)^10)^10)
      -- False
      -- (0.06 secs, 119,272 bytes)
      -- λ> libreDeCuadrados''' 510510
      -- True
      -- (1.81 secs, 139,202,280 bytes)
      -- λ> libreDeCuadrados'' 510510
      -- True
      -- (2.45 secs, 210,445,488 bytes)
  5. luipromor
    libreDeCuadrados :: Integer -> Bool
    libreDeCuadrados x =
      and [y /= z^2 | y <- factores x , z <- factores x ]
      where factores x = [y | y <- [2..x], mod x y ==0]
  6. javmarcha1
    libreDeCuadrados :: Integer -> Bool
    libreDeCuadrados x =
      null [y | y <- [2..x] , rem x (y^2) == 0]
     
    -- Definición más eficiente que libreDeCuadrados
    libreDeCuadrados2 :: Integer -> Bool
    libreDeCuadrados2 x =
      null [y | y <- (divisorescuadrado x) , rem x y == 0]
     
    divisorescuadrado :: Integer -> [Integer]  
    divisorescuadrado x =
      [y^2 | y <-[2..div x 2]
           , rem x y == 0
           , y^2 <= x]
     
    -- Definición más eficiente que libreDeCuadrados y libreDeCuadrados2
    libreDeCuadrados3 :: Integer -> Bool
    libreDeCuadrados3 x =
      factorizacion x == sinRepetidos (factorizacion x)
     
    factorizacion :: Integer -> [Integer]
    factorizacion n 
      | n == 1    = []
      | otherwise = x : factorizacion (div n x)
      where x = menorFactor n
     
    menorFactor :: Integer -> Integer
    menorFactor n = head [x | x <- [2..], rem n x == 0]
     
    sinRepetidos :: Eq a => [a] -> [a]
    sinRepetidos [] = []
    sinRepetidos (x:xs)
      | x `elem` xs = sinRepetidos xs
      | otherwise   = x : sinRepetidos xs
     
    -- Optimización:
    --   λ> libreDeCuadrados 11741730
    --   True
    --   (24.94 secs, 8,642,026,096 bytes)
    --   λ> libreDeCuadrados2 11741730
    --   True
    --   (8.39 secs, 1,597,240,696 bytes)
    --   λ> libreDeCuadrados3 11741730
    --   True
    --   (0.00 secs, 150,208 bytes)

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.