Menu Close

Máxima suma de dos cuadrados condicionados

El enunciado del problema 3 de la IMO (Olimpiada Internacional de Matemáticas) de 1981 es

Calcular el máximo valor de m² + n² donde m y n son números enteros tales que m, n ∈ {1, 2, …, 1981} y (n² – mn – m²)² = 1.

Definir la función

   maximoValor :: Integer -> Integer

tal que (maximoValor k) es el máximo valor de m² + n² donde m y n son números enteros tales que m, n ∈ {1, 2, …, k} y (n² – mn – m²)² = 1. Por ejemplo,

   maximoValor 10       ==  89
   maximoValor (10^20)  ==  9663391306290450775010025392525829059713
   length (show (maximoValor5 (10^(4*10^4))))  ==  80000

Usando la función maximoValor, calcular la respuesta del problema.

Soluciones
-- 1ª solución
-- ===========
 
maximoValor :: Integer -> Integer
maximoValor k =
  maximum [m^2 + n^2 | m <- [1..k],
                       n <- [m..k],
                       (n^2 - m*n - m^2)^2 == 1]
 
-- 2ª solución
-- ===========
 
maximoValor2 :: Integer -> Integer
maximoValor2 k =
  maximum [m^2 + n^2 | (m, n) <- soluciones k]
 
-- (soluciones k) es la lista de los pares (m,n) tales que
-- m, n ∈ {1, 2,..., k}, m <= n y (n² - mn - m²)² = 1.
-- Por ejemplo,
--    λ> soluciones 50
--    [(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34)]
soluciones :: Integer -> [(Integer,Integer)]
soluciones k =
  [(m, n) | m <- [1..k],
            n <- [m..k],
            (n^2 - m*n - m^2)^2 == 1]
 
-- 3ª solución
-- ===========
 
maximoValor3 :: Integer -> Integer
maximoValor3 k = m^2 + n^2
  where (m, n) = last (soluciones k)
 
-- 4ª solución
-- ===========
 
maximoValor4 :: Integer -> Integer
maximoValor4 k = m^2 + n^2
  where (m, n) = head [(m, n) | m <- [k,k-1..1],
                                n <- [k,k-1..m],
                                (n^2 - m*n - m^2)^2 == 1]
 
-- 5ª solución
-- ===========
 
-- Con el siguiente cálculo
--    λ> soluciones 50
--    [(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34)]
-- se observa que las soluciones son pares de términos consecutivos de
-- la sucessión de Fibonacci.
 
maximoValor5 :: Integer -> Integer
maximoValor5 k = m^2 + n^2
  where [m,n] = take 2 (reverse (takeWhile (<= k) fibs))
 
-- fibs es la la sucesión de los números de Fibonacci. Por ejemplo,
--    take 14 fibs  == [1,1,2,3,5,8,13,21,34,55,89,144,233,377]
fibs :: [Integer]
fibs = 1 : scanl (+) 1 fibs
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> maximoValor 1500
--    1346269
--    (1.94 secs, 2,188,819,744 bytes)
--    λ> maximoValor2 1500
--    1346269
--    (1.93 secs, 2,188,821,752 bytes)
--    λ> maximoValor3 1500
--    1346269
--    (1.95 secs, 2,188,803,312 bytes)
--    λ> maximoValor4 1500
--    1346269
--    (0.71 secs, 775,331,376 bytes)
--    λ> maximoValor5 1500
--    1346269
--    (0.01 secs, 106,952 bytes)
--
--    λ> maximoValor4 4000
--    9227465
--    (5.00 secs, 5,641,750,992 bytes)
--    λ> maximoValor5 4000
--    9227465
--    (0.01 secs, 107,104 bytes)
 
-- Cálculo de la respuesta
-- =======================
 
-- El cálculo es
--    λ> maximoValor5 1981
--    3524578

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="haskell"> y otra con </pre>

Una solución de “Máxima suma de dos cuadrados condicionados

  1. Alejandro García Alcaide
    import Test.QuickCheck
    -- Esta definicion no es, sin embargo, muy eficiente. No obstante, es capaz de
    -- hallar la solucion del problema.
     
    maximoValor1 :: Integer -> Integer
    maximoValor1 k =
      maximum [m^2+n^2 | m <- [1..k], n <- [1..k], (n^2-m*n-m^2)^2 == 1]
     
    -- λ> maximoValor1 1981
    -- 3524578
    -- (15.45 secs, 7,629,307,312 bytes)
     
    -- Buscamos otra forma de definir esta funcion que sea mas eficiente. Si nos
    -- damos cuenta, x^2==1 <==> abs x = 1. Entonces: 
    maximoValor2 :: Integer -> Integer
    maximoValor2 k =
      maximum [m^2+n^2 | m <- [1..k], n <- [1..k], abs (n^2-m*n-m^2) == 1]
     
    -- λ> maximoValor2 1981
    -- 3524578
    -- (10.31 secs, 5,726,214,856 bytes)
     
    -- Vamos a intentar mejorar un poco mas la eficiencia. 
    maximoValor3 :: Integer -> Integer
    maximoValor3 k = m^2+n^2
     where (m,n) = conjuntoDePares k
             where conjuntoDePares k =
                     head [(m,n) | m <- [k,k-1..1], n <- [k,k-1..1],
                           abs (n^2-m*n-m^2) == 1]
     
    -- Veamos si la definicion es correcta.
    propiedad :: Integer -> Property 
    propiedad k = k > 0 ==> maximoValor1 k == maximoValor3 k
     
    -- λ> quickCheck prop
    -- +++ OK, passed 100 tests.
    -- (0.71 secs, 328,660,584 bytes)
     
    -- Efectivamente, hemos conseguido mejorar la eficiencia:
    -- λ> maximoValor3 1981
    -- 3524578
    -- (5.91 secs, 3,103,647,048 bytes)

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.