Menu Close

Números triangulares y sus propiedades en Haskell

Los números triangulares se forman como sigue
triangulares

En la siguiente relación de ejercicios (elaborada para I1M) se muestran distintas definiciones de los números triangulares y algunas de sus propiedades en Haskell.

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------
 
import Data.List
import Test.QuickCheck
 
-- ---------------------------------------------------------------------
-- § Números triangulares                                             --
-- ---------------------------------------------------------------------
 
-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir, por recursión, la función
--    triangularR :: Integer -> Integer
-- tal que (triangularR n) es el n-ésimo número triangular. Por ejemplo,
--    triangularR 3  ==  6
--    triangularR 4  ==  10
-- ---------------------------------------------------------------------
 
triangularR :: Integer -> Integer
triangularR 1 = 1
triangularR n = n + triangularR (n-1)
 
-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir, por comprensión, la función
--    triangularC :: Integer -> Integer
-- tal que (triangularC n) es el n-ésimo número triangular. Por ejemplo,
--    triangularC 3  ==  6
--    triangularC 4  ==  10
-- ---------------------------------------------------------------------
 
triangularC :: Integer -> Integer
triangularC n = sum [1..n]
 
-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir, mediante una fórmula, la función
--    triangular :: Integer -> Integer
-- tal que (triangular n) es el n-ésimo número triangular. Por ejemplo,
--    triangular 3  ==  6
--    triangular 4  ==  10
-- ---------------------------------------------------------------------
 
triangular :: Integer -> Integer
triangular n = n*(n+1) `div` 2
 
-- ---------------------------------------------------------------------
-- Ejercicio 4. Comprobar con QuickCheck que las tres definiciones
-- anteriores son equivalentes. 
-- ---------------------------------------------------------------------
 
-- La propiedad es
prop_equivalencia :: Integer -> Property
prop_equivalencia n =
    n > 0 ==> triangular n == triangularR n &&
              triangular n == triangularC n 
 
-- La comprobación es
--    ghci> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.
 
-- ---------------------------------------------------------------------
-- Ejercicio 5. Comparar el tiempo y espacio utilizado en los
-- siguientes cálculos
--    triangularR 1000000
--    triangularC 1000000
--    triangular  1000000
-- ---------------------------------------------------------------------
 
--    ghci> triangularR 1000000
--    500000500000
--    (1.80 secs, 173351432 bytes)
--    ghci> triangularC 1000000
--    500000500000
--    (0.79 secs, 140856704 bytes)
--    ghci> triangular 1000000
--    500000500000
--    (0.01 secs, 521392 bytes)
 
-- ---------------------------------------------------------------------
-- § Suma de pares de triangulares consecutivos                       --
-- ---------------------------------------------------------------------
 
-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir, usando triangular, la función
--    sumaTriangularesConsecutivos :: Integer -> Integer
-- tal que (sumaTriangularesConsecutivos n) es la suma de número
-- triangular n-ésimo y su siguiente número triangular. Por ejemplo,
--    sumaTriangularesConsecutivos 3  ==  16
-- ---------------------------------------------------------------------
 
sumaTriangularesConsecutivos :: Integer -> Integer
sumaTriangularesConsecutivos n = 
    triangular n + triangular (n+1)
 
-- ---------------------------------------------------------------------
-- Ejercicio 7. Calcular los valores de (sumaTriangularesConsecutivos n)
-- para n entre 1 y 10. 
-- ---------------------------------------------------------------------
 
-- El cálculo es
--    ghci> [sumaTriangularesConsecutivos n | n <- [1..10]]
--    [4,9,16,25,36,49,64,81,100,121]
 
-- ---------------------------------------------------------------------
-- Ejercicio 8. A partir del cálculo del ejercicio anterior conjeturar
-- una fórmula para calcular (sumaTriangularesConsecutivos n) y
-- comprobarla con  QuickCheck. 
-- ---------------------------------------------------------------------
 
-- La conjetura es que (sumaTriangularesConsecutivos n) = (n+1)^2
conjetura :: Integer -> Property
conjetura n =
    n > 0 ==> sumaTriangularesConsecutivos n == (n+1)^2
 
-- La comprobación es
--    ghci> quickCheck conjetura
--    +++ OK, passed 100 tests.
 
-- ---------------------------------------------------------------------
-- § La sucesión de números triangulares                              --
-- ---------------------------------------------------------------------
 
-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir, usando triangular, la función
--    triangulares1 :: [Integer]
-- tal que 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 = [triangular n | n <- [1..]]
 
-- ---------------------------------------------------------------------
-- Ejercicio 10. Definir, por recursión, la función
--    triangulares2 :: [Integer]
-- tal que triangulares2 es la lista de los números triangulares. Por
-- ejemplo, 
--    take 10 triangulares2  ==  [1,3,6,10,15,21,28,36,45,55]
-- ---------------------------------------------------------------------
 
triangulares2 :: [Integer]
triangulares2 = 1 : zipWith (+) [2..] triangulares2
 
-- ---------------------------------------------------------------------
-- Ejercicio 11. Definir, usando scanl, la función
--    triangulares3 :: [Integer]
-- tal que triangulares3 es la lista de los números triangulares. Por
-- ejemplo, 
--    take 10 triangulares3  ==  [1,3,6,10,15,21,28,36,45,55]
-- ---------------------------------------------------------------------
 
triangulares3 :: [Integer]
triangulares3 = scanl (+) 1 [2..]
 
-- ---------------------------------------------------------------------
-- Ejercicio 12. Definir la función
--    prop_equivalentes_triangulares :: Int -> Bool
-- tal que (prop_equivalentes_triangulares n) se verifica si las tres
-- definiciones de triangulares coinciden para todos los números entre 1
-- y n. 
--
-- Comprobar si coinciden para los números entre 1 y 1000.
-- ---------------------------------------------------------------------
 
prop_equivalentes_triangulares :: Int -> Bool
prop_equivalentes_triangulares n =
    take n triangulares2 == xs && 
    take n triangulares3 == xs
    where xs = take n triangulares1
 
-- La comprobación  es
--    ghci> prop_equivalentes_triangulares 1000
--    True
 
-- ---------------------------------------------------------------------
-- § Suma de números triangulares                                     --
-- ---------------------------------------------------------------------
 
-- ---------------------------------------------------------------------
-- Ejercicio 13. Definir, usando triangulares1, la función
--    sumaTriangulares1 :: Integer -> Integer
-- tal que (sumaTriangulares1 n) es la suma de los n primeros números
-- triangulares. Por ejemplo,
--    sumaTriangulares1 5  ==  35
-- ---------------------------------------------------------------------
 
sumaTriangulares1 :: Integer -> Integer
sumaTriangulares1 n = sum (genericTake n triangulares1)
 
-- ---------------------------------------------------------------------
-- Ejercicio 14. Definir, usando triangulares1, la función
--    sumaTriangulares2 :: Integer -> Integer
-- tal que (sumaTriangulares2 n) es la suma de los n primeros números
-- triangulares. Por ejemplo,
--    sumaTriangulares2 5  ==  35
-- ---------------------------------------------------------------------
 
sumaTriangulares2 :: Integer -> Integer
sumaTriangulares2 n = sum (genericTake n triangulares2)
 
-- ---------------------------------------------------------------------
-- Ejercicio 15. Definir, usando triangulares3, la función
--    sumaTriangulares3 :: Integer -> Integer
-- tal que (sumaTriangulares3 n) es la suma de los n primeros números
-- triangulares. Por ejemplo,
--    sumaTriangulares3 5  ==  35
-- ---------------------------------------------------------------------
 
sumaTriangulares3 :: Integer -> Integer
sumaTriangulares3 n = sum (genericTake n triangulares3)
 
-- ---------------------------------------------------------------------
-- Ejercicio 16. Comparar el tiempo y espacio utilizado en los
-- siguientes cálculos
--    sumaTriangulares1 1000000
--    sumaTriangulares2 1000000
--    sumaTriangulares3 1000000
-- ---------------------------------------------------------------------
 
-- El cálculo es
--    ghci> sumaTriangulares1 1000000
--    166667166667000000
--    (3.57 secs, 480278768 bytes)
--    ghci> sumaTriangulares2 1000000
--    166667166667000000
--    (1.84 secs, 322014636 bytes)
--    ghci> sumaTriangulares3 1000000
--    166667166667000000
--    (1.81 secs, 321983444 bytes)
 
-- ---------------------------------------------------------------------
-- Ejercicio 17. Calcular las sumas de los n primeros números
-- triangulares para n entre 1 y 5.
-- ---------------------------------------------------------------------
 
-- El cálculo es
--    ghci> [sumaTriangulares3 n | n <- [1..5]]
--    [1,4,10,20,35]
 
-- ---------------------------------------------------------------------
-- Ejercicio 18. A partir del cálculo anterior, conjeturar una fórmula
-- para calcular la suma de los primeros n números triangulares.
-- ---------------------------------------------------------------------
 
-- Usando Wolfram Alpha (como se muestra en http://wolfr.am/MoPMXY ) se
-- obtiene que la suma de los primeros n números triangulares es
--    n*(n+1)*(n+2)/6
 
-- ---------------------------------------------------------------------
-- Ejercicio 19. Comprobar con QuickCheck la conjetura obtenida en el
-- ejercicio anterior.
-- ---------------------------------------------------------------------
 
-- La conjetura es
prop_sumaTriangulares :: Integer -> Property
prop_sumaTriangulares n =
    n > 0 ==> sumaTriangulares3 n == (n*(n+1)*(n+2)) `div` 6
 
-- La comprobación es
--    ghci> quickCheck prop_sumaTriangulares
--    +++ OK, passed 100 tests.
 
-- ---------------------------------------------------------------------
-- § Teorema de Gauss                                                 --
-- ---------------------------------------------------------------------
 
-- ---------------------------------------------------------------------
-- Ejercicio 20. Definir la función 
--    sumas :: [Integer] -> Integer -> Integer -> [[Integer]]
-- tal que (sumas xs m n) es la lista de las de listas crecientes de,
-- como máximo, m elementos de la lista ordenada creciente xs cuya suma
-- es n. Por ejemplo, 
--    ghci> sumas [1..9] 2 7
--    [[1,6],[2,5],[3,4],[7]]
--    ghci> sumas [1..9] 3 7
--    [[1,1,5],[1,2,4],[1,3,3],[1,6],[2,2,3],[2,5],[3,4],[7]]
-- ---------------------------------------------------------------------
 
sumas :: [Integer] -> Integer -> Integer -> [[Integer]]
sumas _  _ 0 = [[]]
sumas [] _ _ = []
sumas _  0 _ = []
sumas (x:xs) m n
    | x > n     = []
    | otherwise = [x:ys | ys <- sumas (x:xs) (m-1) (n-x)] ++ 
                  sumas xs m n
 
-- ---------------------------------------------------------------------
-- Ejercicio 21. Definir la función
--    descomposicionesTriangulares :: Integer -> Integer -> [[Integer]]
-- tal que (descomposicionesTriangulares m n) es la lista crecientes de,
-- como máximo m números triangulares, cuya suma es n. Por ejemplo,
--    descomposicionesTriangulares 3 5   ==  [[1,1,3]]
--    descomposicionesTriangulares 3 6   ==  [[3,3],[6]]
--    descomposicionesTriangulares 3 20  ==  [[10,10]]
--    descomposicionesTriangulares 3 12  ==  [[1,1,10],[3,3,6],[6,6]]
-- ---------------------------------------------------------------------
 
descomposicionesTriangulares :: Integer -> Integer -> [[Integer]]
descomposicionesTriangulares m n = 
    sumas (takeWhile (<=n) triangulares3) m n
 
 
-- ---------------------------------------------------------------------
-- Ejercicio 22. Definir 
--    gradoTriangular :: Integer -> Integer
-- tal que (gradoTriangular n) es el menor cantidad de números
-- triangulares cuya suma es n. Por ejemplo,
--    gradoTriangular 5  ==  3
--    gradoTriangular 6  ==  1
--    gradoTriangular 4  ==  2
-- ---------------------------------------------------------------------
 
gradoTriangular :: Integer -> Integer
gradoTriangular n = 
    minimum [m | m <- [1..n], not (null (descomposicionesTriangulares m n))]
 
-- ---------------------------------------------------------------------
-- Ejercicio 23. Calcular el número mínimo de sumandos para expresar
-- cualquiera de los 20 primeros números naturales.
-- ---------------------------------------------------------------------
 
-- El cálculo es
--    ghci> [gradoTriangular n | n <- [1..20]]
--    [1,2,1,2,3,1,2,3,2,1,2,2,2,3,1,2,3,2,3,2]
 
-- ---------------------------------------------------------------------
-- Ejercicio 24. A la vista del cálculo del ejercicio anterior,
-- conjeturar la menor cota superior del número mínimo de sumandos para
-- expresar cualquiera número natural y comprobar la conjetura con
-- QuickCheck. 
-- ---------------------------------------------------------------------
 
-- La conjetura es que todos los números naturales se pueden expresar
-- como suma de tres, o menos, números triangulares (no necesariamente
-- distintos). 
 
-- La expresión de la conjetura
prop_gradoTriangular :: Integer -> Property
prop_gradoTriangular n =
    n >= 0 ==> not (null (descomposicionesTriangulares 3 n))
 
-- La comprobación es
--    ghci> quickCheck prop_gradoTriangular
--    +++ OK, passed 100 tests.
 
-- ---------------------------------------------------------------------
-- Nota 1. En 1796, el matemático y científico alemán Carl Friedrich
-- Gauss descubrió que todo entero positivo puede representarse como la
-- suma de un máximo de tres números triangulares, hecho que describió
-- en su diario con la misma palabra que usara Arquímedes en su famoso
-- descubrimiento: "¡Eureka! num= Δ + Δ + Δ". 
-- ---------------------------------------------------------------------
 
-- ---------------------------------------------------------------------
-- § Números triangulares de Mersenne                                 --
-- ---------------------------------------------------------------------
 
-- ---------------------------------------------------------------------
-- Ejercicio 25. Definir la función
--    esTriangular :: Integer -> Bool
-- tal que (esTriangular n) se verifica si n es un número
-- triangular. Por ejemplo,
--    esTriangular 10  ==  True
--    esTriangular 12  ==  False
-- ---------------------------------------------------------------------
 
esTriangular :: Integer -> Bool
esTriangular n = 
    n == head (dropWhile (<n) triangulares3)
 
-- ---------------------------------------------------------------------
-- Ejercicio 26. Los números números triangulares de Mersenne son los
-- números triangulares de la forma 2^b-1.
--
-- Definir la función
--    triangularesMersenne :: [Integer]
-- tal que triangularesMersenne es la lista de los números triangulares
-- de Mersenne. Por ejemplo,
--    take 3 triangularesMersenne  ==  [1,3,15]
-- ---------------------------------------------------------------------
 
triangularesMersenne :: [Integer]
triangularesMersenne =
    [2^b-1 | b <- [0..], esTriangular (2^b-1)]
 
-- ---------------------------------------------------------------------
-- Ejercicio 27. Calcular la lista de los números triangulares de
-- Mersenne. 
-- ---------------------------------------------------------------------
 
-- El cálculo es
--    ghci> triangularesMersenne
--    [1,3,15,4095  C-c C-c Interrupted.
-- He abortado el cálculo, porque pasaba tiempo sin encontrar ningún
-- nuevo número.
 
-- ---------------------------------------------------------------------
-- Ejercicio 28. A la vista del cálculo anterior, conjeturar cuál es el
-- mayor número triangular de Mersenne y comprobarla con QuickCheck.
-- ---------------------------------------------------------------------
 
-- La conjetura es que el mayor número triangular de Mersenne es
-- 4095. Puesto que 4095 = 2^12-1, la expresión de la conjetura es para
-- los exponentes entre 13 y n es
prop_triangularMersenne :: Integer -> Bool
prop_triangularMersenne n =
    and [not (esTriangular (2^b-1)) | b <- [13..n]]
 
-- La comprobación para n = 40 es
--    ghci> prop_triangularMersenne 40
--    True

Fuente

Destino
La anterior relación de ejercicios la ha elaborado para

PeH