Máxima potencia que divide al factorial
La máxima potencia de 2 que divide al factorial de 5 es 3, ya que 5! = 120, 120 es divisible por 2^3 y no lo es por 2^4.
Definir la función
maxPotDivFact :: Integer -> Integer -> Integer
tal que (maxPotDivFact p n), para cada primo p, es el mayor k tal que p^k divide al factorial de n. Por ejemplo,
maxPotDivFact 2 5 == 3 maxPotDivFact 3 6 == 2 maxPotDivFact 2 10 == 8 maxPotDivFact 3 10 == 4 maxPotDivFact 2 (10^2) == 97 maxPotDivFact 2 (10^3) == 994 maxPotDivFact 2 (10^4) == 9995 maxPotDivFact 2 (10^5) == 99994 maxPotDivFact 2 (10^6) == 999993 maxPotDivFact 3 (10^5) == 49995 maxPotDivFact 3 (10^6) == 499993 maxPotDivFact 7 (10^5) == 16662 maxPotDivFact 7 (10^6) == 166664 length (show (maxPotDivFact 2 (10^20000))) == 20000
Soluciones
import Data.List (genericIndex, genericTake) import Data.Numbers.Primes (primes) import Test.QuickCheck -- 1ª definición maxPotDivFact :: Integer -> Integer -> Integer maxPotDivFact p n = head [k | k <- [0..], f `mod` (p^k) /= 0] - 1 where f = product [1..n] -- 1ª definición maxPotDivFact2 :: Integer -> Integer -> Integer maxPotDivFact2 p n | n < p = 0 | otherwise = m + maxPotDivFact2 p m where m = n `div` p -- 3ª definición maxPotDivFact3 :: Integer -> Integer -> Integer maxPotDivFact3 p = sum . takeWhile (> 0) . tail . iterate (`div` p) -- Comparación de eficiencia -- λ> maxPotDivFact 2 (10^4) -- 9995 -- (5.47 secs, 161,040,624 bytes) -- λ> maxPotDivFact2 2 (10^4) -- 9995 -- (0.01 secs, 0 bytes) -- λ> maxPotDivFact2 2 (10^4) -- 9995 -- (0.01 secs, 0 bytes) -- -- λ> length (show (maxPotDivFact2 2 (10^20000))) -- 20000 -- (1.93 secs, 592,168,544 bytes) -- λ> length (show (maxPotDivFact3 2 (10^20000))) -- 20000 -- (2.93 secs, 861,791,504 bytes)