{"id":7169,"date":"2022-08-04T06:00:18","date_gmt":"2022-08-04T04:00:18","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7169"},"modified":"2022-12-14T17:00:18","modified_gmt":"2022-12-14T15:00:18","slug":"numero-de-representaciones-de-n-como-suma-de-dos-cuadrados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numero-de-representaciones-de-n-como-suma-de-dos-cuadrados\/","title":{"rendered":"N\u00famero de representaciones de n como suma de dos cuadrados"},"content":{"rendered":"


\nSea \"n\" un n\u00famero natural cuya factorizaci\u00f3n prima es
\n$$n = 2^{a} \\times p(1)^{b(1)} \\times \\dots \\times p(n)^{b(n)} \\times q(1)^{c(1)} \\times \\dots \\times q(m)^{c(m)}$$
\ndonde los \"p(i)\" son los divisores primos de \"n\" congruentes con 3 m\u00f3dulo 4 y los \"q(j)\" son los divisores primos de \"n\" congruentes con 1 m\u00f3dulo 4. Entonces, el n\u00famero de forma de descomponer \"n\" como suma de dos
\ncuadrados es 0, si alg\u00fan \"b(i)\" es impar y es el techo (es decir, el n\u00famero entero m\u00e1s pr\u00f3ximo por exceso) de
\n$$\\frac{(1+c(1)) \\times \\dots \\times (1+c(m))}{2}$$
\nen caso contrario. Por ejemplo, el n\u00famero
\n$$2^{3} \\times (3^{9} \\times 7^{8}) \\times (5^{3} \\times 13^{6})$$
\nno se puede descomponer como sumas de dos cuadrados (porque el exponente de 3 es impar) y el n\u00famero
\n$$2^{3} \\times (3^{2} \\times 7^{8}) \\times (5^{3} \\times 13^{6})$$
\ntiene 14 descomposiciones como suma de dos cuadrados (porque los exponentes de 3 y 7 son pares y el techo de
\n$$\\frac{(1+3) \\times (1+6)}{2}$$
\nes 14).<\/p>\n

Definir la funci\u00f3n<\/p>\n

\n   nRepresentaciones :: Integer -> Integer\n<\/pre>\n
tal que (nRepresentaciones n) es el n\u00famero de formas de representar n como suma de dos cuadrados. Por ejemplo,<\/p>\n
\n   nRepresentaciones (2^3*3^9*5^3*7^8*13^6)        ==  0\n   nRepresentaciones (2^3*3^2*5^3*7^8*13^6)        ==  14\n   head [n | n <- [1..], nRepresentaciones n > 8]  ==  71825\n<\/pre>\n
Usando la funci\u00f3n representaciones del ejercicio anterior, comprobar con QuickCheck la siguiente propiedad<\/p>\n
\n   prop_representacion :: Positive Integer -> Bool\n   prop_representacion (Positive n) =\n     nRepresentaciones2 n == genericLength (representaciones n)\n<\/pre>\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\nnRepresentaciones1 :: Integer -> Integer\nnRepresentaciones1 n =\n  ceiling (fromIntegral (product (map aux (factorizacion n))) \/ 2)\n  where aux (p,e) | p == 2         = 1\n                  | p `mod` 4 == 3 = if even e then 1 else 0\n                  | otherwise      = e+1\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-- 2\u00aa soluci\u00f3n\n-- ===========\n\nnRepresentaciones2 :: Integer -> Integer\nnRepresentaciones2 n =\n  (1 + product (map aux (factorizacion n))) `div`  2\n  where aux (p,e) | p == 2         = 1\n                  | p `mod` 4 == 3 = if even e then 1 else 0\n                  | otherwise      = e+1\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_nRepresentaciones :: Positive Integer -> Bool\nprop_nRepresentaciones (Positive n) =\n  nRepresentaciones1 n == nRepresentaciones2 n\n  \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_nRepresentaciones\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> head [n | n <- [1..], nRepresentaciones1 n > 8]\n--    71825\n--    (1.39 secs, 2,970,063,760 bytes)\n--    \u03bb> head [n | n <- [1..], nRepresentaciones2 n > 8]\n--    71825\n--    (1.71 secs, 2,943,788,424 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_representacion :: Positive Integer -> Bool\nprop_representacion (Positive n) =\n  nRepresentaciones2 n == genericLength (representaciones n)\n\nrepresentaciones :: Integer -> [(Integer,Integer)]\nrepresentaciones n =\n  [(x,raiz z) | x <- [0..raiz (n `div` 2)], \n                let z = n - x*x,\n                esCuadrado z]\n\nesCuadrado :: Integer -> Bool\nesCuadrado x = x == y * y\n  where y = raiz x\n\nraiz :: Integer -> Integer\nraiz x = floor (sqrt (fromIntegral x))\n    \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_representacion\n--    +++ OK, passed 100 tests.\n\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
Referencias<\/h4>\n