Exponente en la factorización

Definir la función

   exponente :: Integer -> Integer -> Int

1	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

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.

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.

Un comentario

{-# 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)

-}

{-# 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)

Responder

Exponente en la factorización

Soluciones

Un comentario

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

Un comentario

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico