Números cuyos factoriales son divisibles por x pero no por y
Hay 3 números (el 2, 3 y 4) cuyos factoriales son divisibles por 2 pero no por 5. Análogamente, hay números 5 (el 5, 6, 7, 8, 9) cuyos factoriales son divisibles por 15 pero no por 25.
Definir la función
|
1 |
nNumerosConFactorialesDivisibles :: Integer -> Integer -> Integer |
tal que (nNumerosConFactorialesDivisibles x y) es la cantidad de números cuyo factorial es divisible por x pero no por y. Por ejemplo,
|
1 2 3 |
nNumerosConFactorialesDivisibles 2 5 == 3 nNumerosConFactorialesDivisibles 15 25 == 5 nNumerosConFactorialesDivisibles 100 2000 == 5 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
import Data.List (genericLength) -- 1ª solución -- =========== nNumerosConFactorialesDivisibles :: Integer -> Integer -> Integer nNumerosConFactorialesDivisibles x y = genericLength (numerosConFactorialesDivisibles x y) -- (numerosConFactorialesDivisibles x y) es la lista de números -- divisibles por el factorial de x pero no divisibles por el -- factorial de y. Por ejemplo, -- numerosConFactorialesDivisibles 2 5 == [2,3,4] -- numerosConFactorialesDivisibles 15 25 == [5,6,7,8,9] numerosConFactorialesDivisibles :: Integer -> Integer -> [Integer] numerosConFactorialesDivisibles x y = [z | z <- [0..y-1] , factorial z `mod` x == 0 , factorial z `mod` y /= 0] -- (factorial n) es el factorial de n. Por ejemplo, -- factorial 4 == 24 factorial :: Integer -> Integer factorial n = product [1..n] -- 2ª solución (usando la función de Smarandache) -- ============================================== nNumerosConFactorialesDivisibles2 :: Integer -> Integer -> Integer nNumerosConFactorialesDivisibles2 x y = max 0 (smarandache y - smarandache x) --(smarandache n) es el menor número cuyo factorial es divisible por -- n. Por ejemplo, -- smarandache 8 == 4 -- smarandache 10 == 5 -- smarandache 16 == 6 smarandache :: Integer -> Integer smarandache x = head [n | (n,y) <- zip [0..] factoriales , y `mod` x == 0] -- factoriales es la lista de los factoriales. Por ejemplo, -- λ> take 12 factoriales -- [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800] factoriales :: [Integer] factoriales = 1 : scanl1 (*) [1..] -- Comparación de eficiencia -- λ> nNumerosConFactorialesDivisibles 100 2000 -- 5 -- (2.70 secs, 3,933,938,648 bytes) -- λ> nNumerosConFactorialesDivisibles2 100 2000 -- 5 -- (0.01 secs, 148,200 bytes) |