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
1 |
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,
1 2 3 |
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
-- 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 |
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