maximoValor :: Integer -> Integer

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

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