Números suma de dos cuadrados
El enunciado de un problema 3.3 de la Fase Local de la Olimpiada Matemática Española del 2004 es
Hallad todas las posibles formas de escribir 2003 como suma de dos cuadrados de números enteros positivos.
Definir la sucesión
sonSumaDosCuadrados :: [Integer]
cuyos elementos son los números que se pueden expresar como suma de los cuadrados de dos números naturales. Por ejemplo,
take 6 sonSumaDosCuadrados == [0,1,2,4,5,8] sonSumaDosCuadrados !! (10^4) == 39593
Comprobar con QuickCheck las siguientes propiedades:
- La sucesión sonSumaDosCuadrados es infinita.
- Los elementos de sonSumaDosCuadrados no son congruentes con 3 módulo 4 (es decir, sus restos al dividirlo por 4 son distintos de 3).
Usando sonSumaDosCuadrados, resolver el problema propuesto; es decir, calcular todas las posibles formas de escribir 2003 como suma de dos cuadrados de números enteros positivos.
Soluciones
import Test.QuickCheck (Property, (==>), quickCheck) -- 1ª solución -- =========== sonSumaDosCuadrados :: [Integer] sonSumaDosCuadrados = filter esSumaDeDosCuadrados [0..] -- (esSumaDeDosCuadrados) se verifica si n se puede escribir como la -- suma de los cuadrados de dos números naturales. Por ejemplo, -- esSumaDeDosCuadrados 5 == True -- esSumaDeDosCuadrados 3 == False esSumaDeDosCuadrados :: Integer -> Bool esSumaDeDosCuadrados = not . null . descomposicionesSumaDosCuadrados -- (descomposicionesSumaDosCuadrados n) es la lista de pares de -- cuadrados de números naturales (con la primera componente menor o -- igual que la segunda) cuya suma es n. Por ejmplo, -- descomposicionesSumaDosCuadrados 3 == [] -- descomposicionesSumaDosCuadrados 4 == [(0,4)] -- descomposicionesSumaDosCuadrados 5 == [(1,4)] -- descomposicionesSumaDosCuadrados 25 == [(0,25),(9,16)] -- descomposicionesSumaDosCuadrados 325 == [(1,324),(36,289),(100,225)] -- descomposicionesSumaDosCuadrados 1105 == [(16,1089),(81,1024),(144,961),(529,576)] descomposicionesSumaDosCuadrados :: Integer -> [(Integer,Integer)] descomposicionesSumaDosCuadrados n = [(a,b) | a <- xs, let b = n - a, b `elem` xs, a <= b] where xs = takeWhile (<= n) cuadrados -- cuadrados es la lista de los cuadrados. Por ejemplo, -- take 10 cuadrados == [0,1,4,9,16,25,36,49,64,81] cuadrados :: [Integer] cuadrados = map (^2) [0..] -- 2ª solución -- =========== sonSumaDosCuadrados2 :: [Integer] sonSumaDosCuadrados2 = filter esSumaDeDosCuadrados2 [0..] esSumaDeDosCuadrados2 :: Integer -> Bool esSumaDeDosCuadrados2 = not . null . descomposicionesSumaDosCuadrados2 descomposicionesSumaDosCuadrados2 :: Integer -> [(Integer,Integer)] descomposicionesSumaDosCuadrados2 n = [(a,b) | a <- ys, let b = n - a, b `elem` m : zs] where m = n `div` 2 xs = takeWhile (<= n) cuadrados (ys,zs) = span (<= m) xs -- 3ª solución -- ========== sonSumaDosCuadrados3 :: [Integer] sonSumaDosCuadrados3 = mezclaTodas [[n^2+k^2 | k <- [n..]] | n <- [0..]] -- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como -- sus elementos son listas infinitas ordenadas. Por ejemplo, -- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]]) -- [2,3,4,5,6,7,8,9,10,11] -- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]]) -- [2,4,6,8,9,10,12,14,16,18] -- --------------------------------------------------------------------- mezclaTodas :: Ord a => [[a]] -> [a] mezclaTodas = foldr1 xmezcla where xmezcla (x:xs) ys = x : mezcla xs ys -- (mezcla xs ys) es la mezcla de las listas infinitas ordenadas xs es -- ys. Por ejemplo, -- take 10 (mezcla [1,3..] [4,8..]) == [1,3,4,5,7,8,9,11,12,13] mezcla :: Ord a => [a] -> [a] -> [a] mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys) | x == y = x : mezcla xs ys | x > y = y : mezcla (x:xs) ys -- Comprobación de equivalencia -- ============================ -- La comprobación es -- λ> take 1000 sonSumaDosCuadrados == take 1000 sonSumaDosCuadrados2 -- True -- λ> take 1000 sonSumaDosCuadrados2 == take 1000 sonSumaDosCuadrados3 -- True -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sonSumaDosCuadrados !! (5*10^3) -- 18973 -- (2.29 secs, 266,485,976 bytes) -- λ> sonSumaDosCuadrados2 !! (5*10^3) -- 18973 -- (1.01 secs, 473,019,976 bytes) -- λ> sonSumaDosCuadrados3 !! (5*10^3) -- 18973 -- (0.17 secs, 103,957,288 bytes) -- -- λ> sonSumaDosCuadrados2 !! (5*10^4) -- 216090 -- (78.14 secs, 17,856,157,080 bytes) -- λ> sonSumaDosCuadrados3 !! (5*10^4) -- 216090 -- (4.23 secs, 3,325,056,480 bytes) -- Propiedades -- =========== -- La primera propiedad es prop_infinitud :: Integer -> Bool prop_infinitud n = (not . null) (dropWhile (<= n) sonSumaDosCuadrados3) -- Su comprobación es -- λ> quickCheck prop_infinitud -- +++ OK, passed 100 tests. -- La segunda propiedad es prop_modulo4 :: Int -> Property prop_modulo4 k = k >= 0 ==> (sonSumaDosCuadrados3 !! k) `mod` 4 /= 3 -- Su comprobación es -- λ> quickCheck prop_modulo4 -- +++ OK, passed 100 tests. -- 4ª solución -- =========== -- Basada en la 2ª propiedad. sonSumaDosCuadrados4 :: [Integer] sonSumaDosCuadrados4 = filter esSumaDeDosCuadrados4 [0..] esSumaDeDosCuadrados4 :: Integer -> Bool esSumaDeDosCuadrados4 = not . null . descomposicionesSumaDosCuadrados4 descomposicionesSumaDosCuadrados4 :: Integer -> [(Integer,Integer)] descomposicionesSumaDosCuadrados4 n | n `mod` 4 == 3 = [] | otherwise = [(a,b) | a <- ys, let b = n - a, b `elem` m : zs] where m = n `div` 2 xs = takeWhile (<= n) cuadrados (ys,zs) = span (<= m) xs -- Comprobación de equivalencia -- ============================ -- La comprobación es -- λ> take 1000 sonSumaDosCuadrados3 == take 1000 sonSumaDosCuadrados4 -- True -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sonSumaDosCuadrados2 !! (10^4) -- 39593 -- (3.60 secs, 1,413,851,720 bytes) -- λ> sonSumaDosCuadrados3 !! (10^4) -- 39593 -- (0.42 secs, 284,603,104 bytes) -- λ> sonSumaDosCuadrados4 !! (10^4) -- 39593 -- (2.58 secs, 1,043,995,480 bytes) -- Cálculo para resolver el problema -- ================================= -- El cálculo es -- λ> 2003 == head (dropWhile (<2003) sonSumaDosCuadrados3) -- False -- Por tanto, no es posible escribir 2003 como suma de dos cuadrados de -- números enteros positivos.