Números triangulares con n cifras distintas
Los números triangulares se forman como sigue
* * * * * * * * * * 1 3 6
La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son
1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5
Definir la función
triangularesConCifras :: Int -> [Integer]
tal que (triangulares n) es la lista de los números triangulares con n cifras distintas. Por ejemplo,
take 6 (triangularesConCifras 1) == [1,3,6,55,66,666] take 6 (triangularesConCifras 2) == [10,15,21,28,36,45] take 6 (triangularesConCifras 3) == [105,120,136,153,190,210] take 5 (triangularesConCifras 4) == [1035,1275,1326,1378,1485] take 2 (triangularesConCifras 10) == [1062489753,1239845706]
Soluciones
import Data.List (nub) import Test.QuickCheck -- 1ª solución -- =========== triangularesConCifras1 :: Int -> [Integer] triangularesConCifras1 n = [x | x <- triangulares1, nCifras x == n] -- triangulares1 es la lista de los números triangulares. Por ejemplo, -- take 10 triangulares1 == [1,3,6,10,15,21,28,36,45,55] triangulares1 :: [Integer] triangulares1 = map triangular [1..] triangular :: Integer -> Integer triangular 1 = 1 triangular n = triangular (n-1) + n -- (nCifras x) es el número de cifras distintas del número x. Por -- ejemplo, -- nCifras 325275 == 4 nCifras :: Integer -> Int nCifras = length . nub . show -- 2ª solución -- =========== triangularesConCifras2 :: Int -> [Integer] triangularesConCifras2 n = [x | x <- triangulares2, nCifras x == n] triangulares2 :: [Integer] triangulares2 = [(n*(n+1)) `div` 2 | n <- [1..]] -- 3ª solución -- =========== triangularesConCifras3 :: Int -> [Integer] triangularesConCifras3 n = [x | x <- triangulares3, nCifras x == n] triangulares3 :: [Integer] triangulares3 = 1 : [x+y | (x,y) <- zip [2..] triangulares3] -- 4ª solución -- =========== triangularesConCifras4 :: Int -> [Integer] triangularesConCifras4 n = [x | x <- triangulares4, nCifras x == n] triangulares4 :: [Integer] triangulares4 = 1 : zipWith (+) [2..] triangulares4 -- 5ª solución -- =========== triangularesConCifras5 :: Int -> [Integer] triangularesConCifras5 n = [x | x <- triangulares5, nCifras x == n] triangulares5 :: [Integer] triangulares5 = scanl (+) 1 [2..] -- Comprobación de equivalencia -- ============================ -- La 1ª propiedad es prop_triangularesConCifras1 :: Bool prop_triangularesConCifras1 = [take 2 (triangularesConCifras1 n) | n <- [1..7]] == [take 2 (triangularesConCifras2 n) | n <- [1..7]] -- La comprobación es -- λ> prop_triangularesConCifras1 -- True -- La 2ª propiedad es prop_triangularesConCifras2 :: Int -> Bool prop_triangularesConCifras2 n = all (== take 5 (triangularesConCifras2 n')) [take 5 (triangularesConCifras3 n'), take 5 (triangularesConCifras4 n'), take 5 (triangularesConCifras5 n')] where n' = 1 + n `mod` 9 -- La comprobación es -- λ> quickCheck prop_triangularesConCifras -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> (triangularesConCifras1 3) !! 220 -- 5456556 -- (2.48 secs, 1,228,690,120 bytes) -- λ> (triangularesConCifras2 3) !! 220 -- 5456556 -- (0.01 secs, 4,667,288 bytes) -- -- λ> (triangularesConCifras2 3) !! 600 -- 500010500055 -- (1.76 secs, 1,659,299,872 bytes) -- λ> (triangularesConCifras3 3) !! 600 -- 500010500055 -- (1.67 secs, 1,603,298,648 bytes) -- λ> (triangularesConCifras4 3) !! 600 -- 500010500055 -- (1.20 secs, 1,507,298,248 bytes) -- λ> (triangularesConCifras5 3) !! 600 -- 500010500055 -- (1.15 secs, 1,507,298,256 bytes)
El código se encuentra en GitHub.