Definir la funci\u00f3n<\/p>\n
\n representaciones :: Integer -> [(Integer,Integer)]\n<\/pre>\ntal que (representaciones n) es la lista de pares de n\u00fameros naturales (x,y) tales que n = x^2 + y^2. Por ejemplo.<\/p>\n
\n representaciones 20 == [(2,4)]\n representaciones 25 == [(0,5),(3,4)]\n representaciones 325 == [(1,18),(6,17),(10,15)]\n length (representaciones (10^14)) == 8\n<\/pre>\nComprobar con QuickCheck que un n\u00famero natural n se puede como suma de dos cuadrados si, y s\u00f3lo si, en la factorizaci\u00f3n prima de n todos los exponentes de sus factores primos congruentes con 3 m\u00f3dulo 4 son pares.<\/p>\n
Soluciones<\/h4>\n\nimport Data.List (genericLength, group)\nimport Data.Numbers.Primes (primeFactors)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nrepresentaciones1 :: Integer -> [(Integer,Integer)]\nrepresentaciones1 n =\n [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nrepresentaciones2 :: Integer -> [(Integer,Integer)]\nrepresentaciones2 n =\n [(x,raiz z) | x <- [0..raiz (n `div` 2)], \n let z = n - x*x,\n esCuadrado z]\n\n-- (raiz x) es la ra\u00edz cuadrada entera de x. Por ejemplo,\n-- raiz 25 == 5\n-- raiz 24 == 4\n-- raiz 26 == 5\nraiz :: Integer -> Integer\nraiz = floor . sqrt . fromIntegral\n \n-- (esCuadrado x) se verifica si x es un n\u00famero al cuadrado. Por\n-- ejemplo,\n-- esCuadrado 25 == True\n-- esCuadrado 26 == False\nesCuadrado :: Integer -> Bool\nesCuadrado x = x == y * y\n where y = raiz x\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n \nrepresentaciones3 :: Integer -> [(Integer, Integer)]\nrepresentaciones3 n = aux 0 (raiz n)\n where aux x y\n | x > y = [] \n | otherwise = case compare (x*x + y*y) n of\n LT -> aux (x + 1) y\n EQ -> (x, y) : aux (x + 1) (y - 1)\n GT -> aux x (y - 1)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_representaciones :: Positive Integer -> Bool\nprop_representaciones (Positive n) =\n all (== representaciones1 n)\n [representaciones2 n,\n representaciones3 n]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_representaciones\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> representaciones1 4000\n-- [(20,60),(36,52)]\n-- (4.95 secs, 2,434,929,624 bytes)\n-- \u03bb> representaciones2 4000\n-- [(20,60),(36,52)]\n-- (0.00 secs, 599,800 bytes)\n-- \u03bb> representaciones3 4000\n-- [(20,60),(36,52)]\n-- (0.01 secs, 591,184 bytes)\n-- \n-- \u03bb> length (representaciones2 (10^14))\n-- 8\n-- (6.64 secs, 5,600,837,088 bytes)\n-- \u03bb> length (representaciones3 (10^14))\n-- 8\n-- (9.37 secs, 4,720,548,264 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_representacion :: Positive Integer -> Bool\nprop_representacion (Positive n) =\n not (null (representaciones2 n)) == \n all (\\(p,e) -> p `mod` 4 \/= 3 || even e) (factorizacion n)\n\n-- (factorizacion n) es la factorizaci\u00f3n prima de n. Por ejemplo,\n-- factorizacion 600 == [(2,3),(3,1),(5,2)]\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n =\n map (\\xs -> (head xs, genericLength xs)) (group (primeFactors n))\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_representacion\n-- +++ OK, passed 100 tests.\n<\/pre>\n