Menu Close

Exponente en la factorización

Definir la función

   exponente :: Integer -> Integer -> Int

tal que (exponente x n) es el exponente de x en la factorizacón prima de n (se supone que x > 1 y n > 0). Por ejemplo,

   exponente 2 24  ==  3
   exponente 3 24  ==  1
   exponente 6 24  ==  0
   exponente 7 24  ==  0

Soluciones

import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
exponente1 :: Integer -> Integer -> Int
exponente1 x n
  | esPrimo x = aux n
  | otherwise = 0
  where aux m | m `mod` x == 0 = 1 + aux (m `div` x)
              | otherwise      = 0
 
-- (esPrimo x) se verifica si x es un número primo. Por ejemplo,
--    esPrimo 7  ==  True
--    esPrimo 8  ==  False
esPrimo :: Integer -> Bool
esPrimo x =
  [y | y <- [1..x], x `mod` y == 0] == [1,x]
 
-- 2ª solución
-- ===========
 
exponente2 :: Integer -> Integer -> Int
exponente2 x n
  | esPrimo x = length (takeWhile (`divisible` x) (iterate (`div` x) n))
  | otherwise = 0
 
-- (divisible n x) se verifica si ne divisible por x. Por ejemplo,
--    divisible 6 2  ==  True
--    divisible 7 2  ==  False
divisible :: Integer -> Integer -> Bool
divisible n x = n `mod` x == 0
 
-- 3ª solución
-- ===========
 
exponente3 :: Integer -> Integer -> Int
exponente3 x n =
  length (filter (==x) (primeFactors n))
 
-- Equivalencia de las definiciones
-- ================================
 
-- La propiedad es
prop_exponente :: Integer -> Integer -> Property
prop_exponente x n =
  x > 1 && n > 0 ==>
  exponente1 x n == exponente2 x n &&
  exponente1 x n == exponente3 x n
 
-- La comprobación es
--    λ> quickCheck prop_exponente
--    +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Ejercicio

Una solución de “Exponente en la factorización

  1. j0sejuan
    {-# LANGUAGE MagicHash #-}
    import GHC.Integer.Logarithms
    import GHC.Types
    import GHC.Prim
     
    -- trivial
    exponente' b n = length $ takeWhile ((0==).(n `mod`)) $ (b^) <$> [1..]
     
    -- el logaritmo de 2 es saber la posición del MSB
    log2 :: Integer -> Int
    log2 n = I# (integerLog2# n)
     
    -- un takeWhile pero que devuelve el primero que incumple
    takeWhile' _ [] = []
    takeWhile' f (x:xs) = if f x then x: takeWhile' f xs else [x]
     
    -- una cota superior es z = b^e que podemos usar para revisar
    --   e, e/2, e/4, ..., 0
    exponente b z = id
     $ sum
     $ tail
     $ map fst
     $ takeWhile' ((0/=).snd.snd)
     $ iterate ((_, (s, e)) ->
         let b' = b^e
             e' = exponente' b' s
         in  (e' * e, (s `div` (b'^e'), e `div` 2)))
         (-1,(z,log2 z `div` log2 b))
     
    {-
     
    *Main> quickCheckWith (stdArgs {maxSuccess = 10000}) $ x n ->
                x > 1 && n > 0 ==> exponente x n == exponente' x n
    +++ OK, passed 10000 tests; 37381 discarded.
    (0.77 secs, 981,831,632 bytes)
     
    *Main> exponente' 4 (4^45678 * 37)
    45678
    (8.62 secs, 1,205,007,712 bytes)
     
    *Main> exponente 4 (4^45678 * 37)
    45678
    (0.01 secs, 389,336 bytes)
     
    -}

Escribe tu solución

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