Ir al contenido principal

Número de representaciones de n como suma de dos cuadrados

Sea \( n \) un número natural cuya factorización prima es \[ n = 2^a \cdot p_1^{b_1} \cdots p_n^{b_n} \cdot q_1^{c_1} \cdots q_m^{c_m} \] donde los \( p_i \) son los divisores primos de \( n \) congruentes con \( 3 \) módulo \( 4 \) y los \( q_j \) son los divisores primos de \( n \) congruentes con \( 1 \) módulo \( 4 \). Entonces, el número de formas de descomponer \( n \) como suma de dos cuadrados es \( 0 \), si algún \( b_i \) es impar y es el techo (es decir, el número entero más próximo por exceso) de \[ \frac{(1+c_1) \cdots (1+c_m)}{2} \] en caso contrario. Por ejemplo, el número \( 2^3 \cdot (3^9 \cdot 7^8) \cdot (5^3 \cdot 13^6) \) no se puede descomponer como sumas de dos cuadrados (porque el exponente de \( 3 \) es impar) y el número \( 2^3 \cdot (3^2 \cdot 7^8) \cdot (5^3 \cdot 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)(1+6)}{2} \) es \( 14 \)).

Definir la función

   nRepresentaciones :: Integer -> Integer

tal que (nRepresentaciones n) es el número de formas de representar n como suma de dos cuadrados. Por ejemplo,

   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

prop_nRepresentaciones :: Integer -> Property
prop_nRepresentaciones n =
    n > 0 ==>
      nRepresentaciones2 n == genericLength (representaciones n)

Soluciones

import Test.QuickCheck
import Data.List (genericLength, group)
import Data.Numbers.Primes (primeFactors)

-- 1ª definició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ª definició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 la propiedad
-- ============================

-- La propiedad es
prop_nRepresentaciones :: Integer -> Property
prop_nRepresentaciones n =
    n > 0 ==>
      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
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_representacion
--    +++ OK, passed 100 tests.

Referencias

La sucesión [nRepresentaciones n | n <- [0..]] es la A000161 de la OEIS.