Menu Close

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)
Avanzado

10 soluciones de “Máxima potencia que divide al factorial

  1. enrnarbej
    maxPotDivFact :: Integer -> Integer -> Integer
    maxPotDivFact p n = aux p n 1
      where
        aux p n k | d > 0     = d + aux p n (k+1)
                  | otherwise = 0
          where d = n `div` p^k
    • enrnarbej
      maxPotDivFact2 :: Integer -> Integer -> Integer
      maxPotDivFact2 p n = sum $ tail $ takeWhile (>0) $ scanl div n (repeat p)
       
      {- Comparacion de eficiencia:
       
      *Main> length (show (maxPotDivFact 2 (10^20000)))
      20000
      (11.59 secs, 1,725,211,232 bytes)
       
      *Main> length (show (maxPotDivFact2 2 (10^20000)))
      20000
      (1.17 secs, 856,852,664 bytes)
      -}
  2. paumacpar

    Usando la fórmula de Polignac:

    maxPotDivFact :: Integer -> Integer -> Integer
    maxPotDivFact p n = auxM2 (tail (iterate (*p) 1)) 0
      where auxM2 (x:xs) k
              | div n x == 0 = k
              | otherwise    = auxM2 xs (k + div n x)
  3. albcercid
    -- Primera definición:
    maxPotDivFact :: Integer -> Integer -> Integer
    maxPotDivFact p n = sum [div n a | a <- takeWhile (n>=) (pot p)]
      where pot n = [n^x | x <- [1..]]
     
    -- Definición mejorada: 
    maxPotDivFact2 :: Integer -> Integer -> Integer
    maxPotDivFact2 p n = x + aux x p
      where x = div n p
            aux x n | t == 0    = 0
                    | otherwise = t + aux t n
              where t = div x n
  4. Chema Cortés
    maxPotDivFact :: Integer -> Integer -> Integer
    maxPotDivFact p = sum  . takeWhile (>0) . tail . iterate (`div` p)
  5. joscasgom1
    maxPotDivFact :: Integer -> Integer -> Integer
    maxPotDivFact n x = funcion  n [1..x]
     
    funcion :: Integer -> [Integer] -> Integer
    funcion _ [] = 0
    funcion n (x:xs)
      | mod x n == 0 = 1 + funcion n (div x n : xs)
      | otherwise    = funcion n xs
  6. margirmon
    maxPotDivFact :: Integer -> Integer -> Integer
    maxPotDivFact p n = fst (aux p (0, n))
      where aux :: Integer -> (Integer, Integer) -> (Integer, Integer)
            aux p (x, 0) = (x, 0)
            aux p (x, n) = aux p (x+y, y) 
              where y = n `div` p
  7. cescarde
    -- 1ª Definición:
    maxPotDivFact :: Integer -> Integer -> Integer
    maxPotDivFact p n = genericLength (filtra p (fPrimos (fact n)))
     
    fact :: Integer -> Integer
    fact 0 = 1
    fact n = n * fact (n-1)
     
    fPrimos :: Integer -> [Integer]
    fPrimos 1 = [] 
    fPrimos n = head [p : fPrimos (div n p) | p <- [2..], mod n p == 0]
     
    filtra :: Integer -> [Integer] -> [Integer]
    filtra _ [] = []
    filtra p (x:xs) | p == x    = x : filtra p xs
                    | otherwise = filtra p xs
     
    -- 2ª Definición:
    maxPotDivFact2 :: Integer -> Integer -> Integer
    maxPotDivFact2 p n = losDivisores p (fact n) 
     
    losDivisores :: Integer -> Integer -> Integer
    losDivisores p n | rem n p == 0 = 1 + losDivisores p (div n p)
                     | otherwise    = 0
  8. Juanjo Ortega (juaorture)

    La solución más eficiente no llega a calcular el último ejemplo.

    import Data.Numbers.Primes
    import Test.QuickCheck
     
    -- La función nIguales n xs cuenta los elementos de la lista xs que son iguales a n.
     
    nIguales :: Eq a => a -> [a] -> Integer
    nIguales _ []                 = 0
    nIguales n (x:xs) | n == x    = 1 + nIguales n xs
                      | otherwise = nIguales n xs
     
    maxPotDivFact :: Integer -> Integer -> Integer
    maxPotDivFact p n = nIguales p (concatMap primeFactors [2..n])
     
    maxPotDivFactFB :: Integer -> Integer -> Integer
    maxPotDivFactFB p n = aux p (product [1..n]) 0
                    where aux :: Integer -> Integer -> Integer -> Integer
                          aux p n x | n `mod` p == 0 = aux p (n `div` p) (x+1)
                                    | otherwise      = x
     
    -- La función maxPotDivFact2 p n cuenta las veces que el factor primo p está en todos
    -- los números de 1 a n, ya que, por ejemplo para el 2, habrá n/2 múltiplos de 2, n/4
    -- múltiplos de 4, n/8 múltiplos de 8...
     
    maxPotDivFact2 :: Integer -> Integer -> Integer
    maxPotDivFact2 p n = sum (takeWhile (>0) [n `div` p^a | a <- [1..]])
     
    -- La siguiente propiedad comprueba la igualdad de las 3 definiciones.
     
    prop_div :: Integer -> Integer -> Property
    prop_div p n = isPrime p && n >= 0 ==> maxPotDivFact p n  == x &&
                                           maxPotDivFact2 p n == x
            where x = maxPotDivFactFB p n
     
    -- Comprobación de la propiedad:
    -- *Main> quickCheck prop_div
    -- *** Gave up! Passed only 87 tests
     
    -- Comparación de eficiencia
    -- *Main> maxPotDivFactFB 2 (10^5)
    -- 99994
    -- (25.98 secs, 29,675,874,248 bytes)
    -- *Main> maxPotDivFact 2 (10^5)
    -- 99994
    -- (2.07 secs, 4,226,115,352 bytes)
    -- *Main> maxPotDivFact2 2 (10^5)
    -- 99994
    -- (0.01 secs, 104,776 bytes)
     
    -- *Main> maxPotDivFact 2 (10^6)
    -- 999993
    -- (48.91 secs, 86,623,561,832 bytes)
    -- *Main> maxPotDivFact2 2 (10^6)
    -- 999993
    -- (0.01 secs, 109,456 bytes)
    • Juanjo Ortega (juaorture)

      Por un fallo en la comprobación pensaba que no calculaba el último ejemplo pero sí que lo hace:

      -- *Main>  length (show (maxPotDivFact2 2 (10^20000))) 
      -- 20000
      -- (11.25 secs, 1,982,493,416 bytes)

Escribe tu solución

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