Menu Close

Cadenas de divisores

Una cadena de divisores de un número n es una lista donde cada elemento es un divisor de su siguiente elemento en la lista. Por ejemplo, las cadenas de divisores de 12 son [2,4,12], [2,6,12], [2,12], [3,6,12], [3,12], [4,12], [6,12] y [12].

Definir la función

   cadenasDivisores :: Int -> [[Int]]

tal que (cadenasDivisores n) es la lista de las cadenas de divisores de n. Por ejemplo,

   λ> cadenasDivisores 12
   [[2,4,12],[2,6,12],[2,12],[3,6,12],[3,12],[4,12],[6,12],[12]]
   λ> length (cadenaDivisores 48)
   48
   λ> length (cadenaDivisores 120)
   132

Soluciones

import Data.List (sort)
import Data.Numbers.Primes (isPrime)
 
-- 1ª definición
-- =============
 
cadenasDivisores :: Int -> [[Int]]
cadenasDivisores n = sort (extiendeLista [[n]])
    where extiendeLista []           = []
          extiendeLista ((1:xs):yss) = xs : extiendeLista yss
          extiendeLista ((x:xs):yss) =
              extiendeLista ([y:x:xs | y <- divisores x] ++ yss)
 
-- (divisores x) es la lista decreciente de los divisores de x distintos
-- de x. Por ejemplo,
--    divisores 12  ==  [6,4,3,2,1]
divisores :: Int -> [Int]
divisores x = 
    [y | y <- [a,a-1..1], x `mod` y == 0]
    where a = x `div` 2
 
-- 2ª definición
-- =============
 
cadenasDivisores2 :: Int -> [[Int]]
cadenasDivisores2 = sort . aux
    where aux 1 = [[]]
          aux n = [xs ++ [n] | xs <- concatMap aux (divisores n)]
 
-- 3ª definición
-- =============
 
cadenasDivisores3 :: Int -> [[Int]]
cadenasDivisores3 = sort . map reverse . aux
    where aux 1 = [[]]
          aux n = map (n:) (concatMap aux (divisores3 n))
 
-- (divisores3 x) es la lista creciente de los divisores de x distintos
-- de x. Por ejemplo,
--    divisores3 12  ==  [1,2,3,4,6]
divisores3 :: Int -> [Int]
divisores3 x = 
    [y | y <- [1..a], x `mod` y == 0]
    where a = x `div` 2
 
-- 1ª definición de nCadenasDivisores
-- ==================================
 
nCadenasDivisores1 :: Int -> Int
nCadenasDivisores1 = length . cadenasDivisores
 
-- 2ª definición de nCadenasDivisores
-- ==================================
 
nCadenasDivisores2 :: Int -> Int
nCadenasDivisores2 1 = 1
nCadenasDivisores2 n = 
    sum [nCadenasDivisores2 x | x <- divisores n]
Medio

4 soluciones de “Cadenas de divisores

  1. Enrique Zubiría
    cadenasDivisores :: Int -> [[Int]]
    cadenasDivisores n = map (++[n]) (filter esCadenaDivisores (subconjuntos $ divisores n))
     
    divisores :: Int -> [Int]
    divisores n = [m | m <- [2..(n-1)], rem n m == 0]
     
    subconjuntos :: [a] -> [[a]]
    subconjuntos [] = [[]]
    subconjuntos (x:xs) = map (x:) sc ++ sc
      where sc = subconjuntos xs
     
    esCadenaDivisores [] = True
    esCadenaDivisores (x:[]) = True
    esCadenaDivisores (x:y:ys) = rem y x == 0 && esCadenaDivisores (y:ys)
  2. fercarnav
    import Data.List
    import Data.Numbers.Primes 
     
    cadenasDivisores :: Int -> [[Int]]
    cadenasDivisores n =
      map (++[n])
          (filter esCadenaDivisores (subconjuntos (delete n (divisores2 n))))
     
    divisores2 :: Int -> [Int]
    divisores2 = tail.sort
              . map (product . concat)
              . sequence
              . map inits
              . group
              . primeFactors
     
    subconjuntos :: [Int] -> [[Int]]
    subconjuntos  = subsequences
     
    esCadenaDivisores [] = True
    esCadenaDivisores (x:[]) = True
    esCadenaDivisores (x:y:ys) = mod y x == 0 && esCadenaDivisores (y:ys)
  3. goncarmar1
    import Data.List
     
    cadenasDivisores :: Int -> [[Int]]
    cadenasDivisores 1 = [[]]
    cadenasDivisores n =
      concat [map (++[n]) (cadenasDivisores a)| a <- divisoresSinN n]
     
    divisoresSinN :: Int -> [Int]
    divisoresSinN n = [x | x <- [2..(n-1)], n `mod` x == 0]++[1]
     
    -- Añado 1 para que no me de una lista vacía, lo que provocaría que la
    -- función cadenasDivisores siempre diera [[]]
  4. juasuator1
    import Data.List
    import Data.Numbers.Primes
     
    cadenasDivisores :: Int -> [[Int]]
    cadenasDivisores n  = map reverse (cadenasDivAlReves n)
      where
        cadenasDivAlReves n
          | isPrime n = [[n]]
          | otherwise = [n]: [n:xs | z <- divisores n   [1,n],
                                     xs <- cadenasDivAlReves z]
     
    divisores :: Int -> [Int]
    divisores = map product . nub . subsequences . primeFactors

Leave a Reply

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