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

1 2	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

λ> 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

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)

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>

Un comentario

import Data.List (genericLength)
import Test.QuickCheck (quickCheck)

-- Definiciones de ternasAditivas:
-- ==============================

ternasAditivas1  :: Integer -> [(Integer,Integer,Integer)]
ternasAditivas1 n = [(a,b,c) | a <- [1..n], b <- [a+1..n], let c = a+b, c <= n] 

ternasAditivas2 :: Integer -> [(Integer,Integer,Integer)]
ternasAditivas2 n = [(a,b,c) | a <- [1..k], b <- [a+1..n-a], let c = a+b]
  where k = div n 2

-- Equivalencia de las definiciones:
-- ================================

prop1 :: Integer -> Bool
prop1 n = ternasAditivas1 m == ternasAditivas2 m
  where m = abs n + 1

-- La comprobación es:
-- λ> quickCheck prop1
-- +++ OK, passed 100 tests.

-- Comparación de eficiencia:
-- =========================

-- λ> length (ternasAditivas1 1500)
-- 561750
-- (0.86 secs, 265,750,936 bytes)
-- λ> length (ternasAditivas2 1500)
-- 561750
-- (0.22 secs, 126,136,296 bytes)
--
-- λ> length (ternasAditivas4 7500)
-- 14058750
-- (4.85 secs, 3,150,451,720 bytes)

ternasAditivas :: Integer -> [(Integer,Integer,Integer)]
ternasAditivas = ternasAditivas2

-- Definiciones de nTernasAditivas:
-- ===============================

nTernasAditivas1 :: Integer -> Integer
nTernasAditivas1 = genericLength . ternasAditivas

-- Vamos a calcular nTernasAditivas1 para los primeros 20 números naturales.
--    λ> [nTernasAditivas1 n | n <- [1..20]]
--    [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]
--
-- Los términos de van construyendo de la forma 0+0+1+1+2+2+3+3+...
--    + Si n es par, tenemos un número par de sumandos y el número de ternas
--    aditivas es el siguiente:
--       2*(1+2+...+n/2-1)
--       = 2*((n/2-1)*(n/2-1+1))/2
--       = n/2*(n-2)/2
--       = (n(n-2))/4
--
--    + Si n es impar, tenemos un número impar de sumandos y el número de
--    ternas aditivas es el siguiente:
--       2*(1+2+...+(n-1)/2-1) + (n-1)/2
--       = 2*(((n-1)/2-1)*((n-1)/2)-1+1)/2 + (n-1)/2
--       = ((n-1)/2)*((n-3)/2) + (n-1)/2
--       = ((n-1)/2)*((n-3)/2 + 1)
--       = ((n-1)/2)^2

nTernasAditivas2 :: Integer -> Integer
nTernasAditivas2 n
  | even n = div (n*(n-2)) 4
  | odd n  = (div (n-1) 2)^2

-- Equivalencia de las definiciones:
-- ================================

prop2 :: Integer -> Bool
prop2 n = nTernasAditivas1 m == nTernasAditivas2 m
  where m = abs n + 1

-- La comprobación es:
-- λ> quickCheck prop2
-- +++ OK, passed 100 tests.

-- Comparación de eficiencia:
-- =========================

-- λ> nTernasAditivas1 5000
-- 6247500
-- (3.04 secs, 2,112,905,800 bytes)
-- λ> nTernasAditivas2 5000
-- 6247500
-- (0.00 secs, 60,008 bytes)
--
-- λ> length (show (nTernasAditivas2 (10^(10^7))))
-- 20000000
-- (3.67 secs, 1,135,725,432 bytes)

nTernasAditivas :: Integer -> Integer
nTernasAditivas = nTernasAditivas2

import Data.List (genericLength)

import Test.QuickCheck (quickCheck)

-- Definiciones de ternasAditivas:

-- ==============================

ternasAditivas1 :: Integer -> [(Integer,Integer,Integer)]

ternasAditivas1 n = [(a,b,c) | a <- [1..n], b <- [a+1..n], let c = a+b, c <= n]

ternasAditivas2 :: Integer -> [(Integer,Integer,Integer)]

ternasAditivas2 n = [(a,b,c) | a <- [1..k], b <- [a+1..n-a], let c = a+b]

where k = div n 2

-- Equivalencia de las definiciones:

-- ================================

prop1 :: Integer -> Bool

prop1 n = ternasAditivas1 m == ternasAditivas2 m

where m = abs n + 1

-- La comprobación es:

-- λ> quickCheck prop1

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia:

-- =========================

-- λ> length (ternasAditivas1 1500)

-- 561750

-- (0.86 secs, 265,750,936 bytes)

-- λ> length (ternasAditivas2 1500)

-- 561750

-- (0.22 secs, 126,136,296 bytes)

-- λ> length (ternasAditivas4 7500)

-- 14058750

-- (4.85 secs, 3,150,451,720 bytes)

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

ternasAditivas = ternasAditivas2

-- Definiciones de nTernasAditivas:

-- ===============================

nTernasAditivas1 :: Integer -> Integer

nTernasAditivas1 = genericLength . ternasAditivas

-- Vamos a calcular nTernasAditivas1 para los primeros 20 números naturales.

-- λ> [nTernasAditivas1 n | n <- [1..20]]

-- [0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90]

-- Los términos de van construyendo de la forma 0+0+1+1+2+2+3+3+...

-- + Si n es par, tenemos un número par de sumandos y el número de ternas

-- aditivas es el siguiente:

-- 2*(1+2+...+n/2-1)

-- = 2*((n/2-1)*(n/2-1+1))/2

-- = n/2*(n-2)/2

-- = (n(n-2))/4

-- + Si n es impar, tenemos un número impar de sumandos y el número de

-- ternas aditivas es el siguiente:

-- 2*(1+2+...+(n-1)/2-1) + (n-1)/2

-- = 2*(((n-1)/2-1)*((n-1)/2)-1+1)/2 + (n-1)/2

-- = ((n-1)/2)*((n-3)/2) + (n-1)/2

-- = ((n-1)/2)*((n-3)/2 + 1)

-- = ((n-1)/2)^2

nTernasAditivas2 :: Integer -> Integer

nTernasAditivas2 n

| even n = div (n*(n-2)) 4

| odd n = (div (n-1) 2)^2

-- Equivalencia de las definiciones:

-- ================================

prop2 :: Integer -> Bool

prop2 n = nTernasAditivas1 m == nTernasAditivas2 m

where m = abs n + 1

-- La comprobación es:

-- λ> quickCheck prop2

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia:

-- =========================

-- λ> nTernasAditivas1 5000

-- 6247500

-- (3.04 secs, 2,112,905,800 bytes)

-- λ> nTernasAditivas2 5000

-- 6247500

-- (0.00 secs, 60,008 bytes)

-- λ> length (show (nTernasAditivas2 (10^(10^7))))

-- 20000000

-- (3.67 secs, 1,135,725,432 bytes)

nTernasAditivas :: Integer -> Integer

nTernasAditivas = nTernasAditivas2

Responder

Ternas aditivas

Soluciones

Nuevas soluciones

Un comentario

Leave a Reply to Rubén Muñoz MkrtchianCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Nuevas soluciones

Se puede imprimir o compartir con

Un comentario

Leave a Reply to Rubén Muñoz MkrtchianCancel reply

Entradas recientes

Buscar

Correo electrónico