Día: 19-mayo-2021

El enunciado del 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

cuyos elementos son los números que se pueden expresar como suma de los cuadrados de dos números naturales. Por ejemplo,

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

<

pre lang=»haskell»>
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,2n..] | n <- [2..]]) -- [2,3,4,5,6,7,8,9,10,11] -- λ> take 10 (mezclaTodas [[n,2n..] | 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 !! (510^3)
— 18973
— (2.29 secs, 266,485,976 bytes)
— λ> sonSumaDosCuadrados2 !! (510^3)
— 18973
— (1.01 secs, 473,019,976 bytes)
— λ> sonSumaDosCuadrados3 !! (5*10^3)
— 18973

— (0.17 secs, 103,957,288 bytes)

— λ> sonSumaDosCuadrados2 !! (510^4)
— 216090
— (78.14 secs, 17,856,157,080 bytes)
— λ> sonSumaDosCuadrados3 !! (510^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.

Nuevas soluciones

• En los comentarios se pueden escribir nuevas soluciones.
• El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>