Menu Close

Día: 18 mayo, 2021

Ternas aditivas

El enunciado del problema C6 de la Fase Local de la Olimpiada Matemática Española del 2006 es

Decimos que tres números naturales distintos forman una terna aditiva si la suma de los dos primeros de ellos es igual al tercero. Hallar, razonadamente, el máximo número de ternas aditivas que puede haber en un conjunto dado de 20 números naturales.

Definir las funciones

   ternasAditivas  :: Integer -> [(Integer,Integer,Integer)]
   nTernasAditivas :: Integer -> Integer

tales que

  • (ternasAditivas n) es la lista de las ternas aditivas crecientes que se pueden formar con los n primeros números enteros positivos. Por ejemplo,
     λ> ternasAditivas 7
     [(1,2,3),(1,3,4),(1,4,5),(1,5,6),(1,6,7),(2,3,5),(2,4,6),(2,5,7),(3,4,7)]
     λ> length (ternasAditivas (10^4))
     24995000
  • (nTernasAditivas n) es el número de ternas aditivas crecientes que se pueden formar con los n primeros números enteros positivos. Por ejemplo,
     nTernasAditivas 7                            ==  9
     length (show (nTernasAditivas (10^(10^5))))  ==  200000
     length (show (nTernasAditivas (10^(10^6))))  ==  2000000
     length (show (nTernasAditivas (10^(10^7))))  ==  20000000

Soluciones

import Data.List (genericLength)
 
-- 1ª definición de ternasAditivas
-- ===============================
 
ternasAditivas :: Integer -> [(Integer,Integer,Integer)]
ternasAditivas n =
  [(a,b,c) | a <- [1..n],
             b <- [a+1..n],
             let c = a+b,
             c <= n]
 
-- 2ª definición de ternasAditivas
-- ===============================
 
ternasAditivas2 :: Integer -> [(Integer,Integer,Integer)]
ternasAditivas2 n =
  [(a,b,a+b) | a <- [1..n],
               b <- [a+1..n-a]]
 
-- Comprobación de equivalencia
-- ============================
 
-- La comprobación es
--    λ> and [ternasAditivas n == ternasAditivas2 n | n <- [1..300]]
--    True
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (ternasAditivas (5*10^3))
--    6247500
--    (4.02 secs, 2,950,741,752 bytes)
--    λ> length (ternasAditivas2 (5*10^3))
--    6247500
--    (1.15 secs, 1,401,184,264 bytes)
 
-- 1ª definición de nTernasAditivas
-- ================================
 
nTernasAditivas :: Integer -> Integer
nTernasAditivas = genericLength . ternasAditivas
 
-- 2ª definición de nTernasAditivas
-- ================================
 
-- Observando los siguientes cálculos
--    λ> [nTernasAditivas n | n <- [1..20]]
--    [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]
--    λ> [(n-1)^2 `div` 4 | n <- [1..20]]
--    [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]
 
nTernasAditivas2 :: Integer -> Integer
nTernasAditivas2 n = (n-1)^2 `div` 4
 
-- 3ª definición de nTernasAditivas
-- ================================
 
nTernasAditivas3 :: Integer -> Integer
nTernasAditivas3 = (`div` 4) . (^ 2) . pred
 
-- Comprobación de equivalencia
-- ============================
 
-- La comprobación es
--    λ> and [nTernasAditivas n == nTernasAditivas2 n | n <- [1..200]]
--    True
--    λ> and [nTernasAditivas2 n == nTernasAditivas3 n | n <- [1..200]]
--    True
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> nTernasAditivas (5*10^3)
--    6247500
--    (5.66 secs, 3,663,331,112 bytes)
--    λ> nTernasAditivas2 (5*10^3)
--    6247500
--    (0.02 secs, 106,752 bytes)
--    λ> nTernasAditivas3 (5*10^3)
--    6247500
--    (0.02 secs, 106,568 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>