Número de representaciones de n como suma de dos cuadrados
Sea 
$$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)}$$
donde los 
cuadrados es 0, si algún 
$$\frac{(1+c(1)) \times \dots \times (1+c(m))}{2}$$
en caso contrario. Por ejemplo, el número
$$2^{3} \times (3^{9} \times 7^{8}) \times (5^{3} \times 13^{6})$$
no se puede descomponer como sumas de dos cuadrados (porque el exponente de 3 es impar) y el número
$$2^{3} \times (3^{2} \times 7^{8}) \times (5^{3} \times 13^{6})$$
tiene 14 descomposiciones como suma de dos cuadrados (porque los exponentes de 3 y 7 son pares y el techo de
$$\frac{(1+3) \times (1+6)}{2}$$
es 14).
Definir la función
|
1 |
nRepresentaciones :: Integer -> Integer |
tal que (nRepresentaciones n) es el número de formas de representar n como suma de dos cuadrados. Por ejemplo,
|
1 2 3 |
nRepresentaciones (2^3*3^9*5^3*7^8*13^6) == 0 nRepresentaciones (2^3*3^2*5^3*7^8*13^6) == 14 head [n | n <- [1..], nRepresentaciones n > 8] == 71825 |
Usando la función representaciones del ejercicio anterior, comprobar con QuickCheck la siguiente propiedad
|
1 2 3 |
prop_representacion :: Positive Integer -> Bool prop_representacion (Positive n) = nRepresentaciones2 n == genericLength (representaciones n) |
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 |
import Data.List (genericLength, group) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck (Positive (Positive), quickCheck) -- 1ª solución -- =========== nRepresentaciones1 :: Integer -> Integer nRepresentaciones1 n = ceiling (fromIntegral (product (map aux (factorizacion n))) / 2) where aux (p,e) | p == 2 = 1 | p `mod` 4 == 3 = if even e then 1 else 0 | otherwise = e+1 -- (factorizacion n) es la factorización prima de n. Por ejemplo, -- factorizacion 600 == [(2,3),(3,1),(5,2)] factorizacion :: Integer -> [(Integer,Integer)] factorizacion n = map (\xs -> (head xs, genericLength xs)) (group (primeFactors n)) -- 2ª solución -- =========== nRepresentaciones2 :: Integer -> Integer nRepresentaciones2 n = (1 + product (map aux (factorizacion n))) `div` 2 where aux (p,e) | p == 2 = 1 | p `mod` 4 == 3 = if even e then 1 else 0 | otherwise = e+1 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_nRepresentaciones :: Positive Integer -> Bool prop_nRepresentaciones (Positive n) = nRepresentaciones1 n == nRepresentaciones2 n -- La comprobación es -- λ> quickCheck prop_nRepresentaciones -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> head [n | n <- [1..], nRepresentaciones1 n > 8] -- 71825 -- (1.39 secs, 2,970,063,760 bytes) -- λ> head [n | n <- [1..], nRepresentaciones2 n > 8] -- 71825 -- (1.71 secs, 2,943,788,424 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_representacion :: Positive Integer -> Bool prop_representacion (Positive n) = nRepresentaciones2 n == genericLength (representaciones n) representaciones :: Integer -> [(Integer,Integer)] representaciones n = [(x,raiz z) | x <- [0..raiz (n `div` 2)], let z = n - x*x, esCuadrado z] esCuadrado :: Integer -> Bool esCuadrado x = x == y * y where y = raiz x raiz :: Integer -> Integer raiz x = floor (sqrt (fromIntegral x)) -- La comprobación es -- λ> quickCheck prop_representacion -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.
Referencias
- W. Stein, Which numbers are the sum of two squares?.
- E.W. Weisstein, Sum of squares function en MathWorld.
- N.J.A. Sloane,Sucesión A004018 de OEIS.
- Expressing a number as a sum of two squares.
- Sum of squares.