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