Menu Close

Representaciones de un número como potencia

El número 512 se puede escribir de tres maneras como potencias:

   512 = 2⁹ = 8³ = 512¹

Definir las funciones

   potencias       :: Integer -> [(Integer,Integer)]
   numeroPotencias :: Integer -> Int

tales que

  • (potencias x) es la lista de las representaciones de x como potencias de números enteros positivos. Por ejemplo,
     potencias 7      ==  [(7,1)]
     potencias 8      ==  [(2,3),(8,1)]
     potencias 512    ==  [(2,9),(8,3),(512,1)]
     potencias 16384  ==  [(2,14),(4,7),(128,2),(16384,1)]
     potencias 65536  ==  [(2,16),(4,8),(16,4),(256,2),(65536,1)]
  • (numeroPotencias x) de las representaciones de x como potencias de números enteros positivos. Por ejemplo,
     numeroPotencias 7          ==  1
     numeroPotencias 8          ==  2
     numeroPotencias 512        ==  3
     numeroPotencias 16384      ==  4
     numeroPotencias 65536      ==  5
     numeroPotencias (2^(10^5)) ==  36

Soluciones

import Data.List (group,genericLength)
import Data.Numbers.Primes (primeFactors)
 
potencias :: Integer -> [(Integer,Integer)]
potencias x = [(a^d,b `div` d) | d <- divisores b]
  where ps = factorizacionPrima x
        b   = mcd (map snd ps)
        a   = product [c^(e `div` b) | (c,e) <- ps]
 
-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 120  ==  [1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120]
divisores :: Integer -> [Integer]
divisores x =
  [y | y <- [1..x], x `mod` y == 0]
 
-- (factorizacionPrima x) es la factorización prima de x. Por ejemplo,
--    factorizacionPrima 1200  ==  [(2,4),(3,1),(5,2)]
factorizacionPrima :: Integer -> [(Integer,Integer)]
factorizacionPrima x =
  [(head xs, genericLength xs) | xs <- group (primeFactors x)]
 
-- (mcd xs) es el máximo común divisor de xs. Por ejemplo,
--    mcd [12,30,42]  ==  6
mcd :: Integral a => [a] -> a
mcd xs = foldr1 gcd xs
 
-- 1ª definición de numeroPotencias
-- ================================
 
--    numeroPotencias 7          ==  1
--    numeroPotencias 8          ==  2
--    numeroPotencias 512        ==  3
--    numeroPotencias 16384      ==  4
--    numeroPotencias 65536      ==  5
--    numeroPotencias (2^(10^5)) ==  36
numeroPotencias :: Integer -> Int
numeroPotencias = length . potencias
 
-- 2ª definición de numeroPotencias
-- ================================
 
numeroPotencias2 :: Integer -> Int
numeroPotencias2 n =
  numeroDivisores (mcd (map length (group (primeFactors n))))
 
-- (numeroDivisores n) es el número de divisores de n. Por ejemplo,
--    numeroDivisores 12  ==  6
--    numeroDivisores 14  ==  4
numeroDivisores :: Int -> Int
numeroDivisores =
  product . map ((+1) . length) . group . primeFactors
 
-- Comparación de eficiencia de numeroPotencias
-- ============================================
 
-- La comparación es
--    λ> numeroPotencias (2^(10^5))
--    36
--    (0.40 secs, 707,287,312 bytes)
--    λ> numeroPotencias2 (2^(10^5))
--    36
--    (0.35 secs, 675,954,872 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

5 soluciones de “Representaciones de un número como potencia

  1. Adolfo Enrique Vázquez Ruiz
     
    potencias :: Integer -> [(Integer,Integer)]
    potencias n = aux1 ( potencia n )
     
    numeroPotencias :: Integer -> Int
    numeroPotencias n = genericLength ( potencias n )
     
    --observemos según los resultados ofrecidos en el enunciado que los pares
    --siguen una sucesión en la que se va elevando el primer término al primer
    --divisor del segundo término y el segundo elemento se divide entre el primer
    --divisor ya mencionado. Sin embargo, debido a que el segundo elemento del par
    --puede tener distintos divisores, estaríamos omitiendo esas
    --posibilidades. Entonces, debemos seguir esta sucesión para cada uno de los
    --posibles divisores del segundo elemento. Por ello, ampliamos la función
    --sucesionParesExp con la función aux1. Estas listas se elaboran a raíz del
    --resultado obtenido en potencia.
     
    sucesionParesExp :: (Integer,Integer) -> [(Integer,Integer)]
    sucesionParesExp (n,1) = []
    sucesionParesExp (n,m) = [(n^(primerDivisor m) , m `div` (primerDivisor m))] ++ sucesionParesExp ( (n^(primerDivisor m) , m `div` (primerDivisor m)) )
     
    aux1 :: (Integer,Integer) -> [(Integer,Integer)]
    aux1 (n,m) = nub ( sort ([(n^(m `div` x) , x) | x <- [1..m] , rem m x == 0] ++ (concat [sucesionParesExp (n^(m `div` x) , x) | x <- [1..m] , rem m x == 0])))
     
    factorPotencia :: Integer -> Integer -> Integer
    factorPotencia 1 m = 0
    factorPotencia n m = 1 + factorPotencia (n `div` m) m
    --factorPotencia determina el número al que se debe elevar el divisor del
    --número en cuestión para igualar el número dado.
     
    potencia :: Integer -> (Integer, Integer)
    potencia n = (primerDivisor n , factorPotencia n (primerDivisor n))
     
    --potencia crea el par formado por el divisor del número y el resultado de
    --factorPotencia. 
     
    primerDivisor :: Integer -> Integer
    primerDivisor n = head [ x | x <- [2..] , rem n x == 0]
    --primerDivisor es el primer divisor del número en cuestión.
     
    --La función en general es bastante eficiente, puesto que el último ejemplo
    --(número de potencias de 2^(10^5)) lo calcula en 0'5 segundos. Ello es debido
    --a que, como se puede observar, no se emplean en exceso listas infinitas y se
    --usan por el contrario patrones y sucesiones, pese a que muchas son de
    --carácter recursivo.
  2. Joaquín Infante Rodríguez
     
    import Data.List
    import Data.Numbers.Primes
     
    potencias ::  Integer -> [(Integer,Integer)]
    potencias x  | isPrime x                         = [(x,1)]
                 | genericLength (nub q) == 1        = [(y,n) |  n<-[1..genericLength q], y<-aux, x==y^n] ++[(x,1)]
                 | otherwise                         = [(y,n) |  n<-[1..genericLength q], y<-[1..r] ,
                                                                                          x==y^n] ++ [(x,1)]
                          where aux = [p^n | n<-[1..genericLength q], (p^n)<= r]
                                r = raizCuadradaAReal (fromIntegral x :: Float)
                                q = primeFactors x
                                p = head q
     
     
    numeroPotencias :: Integer -> Int
    numeroPotencias x = genericLength $potencias x
     
    raizCuadradaAReal :: Float -> Integer
    raizCuadradaAReal x = truncate (sqrt x)
  3. Rubén Muñoz Mkrtchian
    import Data.List
    import Data.Numbers.Primes
     
    -- Definición de potencias
    -- =======================
     
    potencias :: Integer -> [(Integer,Integer)]
    potencias n = aux xs (zip ys (reverse ys))
      where xs = primeraLista (zs1,zs2)
            ys = divisores (mcdLista zs2)
            (zs1,zs2) = factoresConPotencias n
            aux xs ys = [(m^a,b) | (a,b) <- ys]
              where m = product xs
     
    -- primeraLista (xs,ys) es la lista a partir de la cual vamos a calcular por
    -- comprensión la lista de potencias del número n. El producto de esta lista se
    -- corresponde con el número al que se le puede asociar el exponente más alto.
    --    λ> primeraLista ([2,3,5],[6,4,8])
    --    [8,9,625]
     
    primeraLista :: ([Integer],[Integer]) -> [Integer]
    primeraLista (xs,ys) = zipWith (^) xs (map (`div` mcdLista ys) ys)
     
    -- factoresConPotencias n es el par cuyo primer elemento está formado por los
    -- números primos de la factorización de n y cuyo segundo elemento está formado
    -- por los exponentes asociados a dichos números. Por ejemplo,
    --    λ> factoresConPotencias 2025000000
    --    ([2,3,5],[6,4,8])
     
    factoresConPotencias :: Integer -> ([Integer],[Integer])
    factoresConPotencias n = (map head xss, map genericLength xss)
      where xss = group (primeFactors n)
     
    -- divisores n es la lista formada por los divisores de n. Por ejemplo,
    --   λ> divisores 6
    --   [1,2,3,6]
     
    divisores :: Integer -> [Integer]
    divisores = sort
              . map (product . concat)
              . productoCartesiano
              . map inits
              . group
              . primeFactors
     
    -- productoCartesiano xss es el producto cartesiano de las listas de xss. Por
    -- ejemplo, 
    --    λ> productoCartesiano [[1,3],[2,5],[6,4]]
    --    [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]
     
    productoCartesiano :: [[a]] -> [[a]]
    productoCartesiano []       = [[]]
    productoCartesiano (xs:xss) = [x:ys | x <- xs, ys <- productoCartesiano xss]
     
    -- mcdLista xs es el máximo común divisor de todos los elementos que componen
    -- la lista xs. Por ejemplo,
    --    λ> mcdLista [3,9,6,18]
    --    3
     
    mcdLista :: [Integer] -> Integer
    mcdLista = foldl1 gcd
     
    -- Definición de numeroPotencias
    -- =============================
     
    numeroPotencias :: Integer -> Int
    numeroPotencias = length . potencias
     
    -- Con esta definición se calcula en un tiempo razonable el último ejemplo.
    --    λ> numeroPotencias (2^(10^5))
    --    36
    --    (0.34 secs, 687,302,992 bytes)
  4. Juan María Jiménez Jiménez
     
     
    --Para hacer esta definicion he tenido en cuenta el patron que tienen las soluciones de
    --la funcion potencias. Este patron consiste en que la primera y la ultima potencia son
    --respectivamente las descomposicion total del numero en factores primos expresado 
    --como potencia, y el propio numero elevado a 1. En las soluciones intermedias vemos que el exponente de las potencias siguientes son los divisores de la primera potencia. Por ejemplo en
    -- 512, la primera potencia era 2^9 y los siguientes exponentes son 3 y 1. El indice resulta de agrupar
    --el indice original en grupos de x==(exponente de la potencia). Aunque la explicacion sea farragoda, es bastante simple.
     
    --Definimos la funcion divisores que nos hara falta más adelante:
     
    divisores :: Integer -> [Integer]
    divisores n = nub(map (product) (subsequences (primeFactors n)))
     
    --SeparaEnNdiv, toma una lista y un numero y genera una lista donde los elementos se separan 
    --en los divisores de n:
    --λ> separaEnNdiv (primeFactors 8) (genericLength (primeFactors 8))
    --[   [[2],[2],[2],[ ]] , 
    --    [[2,2,2],[]]       ] 
    -- Como vemos, como primeFactors 8  tiene una longitud de 3, se crean dos listas, una con PrimeFactors dividida en grupos de 3 y otra en grupos de 1.
     
    separaEnNdiv :: [Integer] -> Integer -> [[[Integer]]]
    separaEnNdiv xs 0 = [[xs]]
    separaEnNdiv [] _ = []
    separaEnNdiv xs n = map f auxxs
      where auxxs = zip (repeat (xs)) (map (fromIntegral) (divisores n))
            f (as,a) = separa a as
            separa a as | length as >= a = take a as : separa a (drop a as)
                        | otherwise = [as]
     
    --Finalmente solo queda calcular los indices ya que los exponentes correspondientes seran
    --la longitud de cada lista - 1 (por la lista vacia). Para calcular los indices unicamente hacemos el
    --producto de cada grupo de las listas anteriores.
     
    potencias :: Integer -> [(Integer,Integer)]
    potencias n = map f (separaEnNdiv pfn lpfn)
      where pfn   = primeFactors n
            lpfn  = genericLength pfn
            f  xs = (product (head xs) , genericLength xs -1)
     
    numeroPotencias :: Integer -> Int
    numeroPotencias n = length (potencias n)
  5. Inés Mora Caro
     
     
     
    import Data.List
    import Data.Numbers.Primes (primeFactors)
     
    -- (potencias x) es la lista  [(número,exponente)] de las
    -- representaciones de x como potencia de números enteros positivos:
     
    potencias :: Integer -> [(Integer,Integer)]
    potencias x | comprPotencia x = genericTake
                                         (nDivisores (snd (head (potencias))))
                                          potencias
     
                | otherwise = [(x,1)]
                              where potencias =
                                      [((head factores)^n, m`div`n) |
                                       n <- [1..x`div`2],
                                       m == n*(m`div`n)]
                                              where m = genericLength factores 
                                                    factores = primeFactors x
     
     
    -- Por algún motivo al hacerlo con números grandes la lista se queda sin
    -- cerrar, por lo que voy a calcular el número de divisores de
    -- (snd (head (potencias)) para que esto no ocurra.
     
    nDivisores :: Integer -> Integer
    nDivisores x = genericLength
                     $ nub $ map product
                               $ subsequences $ primeFactors x
     
    comprPotencia :: Integer -> Bool
    comprPotencia x | length primos > 1 =
                              isPrefixOf primos
                                (genericTake x (repeat (head primos)))
                    | otherwise = False
                               where primos = primeFactors x
     
     
    numeroPotencias :: Integer -> Integer
    numeroPotencias = genericLength.potencias
     
    -- Comprobamos que funciona:
    -- λ> potencias 65536
    -- [(2,16),(4,8),(16,4),(256,2),(65536,1)]
     
    -- Es capaz de calcularlas con números muy grandes:
    -- λ> numeroPotencias(2^(10^5))
    -- 36
    -- (3.53 secs, 2,634,732,624 bytes)
     
    -- Apuntes:
     
    -- length xs == 2*(m`div`2)
    -- length xs == 3*(m`div`3)
    --    ...
    -- length xs == (m`div`2)*m`div`(m`div`2)
    --      where m = length xs
     
    -- En general, length xs == n*(m`div`n)

Leave a Reply

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