Menor número triangular con más de n divisores
La sucesión de los números triangulares se obtiene sumando los números naturales.
Así, el 7º número triangular es
|
1 |
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. |
Los primeros 10 números triangulares son
|
1 |
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... |
Los divisores de los primeros 7 números triangulares son:
|
1 2 3 4 5 6 7 |
1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 |
Como se puede observar, 28 es el menor número triangular con más de 5 divisores.
Definir la función
|
1 |
menorTriangularConAlMenosNDivisores :: Int -> Integer |
tal que (menorTriangularConAlMenosNDivisores n) es el menor número triangular que tiene al menos n divisores. Por ejemplo,
|
1 2 3 |
menorTriangularConAlMenosNDivisores 5 == 28 menorTriangularConAlMenosNDivisores 50 == 25200 menorTriangularConAlMenosNDivisores 500 == 76576500 |
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
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) |
4 Comentarios