Descomposiciones en sumas de cuadrados en Haskell
Esta relación de ejercicios, para la asignatura de Informática de 1º del Grado en Matemáticas, se basa en el problema 19 de los desafíos matemáticos de El País titulado Cuadrados que suman grandes cifras cuyo enunciado es el siguiente
Los números cuadrados (o cuadrados perfectos) son los cuadrados de los números naturales, es decir: 1 (1^2), 4 (2^2), 9 (3^2), 16 (4^2), 25 (5^2), etcétera. En el problema de esta semana trataremos de descubrir de cuántas maneras distintas se puede escribir un número dado como suma de cuatro cuadrados. Por ejemplo, el número 39 se puede escribir de dos formas: 39=1+1+1+36 y 39=1+4+9+25. Observemos que se pueden repetir sumandos y que no contaremos como maneras distintas de escritura las que se obtienen al cambiar el orden de los sumandos.
Las preguntas concretas son: ¿De cuántas formas distintas se puede escribir 2^2012 como suma de cuatro cuadrados? ¿Y de cuántas formas se puede escribir 2^2011?
La relación de ejercicios es la siguiente
|
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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
-- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- sumasNcuadrados :: Integer -> Integer -> [[Integer]] -- tal que (sumasNcuadrados x n) es la lista de las descomposiciones de -- x en sumas decrecientes de n cuadrados. Por ejemplo, -- sumasNcuadrados 39 4 == [[6,1,1,1],[5,3,2,1]] -- --------------------------------------------------------------------- sumasNcuadrados :: Integer -> Integer -> [[Integer]] sumasNcuadrados 0 _ = [] sumasNcuadrados x 1 | a^2 == x = [[a]] | otherwise = [] where a = ceiling (sqrt (fromIntegral x)) sumasNcuadrados x (n+1) = [a:y:ys | a <- [x',x'-1..1], (y:ys) <- sumasNcuadrados (x-a^2) n, y <= a] where x' = ceiling (sqrt (fromIntegral x)) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- potenciaDe2ComoSumaDe4Cuadrados :: Integer -> [[Integer]] -- tal que (potenciaDe2ComoSumaDe4Cuadrados x) es la lista de las -- descomposiciones de 2^x en sumas decrecientes de n cuadrados. Por -- ejemplo, -- potenciaDe2ComoSumaDe4Cuadrados 6 == [[4,4,4,4]] -- --------------------------------------------------------------------- potenciaDe2ComoSumaDe4Cuadrados :: Integer -> [[Integer]] potenciaDe2ComoSumaDe4Cuadrados x = sumasNcuadrados (2^x) 4 -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- potenciasDe2ComoSumaDe4Cuadrados :: Integer -> Integer -> -- [(Integer,[[Integer]])] -- tal que (potenciasDe2ComoSumaDe4Cuadrados n m) es la lista de los -- pares (x,ys) tales que n <= x <= m e ys es la lista de las -- descomposiciones de 2^x en sumas decrecientes de n cuadrados. Por -- ejemplo, -- ghci> potenciasDe2ComoSumaDe4Cuadrados 4 5 -- [(4,[[2,2,2,2]]),(5,[])] -- --------------------------------------------------------------------- potenciasDe2ComoSumaDe4Cuadrados :: Integer -> Integer -> [(Integer,[[Integer]])] potenciasDe2ComoSumaDe4Cuadrados n m = [(x,potenciaDe2ComoSumaDe4Cuadrados x) | x <- [n..m]] -- --------------------------------------------------------------------- -- Ejercicio 4. Usando la función potenciasDe2ComoSumaDe4Cuadrados -- calcular la lista de las descomposiciones de 2^x en sumas -- decrecientes de n cuadrados, para x entre 1 y 10. -- --------------------------------------------------------------------- -- El cálculo es -- ghci> potenciasDe2ComoSumaDe4Cuadrados 1 10 -- [(1,[]),(2,[[1,1,1,1]]), -- (3,[]),(4,[[2,2,2,2]]), -- (5,[]),(6,[[4,4,4,4]]), -- (7,[]),(8,[[8,8,8,8]]), -- (9,[]),(10,[[16,16,16,16]])] -- --------------------------------------------------------------------- -- Ejercicio 5. A partir del cálculo anterior conjeturar el valor de -- (potenciaDe2ComoSumaDe4Cuadrados x)) y usando la conjetura -- definir la función -- potenciaDe2ComoSumaDe4Cuadrados' :: Integer -> [[Integer]] -- que sea equivalente a potenciaDe2ComoSumaDe4Cuadrados. -- --------------------------------------------------------------------- potenciaDe2ComoSumaDe4Cuadrados' :: Integer -> [[Integer]] potenciaDe2ComoSumaDe4Cuadrados' x | odd x = [] | otherwise = [[y,y,y,y]] where y = 2^((x `div` 2) - 1) -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- conjetura :: Integer -> Integer -> Bool -- tal que (conjetura n m) se verifica si los valores de -- potenciaDe2ComoSumaDe4Cuadrados y potenciaDe2ComoSumaDe4Cuadrados' -- para todo x entre n y m. -- -- Comprobar la conjetura para los valores entre 1 y 20. -- --------------------------------------------------------------------- conjetura :: Integer -> Integer -> Bool conjetura n m = and [potenciaDe2ComoSumaDe4Cuadrados x == potenciaDe2ComoSumaDe4Cuadrados' x | x <- [n..m]] -- La comprobación es -- ghci> conjetura 1 20 -- True -- --------------------------------------------------------------------- -- Ejercicio 7. Usando la conjetura, resolver el desafío; es decir, -- responder a las preguntas ¿de cuántas formas distintas se puede -- escribir 2^2012 como suma de cuatro cuadrados? ¿Y de cuántas formas -- se puede escribir 2^2011? -- --------------------------------------------------------------------- -- El cálculo es -- ghci> length (potenciaDe2ComoSumaDe4Cuadrados' 2012) -- 1 -- ghci> length (potenciaDe2ComoSumaDe4Cuadrados' 2011) -- 0 |
La demostración se encuentra en Una única suma posible de cuadrados.