import Data.List (group)
import Data.Numbers.Primes (primes,primeFactors)
-- 1ª definición
-- =============
menorTriangularConAlMenosNDivisores1 :: Int -> Integer
menorTriangularConAlMenosNDivisores1 n =
head [x | x <- triangulares, nDivisores x >= n]
-- triangulares es la sucesión de los números triangulares. Por ejemplo,
-- take 10 triangulares == [1,3,6,10,15,21,28,36,45,55]
triangulares :: [Integer]
triangulares = scanl (+) 1 [2..]
-- (nDivisores x) es el número de divisores de x. Por ejemplo,
-- nDivisores 28 == 6
nDivisores :: Integer -> Int
nDivisores x =
1 + length [y | y <- [1..x `div` 2], mod x y == 0]
-- 2ª solución
-- ===========
menorTriangularConAlMenosNDivisores2 :: Int -> Integer
menorTriangularConAlMenosNDivisores2 n =
head [x | x <- triangulares, nDivisores2 x >= n]
-- (nDivisores2 x) es el número de divisores de x. Por ejemplo,
-- nDivisores2 28 == 6
nDivisores2 :: Integer -> Int
nDivisores2 n = product [1 + length xs | xs <- group (factoresPrimos n)]
-- (factoresPrimos n) es la lista de los factores primos de n. Por
-- ejemplo,
-- factoresPrimos 28 == [2,2,7]
factoresPrimos :: Integer -> [Integer]
factoresPrimos n = aux n primos
where aux n (p:ps)
| p*p > n = [n]
| n `mod` p == 0 = p : aux (n `div` p) (p:ps)
| otherwise = aux n ps
-- primos es la lista de los números primos. Por ejemplo,
-- take 10 primos == [2,3,5,7,11,13,17,19,23,29]
primos :: [Integer]
primos = 2 : filter ((==1) . length . factoresPrimos) [3,5..]
-- 3ª solución (usando primes)
-- ===========================
menorTriangularConAlMenosNDivisores3 :: Int -> Integer
menorTriangularConAlMenosNDivisores3 n =
head [x | x <- triangulares, nDivisores3 x >= n]
-- (nDivisores3 x) es el número de divisores de x. Por ejemplo,
-- nDivisores3 28 == 6
nDivisores3 :: Integer -> Int
nDivisores3 n = product [1 + length xs | xs <- group (factoresPrimos3 n)]
-- (factoresPrimos3 n) es la lista de los factores primos de n. Por
-- ejemplo,
-- factoresPrimos3 28 == [2,2,7]
factoresPrimos3 n = aux n primes
where
aux n (p:ps)
| p*p > n = [n]
| n `mod` p == 0 = p : aux (n `div` p) (p:ps)
| otherwise = aux n ps
-- 4ª solución (usando primeFactors)
-- =================================
menorTriangularConAlMenosNDivisores4 :: Int -> Integer
menorTriangularConAlMenosNDivisores4 n =
head [x | x <- triangulares, nDivisores4 x >= n]
-- (nDivisores4 x) es el número de divisores de x. Por ejemplo,
-- nDivisores4 28 == 6
nDivisores4 :: Integer -> Int
nDivisores4 n = product [1 + length xs | xs <- group (primeFactors n)]
-- ---------------------------------------------------------------------
-- § Comparación de eficiencia --
-- ---------------------------------------------------------------------
-- La comparación es
-- ghci> menorTriangularConAlMenosNDivisores1 50
-- 25200
-- (1.25 secs, 200236512 bytes)
--
-- ghci> menorTriangularConAlMenosNDivisores2 50
-- 25200
-- (0.02 secs, 4199904 bytes)
--
-- ghci> menorTriangularConAlMenosNDivisores3 50
-- 25200
-- (0.03 secs, 6265128 bytes)
--
-- ghci> menorTriangularConAlMenosNDivisores4 50
-- 25200
-- (0.01 secs, 5753048 bytes)